up: i checked the memory usage for 30000 60 10, it's about 300000*4 bytes

"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 :)

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.

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

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

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.

service unavailable at the very moment？I dunno

The answer is correct. I also got WA when use Extended type, but got AC when change it to Int64.

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

[deleted by moderator]

Edited by moderator 11.04.2004 01:31

>