A thesis week

Atto Round 1, also known as Codeforces Round 1041, was the main event of the week (problems, results, top 5 on the left, analysis). With problem H turning out way easier than the problemsetters have expected, the top places were decided on problem G concerning permutations and their compositions, which for me was just very hard to load into RAM to even think about it :) At the end of the contest I came up with a randomized solution that takes 15 random permutations and asks all their cyclic shifts. It actually passed G1 in upsolving, but during the round I did not manage to find all off-by-one and permutation-instead-of-inverse bugs. But even in upsolving it seemed hopeless for G2 where we only get to take 10 such permutations.

It turns out that Kevin has won the round with exactly the same solution. To pass G2, he tried 1000 different random sets of 10 permutations before starting to ask questions, and chose the set that gives the least collisions. This turned out to be borderline good enough, and 4 submissions that differed only in the random seed (diff on the right) sealed the deal. Well done Kevin, and also well done Jiangly on solving G2 in the "on paper" way :)

I got my share of successful randomized solving in problem H, where after being stuck for a while I decided to submit a solution that took edges that can definitely be taken, and when there is no such edge, took a more or less random edge and continued, and then repeated this process until the time runs out. This should be roughly the same as backtracking but even simpler to implement, and I expected that with n=30 it has a high change of passing, and indeed it did from the first attempt in which I fixed all bugs.

It is curious that neither problemsetters nor myself were able to see:

1) the relatively standard dynamic programming solution for the problem that takes advantage of the fact that from every subtree of the DFS tree we have at most 5 backward edges, and therefore can just add the state of all those edges to the dynamic programming state.

2) the non-bipartite matching solution that does not even rely on the additional "at most 5" property from the problem statement: the problem statement essentially asks for maximum matching, but where each vertex can be used twice instead of once, so we can just duplicate the vertices and be done.

Point 2 is even more bizarre in my case, since my masters thesis 18 years ago was on a more general version of exactly this problem, 2-path-packings. The thesis was in Russian and I don't think it is published anywhere, but it is roughly equivalent to chapter 3 "O(mn)-time algorithm" in this paper. So the matching interpretation should really have been obvious to me, even after 18 years :)

Thanks for reading, and check back next week!