A Stirling week

There were no contests that I'd like to mention this week, but this offers a good chance to look back at the first full week of 2022 :) The new competitive programming year started with Hello 2022 on Codeforces (problems, results, top 5 on the left, analysis). The new year started in just the same way it ended: with a victory for tourist, who has been in amazing form recently. Congratulations!

My round was unfortunately ruined by getting bogged in minor details of the problems. I've started by forgetting to reset the segment tree back to the initial state after processing each group in problem E, but that was still a relatively minor setback. The next problem F was nastier, and I spent quite a lot of time and energy to deal with the first and last groups of zeros properly. Finally, in problem G I just could not untangle myself in time, and my bug turned out to be simply forgetting to ignore smaller numbers to the right of a right-maximum when processing it.

TopCoder SRM 821 on Saturday started the race to qualify for the TCO22 regional events (problems, results, top 5 on the left, analysis). tourist has continued his impressive run of form by becoming the first person ever to win 5 SRMs in a row, also achieving a ridiculous rating of 4034 in the process. Very impressive!

The round featured a 250-pointer that required a math olympiad-style solution. Sure, after knowing that such solution is expected finding it is not so hard, but I somehow tried to think more algorithmically and failed. Having seen that others are submitting the problem for very high scores, I've assumed that the greedy works and submitted it, which at the very least allowed me to get unstuck and move on to the other two problems. Having submitted them, I've implemented a stress-test for the 250 and quickly learned that the greedy does not in fact work, but still could not come up with a working solution, hence no resubmit. Therefore I guess I was lucky to believe in the greedy, as otherwise I wouldn't have had enough time left for the two remaining problems even had I figured the trick out.

I've managed to make up the points I knew I was going to lose by challenging others who submitted greedy and similar solutions for this problem, but even +450 challenge points were not enough as tourist has found +425 for himself. Nevertheless, I enjoyed the excitement of the challenge phase, and the need to make tradeoffs between confidence that your challenge might work with the need to find many challenges in 15 minutes. Props to the TopCoder format for making such exciting rounds possible!

Finally, CodeChef SnackDown 2021 Final Round on Sunday wrapped up the contests of the previous year (problems, results, top 5 on the left, analysis). It was the first online edition of SnackDown, and the first one without the two-person team format (even though the organizers mentioned that they're planning to come back to the team format when the pandemic allows). Mingyang Deng has made steady progress while others stumbled, and therefore had a much better penalty on 6 problems and got the first prize. Well done!

My round went wrong when I quickly reduced the permutation problem to finding the Stirling numbers of the second kind S(n, k) for all k from 1 to a, but then spent at least an hour, and probably more, trying to figure out how to actually do that, including opening a physical copy of Concrete Mathematics searching for some identities that would help me :) However, this was a moment where no magical trick was needed, and one just needed to apply the technique that I described in my blog 5 years ago. I guess my statement back then was wrong: "However, C(n, k) seems to be the only practically relevant function with this property".

This huge delay has set the stage for my last-hour comeback, as I managed first to deal with the quite tricky problem where one needs to take advantage of the fact that some probabilities are too low to significantly reduce the number of dynamic programming states, then to solve the problem about incremental maximums, and then finally see the FFT trick with about 5 minutes remaining, managing to finish coding and submit my solution with about 5 seconds left on the contest clock, after it failed to compile locally, and it passed!

The compilation issues were due to the fact I'm currently using Visual Studio as the backend for CLion, which provides for much faster compilation, but unfortunately lacks int128 support. I had int128 used in my library to apply CRT when doing FFT on three prime moduli, back from the times I used gcc and clang. JHelper's inlining only works on file level, therefore this version of FFT was being included even though it was not actually used.

Here is the incremental maximums problem: you are given a permutation of length 200000, and need to tell if it's possible to split it into two disjoint subsequences in such a way that both parts have the same number of incremental maximums (numbers that are bigger than all previous numbers in the part).

This is one of those problems that look quite ugly after reading the statement, but as you work towards the solution you develop a good understanding of the problem structure, and the solution is therefore quite rewarding when you see it in the end. So I encourage you to take a crack at it, even though of course it is very hard.

This problem has appeared before, but I somehow did not remember it at all even though I solved the relevant round. I guess I focused on other problems then, did not do much upsolving, and did not find it interesting enough for the blog. Well, at least that allowed me to enjoy solving it this time!

Thanks for reading, and check back next week.