A Red Panda week

Last week started with Codeforces Round 459 on Monday (problems, results, top 5 on the left, analysis). Once again the hardest problem was too much to handle, and OO0OOO00O0OOO0O00OOO0OO was quite a lot faster on the first four. Congratulations on the win!

On Saturday, AtCoder hosted an unusually long 5-hour contest called AtCoder Petrozavodsk Contest 001 (problems, results, top 5 on the left, my screencast, analysis). There was a huge difficulty gap between the first six problems, all of which were solved by 52 contestants, and the last four. Only two contestants have managed to solve two of the more difficult kind. Congratulations to Marcin and vepifanov on this amazing feat!

The most approachable problem of the difficult kind, problem H, went like this: 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.

Finally, the Open Cup season came back from the winter break on Sunday with the Grand Prix of Korea (results, top 5 on the left). Moscow State University team Red Panda have won the contest by a whole problem ahead of other super strong university and veteran teams. Congratulations on the victory!

Since the problems for this contest came from Korea, I can't help but wonder if top Korean/Asian ICPC teams have also solved this problemset elsewhere, or will do that later. Does anybody have some scoreboards to share?

Last week I have mentioned a 250-point TopCoder problem: you are given 50 integers, each up to a billion. In one step, you can take any integer that is greater than 1 and divide it by 2. If it was odd, you can choose whether to round up or down. What is the smallest number of steps required to make all integers equal?

My thinking went like this: instead of deciding immediately whether we'd round up or down, let's keep a set of possible values for each integer, which will always be a segment [min;max]. After dividing some numbers by 2 a few times, we'll have such segment for each number. Whenever these segments all have a non-empty intersection, we're done.

For example, if our initial numbers are 3, 5, and 13, then we start with segments [3;3], [5;5] and [13;13]. After dividing the last number by 2 we have [3;3], [5;5] and [6;7]. After doing it again we have [3;3], [5;5] and [3;4]. After dividing the second number by 2 we have [3;3], [2;3] and [3;4]. Now all our segments intersect in point 3, so we can make all numbers equal to 3.

The only remaining thing is to decide which numbers to divide by 2, but it actually flows naturally from the above observation. What does it mean when all segments do not have an intersection? It means that there are two segments [a;b] and [c;d] that do not intersect (this is not true for arbitrary sets, but it is true for segments), without loss of generality we have b<c. But then we must divide the segment [c;d] by 2, otherwise it will never intersect with [a;b] or its descendants. So as long as we don't have an intersection, we can always find a segment to divide by 2 this way.

Thanks for reading, and check back in a couple of days for this week's summary!