January Contests

No, I didn't forget this blog. I was just too lazy to write new posts. Anyway, after the last post I was not very active - I participated only in one SRM and Facebook Hacker Cup's rounds (and SnarkNews Series, though I gave up after having trouble with understanding the Russian statements).

In SRM 706, the first two tasks were relatively easy. My idea for the Hard was as follows. In this task you want to find a family of subsets of {1, ..., N}, where no subset contains two consecutive numbers and for each non-consecutive pair (p, q), at least one subset contains both. First add a subset that contains all even numbers, and add another subset that contains all odd numbers. Now we only need to care about pairs with different parities. In my construction, for example when N = 15, add three sets: {2, 4, 6, 9, 11, 13, 15}, {1, 3, 5, 7, 10, 12, 14}, and {1, 3, 5, 8, 11, 13, 15}. Then do the same thing recursively for {1, ..., 7} and {9, ..., 15} (like divide-and-conquer). This way we only need about 3 * lg N sets but it turned out that the numbers can be as large as 10^25. Maybe we can do it with 2 * lg N sets? I still don't know the answer, let's add it to "Upsolving" section.

My rating slightly increased after the contest and it became 3615. It seems this is the 4th in TopCoder's history. However it's far away from the three legends - Petr (3924), ACRush (3902), and tourist (3836).

Do you understand what the picture above means? Facebook. There were four elimination rounds in this year's FHC. The first three rounds were relatively easy. The second task in Round 1 was notable - at first it looked like a very tedious task where you have to find all subsets of points that can be enclosed by a circle, but there's a significantly simpler solution: you only need to consider the union of two squares.

Last Sunday I participated in Round 3, the last elimination round. I knew problem A so I solved it quickly. After that I read everything and decided to solve B first - it's tricky and requires careful coding, but I'm good at counting tasks and it looked like the easiest one. After that the choice was between C and E. D looked overwhelming at that time. I chose C mainly because it looked very easy to do stress-testing and believed that correct A+B+C can qualify (which turned out to be wrong and I was quite close to the cutoff due to too big penalty). Maybe careful A+B+E was a better strategy. (However, I have to admit that I made a small mistake and my E failed during upsolving).

My solution for C was as follows. First for each non-center vertex i, compute two values x[i] and y[i]. x[i] is the position along the cycle and y[i] is the shortest path from the center. Now the problem asks to compute the sum of min{x[j] - x[i], X - (x[j] - x[i]), y[i] + y[j]}, where X is the total cycle length. In my solution I assumed that the arrays x and y are arbitrary. This leads to a solution with BIT. But x and y are not arbitrary arrays and these satisfy triangle inequalities of a certain graph. If we use this fact, we can prove that for a fixed i we can split the cycle into three consecutive parts and in each part we can determine which of x[j] - x[i], X - (x[j] - x[i]), y[i] + y[j] is the smallest. This leads to a simpler linear solution.

During the contest, my first idea for D was as follows. Consider two numbers x and y, and two masks (the set of non-broken positions) mask1 and mask2. We can't distinguish two states (x, mask1) and (y, mask2) after t seconds if ((x + t) & mask1) and ((y + t) & mask2) are the same. For each bit there are several cases: it is broken in both states, broken in one state and off in another, ... and so on. And looked completely unapproachable. Indeed I missed a very simple thing: when the position i is 0 in the input, we can always assume that the display is broken at this position. This observation greatly simplifies the problem and now we know mask1 and mask2 - now we can concentrate on x and y. After that it's still tricky, but quite solvable task.

How should we solve it during the contest? One possible approach is to consider various cases, but I don't prefer it with such weak examples. Digit DP is also possible but it's fairly complicated. Here's a very simple solution: we can prove that in the optimal solution x and y differ in only two bits. Fix two positions p and q - at position p, x is 0 and y is 1, and at position q, vice versa. And in other positions x and y are the same. In this case, we can prove that there's some r such that the bits at positions [r, N) doesn't matter at all, and we want to minimize the numbers in the least-significant r bits. If we fix these three numbers (p, q, r), we can solve the task without considering various cases. This will lead to a very simple O(N^4) solution. Source code in ideone.

Anyway, I managed to qualify to the Finals. If you also qualified, see you in Seattle!