### Polar_'s blog

By Polar_, history, 12 months ago, 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 ... dp, Comments (5)
 » If you come to post just to downvote then please do downvote + help .Please somebody help I really tried hard to get this ;(
•  » » 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[N]. Now fill each level with red and green balls, but beware it doesn't become <0. Link to understandable code.
•  » » » Thank You so much .
 » 12 months ago, # | ← Rev. 3 →   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!
•  » » Thank You so much . I got it now .