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 ...
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[2][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 .
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 .