| ENG RUS | Timus Online Judge |
Discussion of Problem 1148. Building TowersandreyDagger`~ Damned solution // Problem 1148. Building Towers 15 Jul 2023 01:29 I used my own hash map with modulo 1e5, and buckets with size equal to one bdzxt Fine [1] // Problem 1148. Building Towers 12 Mar 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. bdzxt Re: Fine // Problem 1148. Building Towers 24 Mar 2017 18:48 Passed again... Good. AIT Is it possible to beat MLE with c#? [2] // Problem 1148. Building Towers 22 Oct 2010 02:52 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? AIT Re: Is it possible to beat MLE with c#? [1] // Problem 1148. Building Towers 22 Oct 2010 03:00 up: i checked the memory usage for 30000 60 10, it's about 300000*4 bytes it4.kp Re: Is it possible to beat MLE with c#? // Problem 1148. Building Towers 18 Dec 2012 02:16 It is possible :) QQQQ Please, write correct answer for test [2] // Problem 1148. Building Towers 7 Jun 2006 20:20 2369 60 10 1 19 37507396740 37507396740376 65476805623000 -1 or some else test with big numbers and n < h*(h+m+m-1)/2 Burunduk1 Re: Please, write correct answer for test [1] // Problem 1148. Building Towers 7 Jun 2006 22:49 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 MichaTel Re: Please, write correct answer for test // Problem 1148. Building Towers 22 May 2012 13:07 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 AutumnSky C# crash // Problem 1148. Building Towers 28 Apr 2012 03:41 No needed now. Edited by author 06.06.2012 15:50 IGOR_Lviv NU no subject // Problem 1148. Building Towers 16 Oct 2009 02:58 Edited by author 16.10.2009 05:03 bobchennan Who can help me? // Problem 1148. Building Towers 10 Jul 2009 15:35 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! ftc How to solve this problem? [1] // Problem 1148. Building Towers 23 Jan 2007 13:39 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? svr Re: How to solve this problem? // Problem 1148. Building Towers 15 Dec 2008 19:00 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 =( // Problem 1148. Building Towers 28 Sep 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? =) Denis Koshman Minor fix [2] // Problem 1148. Building Towers 28 Aug 2008 16:19 It's not clear from problem statement that towers are numbered in lexicographical order of their records. Denis Koshman Re: Minor fix [1] // Problem 1148. Building Towers 9 Sep 2008 03:13 "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 :) Vladimir Yakovlev (USU) Problem statement has been rewritten // Problem 1148. Building Towers 13 Sep 2008 21:48 DWED Java MLE [1] // Problem 1148. Building Towers 13 Aug 2008 16:36 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). DWED Re: Java MLE // Problem 1148. Building Towers 15 Aug 2008 03:07 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. Vladimir Yakovlev (USU) Problem 1148 "Building Towers" has been rejudged (+) // Problem 1148. Building Towers 24 Oct 2006 19:22 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 Burunduk1 How to solve it fast? [3] // Problem 1148. Building Towers 14 Mar 2006 22:26 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. Grebnov Ilya[Ivanovo SPU] Re: How to solve it fast? [1] // Problem 1148. Building Towers 15 Mar 2006 02:03 Mail me to Ilya[dot]Grebnov[at]mail[dot]ru Burunduk1 Thank you for your answers // Problem 1148. Building Towers 15 Mar 2006 15:22 :) Kit Re: How to solve it fast? // Problem 1148. Building Towers 15 Mar 2006 10:29 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. Yu Yuanming The memory limit make it a really good problem:) [1] // Problem 1148. Building Towers 28 Dec 2005 14:53 Grebnov Ilya[Ivanovo SPU] Use hashing for some levels of tower. I used for every odd level. // Problem 1148. Building Towers 28 Dec 2005 19:45 Hurricane_NET This problem is a bit complicated.... // Problem 1148. Building Towers 4 Dec 2005 16:17 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! Maigo Akisame (maigoakisame@yahoo.com.cn) Why should my program get Fail(Compilation)? [1] // Problem 1148. Building Towers 3 Aug 2005 18:27 It just stay compiling for a long time, then Fail appears! Hurricane_NET Re: Why should my program get Fail(Compilation)? // Problem 1148. Building Towers 3 Aug 2005 20:42 service unavailable at the very moment？I dunno ChenShi @ZSU Who can help me ? [4] // Problem 1148. Building Towers 19 Apr 2004 06:32 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. Grebnov Ilya[ISPU] Re: Who can help me ? [3] // Problem 1148. Building Towers 21 Apr 2004 00:13 The answer is correct. I also got WA when use Extended type, but got AC when change it to Int64. ChenShi @ZSU Re: Who can help me ? [2] // Problem 1148. Building Towers 22 Apr 2004 06:14 Thank you very much. What's the C++ compiler here ? Vladimir Yakovlev (USU) Use __int64 type and "%I64d" specifier to read/write it. [1] // Problem 1148. Building Towers 22 Apr 2004 18:14 ChenShi @ZSU Re: Use __int64 type and "%I64d" specifier to read/write it. // Problem 1148. Building Towers 28 Apr 2004 09:45 Thank you! AC now :) shitty.Mishka Could anybody tell my why does my program get ML?(+) [2] // Problem 1148. Building Towers 4 Feb 2002 15:07 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 <P><P><P> Re: Could anybody tell my why does my program get ML?(+) // Problem 1148. Building Towers 6 Feb 2002 01:43 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?..) Benone Sinulescu aka Benny Re: Could anybody tell my why does my program get ML?(+) // Problem 1148. Building Towers 15 Aug 2002 01:54 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 Georgi Tsankov How many K's can be there // Problem 1148. Building Towers 1 Apr 2002 17:43 >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 ? Huang Yizheng I can't help doing it though I'm very busy these days.It quite an splendid mathimatical problem. // Problem 1148. Building Towers 27 Jan 2002 16:42
|