sidchelseafan's blog

By sidchelseafan, 7 years ago, In English

Hello, I was trying the problem HANOI07 a.k.a Building The Tower on SPOJ.

Problem link

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

Code

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks , I will try it.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That doesn't do it , unfortunately. Its still TLE'ing. Code

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I will try and get back to you. Thanks :)

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # |
  Vote: I like it 0 Vote: I do not like it

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