nthoang's blog

By nthoang, history, 8 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! Comments (2)
 » 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.
•  » » Thank you, I will try to expand this idea!