Help needed in a DP Problem..

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

Spoiler

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <string>
    #include <string.h>
    #include <vector>
    #include <set>
    #include <map>
    #include <queue>
     
    using namespace std;
     
    #define ll long long
    #define ld long double
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define y0 isdnfviu
    #define y1 asinhiv
    #define fst first
    #define snd second
    #define count sdifnsugh
     
    int s(int n)
    {
    	return (n * (n + 1)) / 2;
    }
     
    const int maxn = 200003, MOD = 1000000007;
     
    int f[maxn];
     
    int main()
    {
    	int r, g;
    	cin >> r >> g;
    	if (r > g)
    		swap(r, g);
    	int n;
    	for (int i = 1; i <= 1000; i++)
    		if (s(i) <= r + g && s(i + 1) > r + g)
    		{
    			n = i;
    			break;
    		}
    	int kol = s(n);
    	f[0] = 1;
    	for (int i = 1; i <= n; i++)
    		for (int j = r; j >= i; j--)
    		{
    			f[j] += f[j-i];
    			if (f[j] >= MOD)
    				f[j] -= MOD;
    		}
    	int ans = 0;
    	for (int i = r; i >= 0; i--)
    		if (i + g >= kol)
    			ans = (ans + f[i]) % MOD;
    	cout << ans << "\n";
    	cin >> n;
    	return 0;
    }

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

Comments (5)

Write comment?

Polar_

5 years ago, # |

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

→ Reply

fanof300iq

5 years ago, # ^ |

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 .

lantrungseo

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

Polar_'s blog