A pen testing week

Codeforces Round 647 was the first contest of the first week of June (problems, results, top 5 on the left, analysis). This round seemed to have a bit more "Failed System Test" outcomes than a typical Codeforces round (instructive example), and yet tourist, Um_nik and boboniu did not make mistakes and solved all problems correctly (to be more precise, both tourist and Um_nik resubmitted one of the problems, so they have managed to correct the mistakes they made). Congratulations to all and especially to tourist on the win!

Google Code Jam 2020 Round 3 selected the 25 finalists, who unfortunately will not travel to Munich, and will instead compete in the online finals (problems, results, top 5 on the left). Besides the significantly easier first problem that was solved by everyone in top 25, the contestants found a lot of different ways to qualify using the other three problems. Gennady.Korotkevich solved all inputs but one and won, continuing his exceptional GCJ form.

I have helped prepare the third problem, Pen Testing, that was created by Ian Tullis and which I find quite amazing: you have 15 ballpoint pens having 0, 1, 2, ..., 14 units of ink in them. The pens are given to you in random order and you don't know which pen is which. The only way for you to get information about the pens is to write something with them. In one turn, you pick one pen and try to spend one unit from ink from it, and you get one bit of information doing that: if the pen had at least one unit of ink left before this turn, you succeed in writing with it, and it now has one unit less (possibly 0). If the pen was empty, then you fail in writing with it, and you know that it's definitely empty. You goal is to eventually choose two pens that have at least 15 units of ink remaining in total.

Just choosing two pens at random without any writing gives you a 46.(6)% probability of success, and writing seemingly makes things even worse as it reduces the amount of remaining ink, and you only learn the concrete identity of a pen after it has no ink left :) And yet the problem asks you to succeed in 63.6% of all cases. How is it even possible?

I have written an extensive analysis for it that you can read by clicking "Analysis" after following the above link. I don't have much to add to it :)

AtCoder Grand Contest 045 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). Nobody could solve problem E, and only apiad has solved problem F, but he did not have enough time left afterwards for the easier problems and finished in 12th place. Solving the first four problems fast was the way to victory this time, and that's exactly what ksun48 did. Congratulations!

I have made most of the steps described in the analysis for problem D, but not all of them. So I have obtained the following recurrence:

for (int n = 1; n <= N; ++n) {
  for (int a = 1; a <= A && a <= n; ++a) {
    if (a == n) {
      w0[n][a] = fact[n];
      w1[n][a] = fact[n];
    } else {
      w0[n][a] = ((n - a) * (int64) w1[n - 1][a] + (a - 1) * (int64) w1[n - 1][a - 1]) % MODULO;
      w1[n][a] = (w0[n - 1][a - 1] + w0[n][a]) % MODULO;
    }
  }
}

where w0[N][A] would contain the final answer. This solution runs in O(N*A), which is too slow since N<=10⁷ and A<=5000. Can you guess how I got this problem accepted (you don't need to read the problem statement :P)?

Thanks for reading, and check back for more!