An unwrapping week

TopCoder SRM 813 took place last Friday (problems, results, top 5 on the left). With this victory tourist has guaranteed himself the TCO qualification spot, so that he does not have to wake up for the last SRM which takes place in the middle of the night — well done! I have grossly overestimated the chances of other solutions being broken, so my challenges for solutuons that did not "look right" brought me -75 points, and that despite one of the challenges being successful :)

The second stage of the new Open Cup season, the Grand Prix of IMO, took place on Sunday (results, top 5 on the left, analysis). Team USA1 continued their streak with the 21st top-3 finish in a row, spanning from the end of the 2019-20 season, but they could not get their fifth victory in a row since team ext71 was 5 penalty minutes faster after getting their 12th problem dramatically at 4:58 from +3. Congratulations to both teams!

I've had some fun digging through the constructive problem K: you are given a positive integer k up to 10⁶, and need to produce any set of at most 30 integers with absolute values not exceeding 10¹⁶ such that the number of its subsets with zero sum, including the empty subset, is exactly k. I doubt it's possible to solve this problem completely in one's head or on paper, so if you're interested, I encourage you to try some idea out with a computer :)

Finaly, CodeChef September Cook-Off wrapped up the week (problems, results, top 5 on the left, analysis). The two last problems were a lot more difficult than the rest, and only gennady.korotkevich was able to solve them both. Great job!

In my previous summary, I have mentioned a VK Cup problem: you have a tape that is infinite in both directions and is split into cells. You're going to write a given random permutation of size n<=15000 onto this tape in the following manner: you write the first number somewhere, then you either stay in the same cell or move one cell to the left or to the right, then write the second number there, then again either stay or move to an adjacent cell, write the third number there, and so on. Whenever you write a number into a cell that already has a number, the old number is overwritten and therefore discarded. After all n numbers have been written, we look at the resulting sequence written on the tape from left to right. What is the maximum possible size of an increasing subsequence of this sequence? Note that the given permutation is guaranteed to have been picked uniformly at random from all permutations of size n.

The first idea is relatively standard for problems of this type: overwriting is hard to deal with, so let us look at the process from the end. Then instead of overwriting we will just skip writing numbers to cells that already have a number, and therefore we will always have a segment of cells that have numbers that will not change anymore, and the rest of the cells free.

The second thing to get out of the way is the "increasing subsequence" complication. In the new setup where we go from the end, it's clear that there's no point at all writing numbers that will not end up in that increasing subsequence, as we can simply stay in the current position and skip writing the unnecessary number instead of moving left/right to write it. The only exception to this is the very first number we write (in reverse order, so the last number of the input permutation) which will always be written even if it's useless for the increasing subsequence. We can deal with this peculiar property of the last number separately, so for the remainder of this post I will forget about it for simplicity.

Now all numbers we write must form an increasing sequence. The property "increasing" is local, so all subsequent numbers will only be compared with the first or the last number written so far, which leads us to a dynamic programming solution. Having processed some prefix of the reversed permutation, only four things matter:

1. what is the first number of the sequence we have so far
2. what is the last number of the sequence we have so far
3. what is the length of the sequence we have so far
4. where in this sequence are we

However, these four things plus the length of the prefix we have processed lead to O(n⁵) states, so while polynomial, this solution does not really cut it for n<=15000. So we need a few tricks to reduce the state space.

The first trick is to notice that since the permutation is random, the length of the sequence will be O(n^0.5) instead of O(n) (more info). Therefore our position inside the sequence also has just O(n^0.5) options, so we have reduced the number of states to O(n⁴) just by staring at the solution for a bit and without changing it :)

The next relatively standard trick is to notice that we don't need the first two dimensions in such detail. Instead, we can store the smallest last number for each combination of (first number, length, our position), which brings us down to O(n³) states. Symmetrically, we could have also stored the biggest first number for each combination of (last number, length, our position).

Here comes another optimization: if we only consider states right after we have written a new number, as opposed to at all moments, then three dimensions of our dynamic programming collapse into one! For example, if we have just written a new first number, then "where in the sequence are we" has just one option — at that first number. Moreover, the prefix of the reversed permutation that we have processed is also fixed — it's the prefix up to that first number. This optimization without the previous optimization would have brought the number of states down to O(n^2.5).

Can we apply both optimizations together? This is what I could not figure out during the contest, but in retrospect it's quite straightforward: yes, we can! The key thing to notice is that we can't apply just "smallest last number" or just "biggest first number" optimizations by themselves. We must use both: if we have just written a new first number, then we need to store the smallest last number for this (first number, length) pair, and if we have just written a new last number, then we need to store the biggest first number for this (last number, length) pair! This brings the number of states down to just O(n^1.5), finally something manageable for n<=15000.

However, having reduced the number of states we have increased the number of transitions: instead of just considering what to do with the next number for a transition, we have to iterate over which will be the next number to be written, leading to O(n) transitions for each state and O(n^2.5) running time.

However, we can use yet another relatively standard trick: instead of naively doing all transitions, we can use a segment tree that stores all "pending" transitions, and be able to find the dynamic programming value for a new state in O(log(n)), solving our problem in O(n^1.5log(n)), which is fast enough. I hope you enjoyed this long process of unwrapping the present as much as I did :)

Thanks for reading, and check back for this week's summary!