Блог пользователя Polar_

Автор Polar_, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

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!