senshi2504's blog

By senshi2504, history, 4 years ago, In English

http://acm.timus.ru/problem.aspx?space=1&num=1017

I have been trying this problem for a while . I have figured out the state to be dp[taken][remaining] where taken tells me the number of blocks i have used till now , and remaining tells me the number of blocks that are left with me . Now base case is trivial , but I am not able to get the transition . Can someone please help me with this . Any help is appreciated :)

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

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

f(taken, remaining) is slightly hard ....

But you're on the right track. The second dimension needs to be something else.

It should be the maximum height of the last tower. We need this information in constructing the second last tower. For example, if we have 7 bricks and we used 3 on last tower, we need to know that we are only allowed maximum height 2.

Here is the recurrence —

f(i, j) represents the number of staircases with i bricks, last tower height at most j.

Then, we have two choices — either we have a tower of height j or we do not.

f(i, j) = f(i — j, j — 1) + f(i, j — 1)

The answer is f(n, n — 1) because we need at least two stairs.

Also, if j >= i, then f(i, j) = f(i, i — 1)

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

Here's some code for your reference. You can follow me on GitHub if you like.

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    Quiet don't understand meaning of initial states. Of course, they are fictive and I see how right answer is got. The same with such auxiliary states like f(n, n). Logically it must equal f(n, n — 1), but we add f(0, n — 1). What is the meaning?

    Sorry for necroposting,

    UPD: All the time I thought about 2-stair staircases. Now it is clear. Sorry for disturbing.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Observe that the answer for a particular state depends on the number of bricks taken and the number of bricks used in the preceding step. Let's have a look at why this is so:

Let's say that we have taken 5 bricks up to a certain point and arranged them in the following 2 configurations:

           _
  _        _
_ _        _
_ _      _ _

Let's say that we had 9 blocks initially.

For the first staircase, we have taken 5 blocks and have 4 blocks to build the remaining part of the staircase. But, the height of the next step we must build is 4. So we can still complete the staircase.

For the second staircase, we have also taken 5 blocks and have 4 blocks to build the remaining part of the staircase. But this time, the height of the next step we must build is 5. So we cannot complete the staircase.

Hence, we must define our dp state as f(t,p) where t is the number of blocks taken so far and p is the number of blocks used the preceding step.

How to transition between states? At each state, assuming that p+1 <= n-t, we have a choice of using p+1 to n-t blocks for the next step. So we need to use the following transition:

for i from p+1 to n-t
do
  f(t,p) += f(t+i,i)
done

Time-complexity of solution: O(n^3)

Of course, don't forget to memoize your solution since it is a DP problem.

If you get stuck, I have written a sample solution here.