Hello, I was trying the problem HANOI07 a.k.a Building The Tower on SPOJ.
So, I realized it is a DP problem. And hence began forming the recurrence. Condensing the problem statement you have n blocks, you need to make a tower of height h such that the bottom most level has m blocks and on each level, number of blocks should be one greater or one lesser than the previous level.
If you have n=7,h=3,m=2 then allowed tower is 2-1-2 and 2-3-2. Constraints are n<=32767,h<=60,m<=10.
My recurrence consists of three states such that f(n,h,m) = f(n-m,h-1,m+1) + f(n-m,h-1,m+1), where f(i,j,k) indicates number of ways you can form a tower consisting of n blocks , of height h and no. of top level blocks being m.
I wrote a top-down and bottom up approach the complexity being O(N*H*M), after some observation You can reduce N by a huge factor (not relevant to the current discussion, i suppose). I did that too.
But I still get TLE, I would submit my links. Could someone please help me with this. Thanks :).
Don't recompute the dp for each test case , only compute it once at the beginning for each value of m then then use it to answer the test cases
Thanks , I will try it.
That doesn't do it , unfortunately. Its still TLE'ing. Code
Your doing 3 4-nested loops inside solve1() the first one for initializing is not important because Arrays are already initialized to 0 when they are global so just delete it.
for the last 2 try mixing them into one 4-nested loops.
also your code is not giving correct answer on my computer please check that too.
I will try and get back to you. Thanks :)
I tried a single four-nested loop code, it still doesn't pass ? What do i do ? I deliberately submitted a wrong single 4-nested loop code to check if it passes TL , it didn't :(
I tried the same thing and it got ac for me I reduced the size of the n to around 2500, lvl to 60 as stated in problem and m to 80 I build table only once
Here is my code : link