| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Damned solution | andreyDagger`~ | 1148. Building Towers | 15 июл 2023 01:29 | 1 |
I used my own hash map with modulo 1e5, and buckets with size equal to one |
| Fine | bdzxt | 1148. Building Towers | 24 мар 2017 18:48 | 2 |
Fine bdzxt 12 мар 2017 08:23 //tower.in
1000 60 10
1
2
3
4
5
20170312
666666666
888888888
999999999
427749136024120470
427749136024120471
427749136024120472
-1
//tower.out
427749136024120472
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 4 3
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 4 5 6 7 6 7 6 7 8 9 8 7 6 5 6 7 8 9 10 9 8 9 10 11
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 2 3 2 3 4 3 4 3 4 5 6 7 8 9 8 9 10 11 12 11 10 9 10 9 10 9 10 9 8 9
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 2 3 4 5 6 5 4 5 6 5 4 3 4 5 6 7 8 9 10 9 8 9 8 7 6 7 6 5 4 5
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 3 4 3 4 5 4 5 6 7 8 9 10 9 8 7 8 9 8 9 10 9 8 9 10 11 12 11 12 13 14 13
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 7 6 5 4 3 2 1 2 3 2 1
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 7 6 5 4 3 2 3 2 1 2 1
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 8 7 6 5 4 3 2 1 2 1 2 1
I finished it in 0.015s. |
| Is it possible to beat MLE with c#? | AIT | 1148. Building Towers | 18 дек 2012 02:16 | 3 |
I tried my solution, I think it should use at most 2MB of memory and got MLE on first test? Is it c# related problem or my solution is that bad? up: i checked the memory usage for 30000 60 10, it's about 300000*4 bytes |
| Please, write correct answer for test | QQQQ | 1148. Building Towers | 22 май 2012 13:07 | 3 |
2369 60 10
1
19
37507396740
37507396740376
65476805623000
-1
or some else test with big numbers and n < h*(h+m+m-1)/2 465476805623937393
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 4 5 6 5
10 9 8 7 6 5 4 3 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 2 1 2 3 4 5 6 7 6 7 6 5 4 5 4 3 2 3 4 5 4 5 6 7 6 5 6 5 6 5 4 3 2 1 2 3
10 9 8 7 6 5 4 3 2 1 2 3 2 1 2 3 4 3 4 5 4 5 4 3 4 3 2 3 4 3 2 3 4 5 6 7 6 7 8 9 10 11 10 11 12 11 10 9 8 9 10 11 12 11 12 13 12 13 14 15
10 9 8 7 6 5 4 3 2 1 2 3 4 3 2 1 2 3 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 14 15 14 13 14 13 12 13 12 11 10 9 8 9 8 7 8 9 10 9 8 9 10 9 8 9 My program provides this result but has got "Wrong answer".............. I found the mistake in my program.
Edited by author 22.05.2012 13:08
Edited by author 31.05.2012 18:13 |
| C# crash | AutumnSky | 1148. Building Towers | 28 апр 2012 03:41 | 1 |
No needed now.
Edited by author 06.06.2012 15:50 |
| no subject | IGOR_Lviv NU | 1148. Building Towers | 16 окт 2009 02:58 | 1 |
Edited by author 16.10.2009 05:03 |
| Who can help me? | bobchennan | 1148. Building Towers | 10 июл 2009 15:35 | 1 |
Now I know how to use DP to count the total number,but how to describ the tower with number K given in respective line of input?I can't work out it.
Could someone give me some hints about this problem or give me the codes?My email address is bobchennan@gmail.com. Thanks!
|
| How to solve this problem? | ftc | 1148. Building Towers | 15 дек 2008 19:00 | 2 |
I have written a solution with O(n * (m + h) + k * h * h * n * (m + h)) time and O(n * (m + h)) memory, but i can't optimize it to work less than 3.5 seconds. Could somebody give me a hint on better solution? DP works.
Let __int64 F[60][70][3000] is such array that
F[i][j][k] number of ways to build tower from level i
having at bottom j bricks and k bricks for using.
then F[i][j][k]=F[i+1][j-1][k-j]+F[i+1][j+1][k-j].
But here 4200*3000*8 bytes!?. After thinking we find that
really in his space used 90000 8-places and 590000 4-places.After this we are using structure int **F[60] as store for 4-places and address for 8-places.If data for DP placed compactly all testes processed quickly.
Edited by author 15.12.2008 19:03 |
| =( | Teacher30 | 1148. Building Towers | 28 сен 2008 23:11 | 1 |
=( Teacher30 28 сен 2008 23:11 When ML was 1 MB instead of 4MB, problem was much more interesting. Now simple solution with "hashes" passes.
There are no AC solutions which use Java or C#... Judges, could you decrease ML? =) |
| Minor fix | Denis Koshman | 1148. Building Towers | 13 сен 2008 21:48 | 3 |
It's not clear from problem statement that towers are numbered in lexicographical order of their records. "Those arrays are sorted in ascending order."
I don't remember if this phrase was there or appeared as result of my previous post, but still it sounds strangely... Because one may think that it speks about internal arrays sorting, so what's the point writing them bottom-up then? :) Also, ascending sorting does not state criteria of descent/ascension (lexicographity).
I'd write it like this: "List of those arrays is sorted in lexicographically ascending order."
I'm sorry for being probably too pedantic :) |
| Java MLE | DWED | 1148. Building Towers | 15 авг 2008 03:07 | 2 |
Is it possible to solve this problem in Java without MLE?
If we use HashMap<Integer,Long> as "cache" we get 287k entries in worst case. Even if ww think about raw data (no objects, no overlap) - it is 3.4Mb
Still thinking how to avoid "full-sized" caching (h X m+h X n). Finally I solved this problem in Java =)
To reduce cache size I used fact that for any N >= Nmax we get f(N,M,H)=const. As analys of cache has shown - it is about 85% of entries. So I built 3 tables - Nmin, Nmax and F.
After that i has maximum 56k entries. But that was also too much for system (huh, i tested on my machine - it got used slightly less than 4Mb...)
I read discussions about this problem and used one hint - we can cache, for example, only even levels. As for performance - it is just 2 times slower... but it gets 2 times less memory... Exactly what we need =)
Good luck. |
| Problem 1148 "Building Towers" has been rejudged (+) | Vladimir Yakovlev (USU) | 1148. Building Towers | 24 окт 2006 19:22 | 1 |
New tests have been added to this problem.
All submissions have been rejudged. Some lost AC because of new tests nad some got AC after changes of memory limit, compilers settings and hardware.
Edited by author 24.10.2006 19:23 |
| How to solve it fast? | Burunduk1 | 1148. Building Towers | 15 мар 2006 15:22 | 4 |
n <= 2400
My AC solution is O(h*n*(m+h) + k*h^2*n*(m+h))
And it uses O(n*(m+h)) of memory.
But there are so many AC in 0.015 sec!
And some AC program's use less than 200K of memory...
I can't invent something like myself :(
Please, anybody explain me fast solution for this problem. Mail me to Ilya[dot]Grebnov[at]mail[dot]ru It is easy. Tests are weak :) My solution uses 400kb instead of 3Mb and works 0.015s instead of 0.5s. It seems, there are n less then 100 or greater then 5000 always. You can use it. |
| The memory limit make it a really good problem:) | Yu Yuanming | 1148. Building Towers | 28 дек 2005 19:45 | 2 |
|
| This problem is a bit complicated.... | Hurricane_NET | 1148. Building Towers | 4 дек 2005 16:17 | 1 |
How to solve it faster than O(hn + querys*h)? It seems that some people managed to solve it in less than 0.1 sec... and I really don't know how...
Thanks! |
| Why should my program get Fail(Compilation)? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1148. Building Towers | 3 авг 2005 20:42 | 2 |
It just stay compiling for a long time, then Fail appears! service unavailable at the very moment？I dunno |
| Who can help me ? | ChenShi @ZSU | 1148. Building Towers | 28 апр 2004 09:45 | 5 |
What is the answer when N=32767,H=60,M=10 ?
My answer is 465476805623937394, is it correct?
I used unsigned long long type, but got TLE. It's very strange.
I got WA when I used long double type. The answer is correct. I also got WA when use Extended type, but got AC when change it to Int64. Thank you very much.
What's the C++ compiler here ? |
| Could anybody tell my why does my program get ML?(+) | shitty.Mishka | 1148. Building Towers | 15 авг 2002 01:54 | 3 |
I tried to submit my program with Comp or Extended and got WA, so I
used long arifmetics, and now I get ML even if I put the maximal
length of the number to be 5 digits!
Here's my program:
[deleted by moderator]
Edited by moderator 11.04.2004 01:33 It really uses small memory, and solution with comp(extended) type
is good (as I think) too, but..
Try this test case:
302 60 10
All the error of the algorithm is TL! (maybe, dynamic?..) The number of towers is less than 2^59 (each new level is either +1
or -1). Comp/__int64 has got 64 bits, so long numbers shouldn't be
needed.
>
> [deleted by moderator]
Edited by moderator 11.04.2004 01:34 |
| How many K's can be there | Georgi Tsankov | 1148. Building Towers | 1 апр 2002 17:43 | 1 |
>Each following line (except the last )contains an integer k. The
>last line contains number -1.
so how many lines are there in the input ? |
| I can't help doing it though I'm very busy these days.It quite an splendid mathimatical problem. | Huang Yizheng | 1148. Building Towers | 27 янв 2002 16:42 | 1 |
|
