Z-Climber

Can somebody please give me some hint for this tasks. I was trying to solve it form 00-00 to 05-30 using combinatorics and i didn't find decent solution that will work for all test cases. :(

Al3kSaNdaR.

My idea was that i should put sol to be Sol = 3 ^ n and then add 2 * 2 * ( n - k ) but i was wrong. :-(

It's obvious that you coud use dynamic programing. Represent your state with coordinates of the current position: x - level and y - current position.

At the begining, you have dp[0][k] = 1, every else field in dp[0] = 0.

From x = 1 to n you do the following:
for every y from 0 to 2*k+1 you apply this:

dp[x][y] += dp[x-1][y-1] + dp[x-1][y] + dp[x-1][y+1]

That's it. Only thing to wory about is overflow. Only first 25 test cases worked with standard types, for full points you had to implement big numbers.

There are still few optimisations one could apply, but... I don't feel like writing now. ;)

Hope my post helped.

Hm, thank you very much. I have to learn dynamic programming ASAP. ;)

The only one optimization is to go to k and not to 2*k+1, here is the reason:
0 0 1 0 0
0 1 1 1 0
1 2 3 2 1
3 5 7 5 3

On this table you can notice that the table halfs are the same....

Hm... That's now the only one. There's also memory optimization. You can observe closely that you use only current and previos row in dp matrix. So there's no need for matrix size of N*(2*k+1) but only 2*(2k+1) without that optimization you mentioned, and only 2*(k+1) with it. So you, basically, need only two DP arrays - one for current row and one for previous. And your loop than goes from 0 to k.

Very neat task, if you ask me... ;)

Nice idea about memory optimization.... ;)

I've figured about the two halves , but is that optimization enough?

@iggy91
i only kept dp[k] where k equals the width , you can remember only one integer that you need , dp[y-1]

tmp=dp[y];
dp[y]=dp[y]+prev+dp[y+1];
prev=tmp;

well...concerning that memory optimization, you're sacrificing time there, but what the heck :D
You needed no optimizations whatsoever to get 100...

Well my solution passed all test by making a bignum struct with char, combined with the optimization above ( two halfs ), and a matrix
BigNum DP[201][201];

@msantl
Very clever, indeed... ;)

I have problem with TLE .
Which optimisation I don't use?

Hm... I haven't practiced working with bignums this way untill now, but... try changing the base in your bignum structure from 10 to some larger int, say 1000000. So one "slot" in your bignum will not hold ony one digit, but a couple of them. Calculations are then decreased and running time is reduced drastically (in my case, at least).

I'm currently trying to figure out where I made a mistake in bugnum addition...

P.S. My solution during contest time got TLE on same test cases as yours, and I submited bignum edition with base = 10, as you did...

@turgond
And why did you say you're sacrificing time when using memory optimization?

I think there is no need to make memory optimization: 1 char = 1 byte, lets assume that every number in DP[201][101] has 30 digits. So the memory usage is
((201*101*30)/1024) = 594.75 KB. Don't know if this is calculation is right.. xD

That's because of constrains in this task, but would you do if they were more cruel? msantl made possible to have memory and time complexity O(n), thus allowing limits to be as high as 10^9 and it would still run under given time limit of .5 seconds...

In this instance there is no need for optimisations if bugnums were implemented in best way, turgond said that.

moze li pliz netko pogledat moj kod, kad maknem bignum prodje prvih ~14, a s bignumom prodju prva dva i 48.

http://www.z-trening.com/new/www/html/submit.php?submit=7100018129&subm_code=1

I think that you should do
int m = max( max( b.n, c.n ), d.n );
n=m;
, or you did someting wrong with the ost.

it shouldn't be that, trim increases n if it should...

and I tried now, and it isn't that ...

translation for my pre previous post, sry for posting it in croatia:

can somebody look at my code, when I remove bignum, first ~14 test cases pass, and when I put bignum, only first 2 and 48. test cases pass ...

http://www.z-trening.com/new/www/html/submit.php?submit=7100018129&subm_code=1

*croatian

anyone? :)