Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### mernazakaria's blog

By mernazakaria, history, 3 months ago, ,

how can i start thinking about problem like this http://codeforces.com/problemset/problem/478/D?

can anyone explain the solution ?

•
• +1
•

 » 3 months ago, # | ← Rev. 2 →   0 Actually, it is pretty obvious that this is solvable by DP. The typical "count number of possibilities under given constraint" is a common class of DP questions.
•  » » 3 months ago, # ^ |   0 thank you so much
 » 3 months ago, # |   0 First observation is that the maximum height h is greatest h satisfying h*(h + 1)/2 <= r + g.let's say total = h*(h + 1)/2, then if you take g green balls and (total — g) red balls, then number of ways of arranging them is same as number of ways of expressing (total — g) as sum of numbers (order doesn't matter) less than h. and the ans is summation of that sum for all g.Here is my code
•  » » 3 months ago, # ^ |   0 thank you so much
•  » » 3 months ago, # ^ |   0 i solved it using dp recursion but it got MLE and i dont understand iterative solution
 » 3 months ago, # | ← Rev. 2 →   0 Wait, this is trivial O(N).
•  » » 3 months ago, # ^ |   0 i dont understand iterative solution of this problem
•  » » 3 months ago, # ^ |   0 Not O(N), it's
•  » » » 3 months ago, # ^ |   0 how ?
•  » » » » 3 months ago, # ^ |   0  for(int j=1;j<=h;++j) for(int i=N;i>=j;--i) dp[i] = (dp[i] + dp[i-j])%num; , and so the time complexity of this nested loop is