mernazakaria's blog

D problem
By mernazakaria, history, 6 years 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

Comments Comments (5)
| Write comment?
»
6 years 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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Wait, this is trivial O(N).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not O(N), it's

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        	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

        → Reply