Polar_'s blog

By Polar_, history, 5 years ago, In English

Today I was trying to solve this problem . But I couldn't solve it . So I tried to understand some solution but still ;( .

Spoiler

I saw this code but couldn't understand . Can anybody help me getting this solution or can you please tell me how to solve this problem .
Thanks ...

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

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

If you come to post just to downvote then please do downvote + help .
Please somebody help I really tried hard to get this ;(

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Think of problem recursively. First find the max height that you can get using r red and g greens, you can use binary search for it.

    Now suppose you are at i_th level, you can fill this level either with red balls or green balls. suppose you say level 1 = top of tower, level 2 as 2nd top and so on. so when you are at i_th level you know how much ball you need to fill in this level, that is i.

    Now when we are at level i we can fill it with either red balls or green balls, we check recursively for each case and recur for next one. the problem is a simple knapsack problem but the problem is it will give you Memory limit exceeded.

    To avoid MLE, you have to solve it iteratively. observe that current ith level depend on i-1 th level.

    so convert the above recusive approach to iterative one of state dp[2][N]. Now fill each level with red and green balls, but beware it doesn't become <0.

    Link to understandable code.

»
5 years ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

Ok it's quite simple.

First step: Determine $$$h$$$. You can derive $$$h$$$ from the following inequality $$$ \frac{h\times (h+1)}{2} \le r+g$$$. You can see that $$$h \le \sqrt{2\times(r+ g)}$$$, so you can bruteforce $$$h$$$.

Second step: Now you see the problem mimics the traditional DP problem: You have $$$h$$$ sacks, the sack $$$i$$$ contains $$$i$$$ blocks, so how many ways can you form $$$X (X\le r)$$$ red blocks using $$$h$$$ sacks.

You can solve like this: $$$f_{X, i}$$$ is the number of way to form $$$X$$$ red blcoks using sacks from $$$1 \rightarrow i$$$. Then $$$f_{X, i} = f_{X-i, i-1} + f_{X, i-1}$$$.

The overall complexity of both time and memory is $$$(r+g)\sqrt{r+g}$$$. Actually the solution code is the optimization of DP, but you can ignore it.

Hope this helps!