1.During contest, 2. In practice mode, and 3.after reading editorial. Sometimes, when I can't prove the correctness of the approach of the editorial(because the editorial says "the proof is obvious", and skips the proof entirely), and there aren't any proofs in comments section too. I can't decide how much time should be spent thinking about the proof. I think and think until and unless I am able to prove it. Is this the right thing to do, even if it takes a few days sometimes?

During contest
I try to disprove my approach with test cases instead of looking for mathematical proof.

During practice
I try to think of a proper proof, then try to disprove the proof with test cases.

Editorial I try to think of a proper proof, then try to disprove the proof with test cases.

The editorial and problem setter's code is not clear to me. Can someone explain the code. I don't understand how he reduced O( n^2 ) to just O( n ) . Please explain this to me .

Thanks!

You have N balls, out of which r1 are of one color, r2 are of another color, r3 are of another color....and so on. There are C colors of balls in total. Balls of same color are identical . You have to choose K balls out of these N balls. What is the best complexity in which this can be done ( not including complexity of precomputation ), and how can we do this?

http://codeforces.me/problemset/problem/543/D

I did not understand the editorial so I wrote a solution of my own. But I don't understand the tricky cases where it fails. Here is my submission ID 11679268 . My logic is simple:

1. Do DFS with "1" as root , store results in dp[i]

2. result[1]=dp[1]

3. result[i]=(1 + result[parent_of_i]/(dp[i]+1)) * dp[i] % mod;

Where is the logic wrong? I couldn't figure it out.