A leafy week

This week featured two weekend contests. First, TopCoder SRM 729 took place on Saturday (problems, results, top 5 on the left, my screencast with commentary). If you sum up the problem columns in the screenshot on the left, you can notice that the sum doesn't match the score column, and that's because the match presented ample opportunities for challenging. You can see on the screencast as I try to prepare an uber-challenge-case for the 450 during the intermission, and spent the beginning of the challenge phase getting it to work, while many solutions were already being challenged. uwi has made the best use of the challenge opportunities and thus claimed the first place. Well done!

Most of the challenge opportunities presented themselves in the medium problem, which looked very standard at first glance. You are given a 1000x1000 grid. In one jump, you can move from a cell to any other cell that's at least the given distance d away — you can't jump very close. What is the smallest number of jumps required to get from one given cell to another given cell?

We could use a standard breadth-first search to solve this problem, but we have 1 million cells and potentially 1 million jumps from each cell, so the total running time would be on the order of 10¹² which is too slow. Can you see at least one way to speed this solution up? (there are many!)

The other weekend contest was the Open Cup 2017-18 Grand Prix of Khamovniki (results, top 5 on the left). Unlike the previous round, the active ICPC teams from Russia were not at the top of the standings, with only two ICPC teams from Asia and a veteran team Past Glory able to solve 10 problems — congratulations, and especially to Seoul National U 2 team for another Open Cup victory!

Problem D "Lunch Queue" was from the rare species of data structure problems that I enjoyed solving. n people are coming to lunch and forming a queue. The people are split into disjoint groups. When i-th person comes to the lunch, if there's nobody from their group c_i already in the queue, they stand at the back of the queue. When there is somebody from their group already in the queue, they can also stand next to any such person (directly before or after), but only if they would be cutting in front of at most a_i people by doing so. If they have multiple positions where they can join the queue according to the above restrictions, they always pick the front-most one. Initially the queue is empty. Given the values of c_i and a_i in the order the people come to lunch, how will the final queue look like?

In my previous summary, I have mentioned a hard AtCoder problem: you are given a rooted tree with n vertices, and each vertex contains an integer between 1 and n, each number appearing exactly once. Your goal is to rearrange the numbers in such a way that vertex 1 has number 1, vertex 2 has number 2, and so on. You're allowed to do the following transformation: take the path connecting the root of the tree with any vertex v, and cyclically rotate it, placing the number that was in root into v, the number that was in v into the parent of v, and so on — essentially a generalization of insertion sort from a single path to an arbitrary tree. You need to sort the tree in at most 25000 operations for n=2000.

I did not solve the problem myself, so I will describe the solution from the official analysis. First, we can notice that given any leaf, we can put the correct value into it in <=n operations (first pull it up to the root, then put it into the leaf in one rotation, and then never touch this leaf again, so we could sort everything in n² operations, which is too much.

However, we can notice that in this approach we have quite a lot of freedom for choosing the moves that pull the given number up. We could try to use this freedom to try to pull up the numbers for all leaves, not just for one leaf. But even that would not be enough, as when our rooted tree is a chain it only has one leaf. However, we know that for a chain a simple solution is possible, called the normal insertion sort: we'll do exactly n operations, and after k operations we'd have k bottom numbers of the chain already sorted in correct order, in each turn inserting the new number to the appropriate place.

Now we need to combine the ideas of pulling the required number from anywhere in the tree with the idea of filling a chain in one O(n) operation stage in such a way that the number of stages would be O(log(n)) for any rooted tree. More precisely, we will find all leaf chains in the tree — chains that hang at the bottom with nothing else attached to them, and fill them all with correct values in one stage. This guarantees O(log(n)) stages since the number of leaves is divided by at least two after each stage.

Whenever the root of the tree has a useful value — one that must be in one of the leaf chains — we will send it there, inserting it into the correct place relative to other values that we've sent to the same leaf chain, just like the insertion sort approach above. And when the root has a useless value, we need to send it somewhere, so let's send it to any position which contains a useful number, but such that all its subtree contains either only useless numbers, or useful numbers that are already placed into the corresponding leaf chain (in other words, the numbers that we don't need to get to the root anymore). This will push this useful number towards the root, and create a subtree that doesn't have any numbers that we want to get to the root.

Why does this cycle finish eventually, and more importantly why does it run in O(n) operations? Each useful value passes through the root only once. A useless value, after passing through the root, ends up being in a dormant subtree, and would never pass through the root again, unless we need to touch this subtree because we're putting a useful value into it. In each such operation, at most one value moves from a dormant subtree back into circulation, and thus can reach the root again. So the total number of times a useless value that we've already seen once returns to the root does not exceed the total number of times we put a useful value into its place, meaning that the total number of operations for one stage is at most n plus total size of leaf paths, so O(n).

Thanks for reading, and check back next week!