Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### nthoang's blog

By nthoang, history, 12 months ago, ,

Hi Codeforces,

Recently I am solving this problem from AtCoder Regular Contest 061: https://atcoder.jp/contests/arc061/tasks/arc061_d

However, I do not come up with any idea. I have tried to look at others' submissions since this contest does not have an English editorial, but I still cannot figure out what the mathematical formulas written in those codes mean.

Hope you guys can help me with the solution for this problem. Many thanks!

• +15

 » 12 months ago, # |   +5 Every scenario can be represented by a string with N + M + K characters 'a', 'b' and 'c'. We should append one extra 'a' at the beginning (because Alice starts) and say that we want the N-th occurrence of 'a' to be earlier than the M-th and K-th occurrence of 'b' and 'c'.To get a quadratic solution, we can iterate over B and C — the number of occurrences of 'b' and the number of occurrences of 'c' before the N-th occurrence of 'a'. Then use some binomials to get the answer.To make it faster, I think we should iterate over the sum B + C. Then some sum of binomial coefficients should be added to the answer, and maybe it's possible to compute it fast.
•  » » 12 months ago, # ^ |   0 Thank you, I will try to expand this idea!