### sidchelseafan's blog

By sidchelseafan, 7 years ago,

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.

Code

• 0

 » 7 years ago, # |   0 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
•  » » 7 years ago, # ^ |   0 Thanks , I will try it.
•  » » 7 years ago, # ^ |   0 That doesn't do it , unfortunately. Its still TLE'ing. Code
•  » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ |   0 I will try and get back to you. Thanks :)
•  » » » » » 7 years ago, # ^ |   0 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 :(
 » 7 years ago, # |   0 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 onceHere is my code : link