nthoang's blog

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

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!

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

4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

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

    Thank you, I will try to expand this idea!