mernazakaria's blog

By mernazakaria, history, 4 weeks ago, In English,

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

can anyone explain the solution ?

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Wait, this is trivial O(N).