An incremental week

TopCoder SRM 822 was the first event of the last week (problems, results, top 5 on the left, analysis). The hard problem did not require too many algorithmic insight, but the implementation and tiny details were extremely tricky to get right. As a result, only bqi343 managed to make it work and he won the SRM ahead of four challenge phase masters. Well done!

I was almost there with the hard problem, my solution had the same phases as the one from the official analysis, but I did not manage to even make it work on samples in time.

Codeforces Round 767 followed on Saturday (problems, results, top 5 on the left, analysis). I did not like the long statement of A and I did not immediately see the solution to B, so I've started solving the (relatively) easier problems in a weird order: D1, D2, C, A. When I solved these four, I saw that tourist already had all of them + problem B solved, so it became clear that I needed to go for the harder problems if I wanted to have a shot at the first place. We solved E roughly at the same time which did not change the situation, so I went all in on F, but unfortunately did not manage to finish in time.

At the end of the contest, my solution for F had just one bug: when comparing fractions a/b and c/d, I compared a*d-b*c with zero without taking the signs of b and d into account :( To be fair to tourist, his solution to F also needed just a few more minutes. Congratulations on the win! As he pointed out after the round, I would have probably won the round if he did not participate, since then I would have solved B instead of F.

I want to mention problem E, not because it was particularly exciting, but because I want to share an interesting trick from my solution: you are given a tree with vertices numbered from 1 to n, initially all colored white. The tree edges have weights. You need to process a sequence of queries of three types:

1. Given l and r, color all vertices with numbers between l and r black.
2. Given l and r, color all vertices with numbers between l and r white.
3. Given x, find the largest edge weight in the union of the shortest paths from x to all black vertices.

Both the number of vertices and the number of queries are up to 300000.

In the past few months, I've become a lot more proficient using AtCoder's general lazy segtree algorithm, and prefer using it to rolling a custom lazy segtree implementation for every problem. However, in problems like this one it can be quite challenging to express the lazy propagation as a monoid + a set of mappings. All the more satisfaction when you actually manage to do it :) Can you see the trick? I'll describe my solution in the next summary.

CodeChef January Cook-Off 2022 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). tourist has solved all problems in less than an hour (out of 2.5 hours available) and won in a very convincing fashion. Great job!

In my previous summary, I have mentioned a CodeChef 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).

The first observation is somewhat natural: let's look at the incremental maximums of the original permutation. If their number k is even, then it's easy to find the required split: let's find the (k/2+1)-th incremental maximum, and let the first subsequence consist of all numbers before it, and the second subsequence of this number and all following number. Then each of the subsequences will have exactly k/2 incremental maximums, and those will be exactly the incremental maximums of the original permutation.

We can also notice the following "reverse" observation: each of the incremental maximums of the original permutation will be an incremental maximum of one of the two subsequences. But of course the subsequence may have additional incremental maximums. Let's call the incremental maximums of the original permutation the big ones, and all others the small ones.

Notice that we can always get rid of a small incremental maximum without affecting any other big or small incremental maximums: just move it to the other subsequence (where it will be hidden by the big incremental maximum that was hiding it in the original permutation), together with any additional small incremental maximums that appear when we remove this one.

Therefore if there is a solution to this problem where both subsequences have small incremental maximums, we can keep removing one from each until one of the subsequences has only big ones. So without loss of generality we can only look for solutions where the second subsequence has only big incremental maximums.

In a similar spirit to the above argument, we can also introduce new small incremental maximums by moving them from the other subsequence. Therefore the set of incremental maximums of the first subsequence can be any increasing subsequence of the original permutation.

Therefore the problem has been reduced to the following: does there exist an increasing subsequence of the given permutation such that it contains exactly k-m out of k big maximums, where m is its length?

Now we can assign a weight of 2 to all big maximums, and a weight of 1 to all other numbers, and our question simply becomes: "does there exist an increasing subsequence of weight k?"

Finally, we can notice that we can always decrease the weight of a subsequence by 2 by simply removing some elements, so it's enough to answer the question "what is the maximum weight of an increasing subsequence which has the same parity as k?" And this question can be answered by adapting a O(n*log(n)) algorithm for the longest increasing subsequence.

Notice how we first obtained a working understanding of the solution space here — that we can have any two disjoint incremental subsequences of the original permutation that cover all big maximums as the sequences of incremental maximums of the two parts — and then the actual algorithmic solution was not that hard to see.

Thanks for reading, and check back (hopefully) tomorrow for this week's summary!

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.