A rolling week

The Oct 15 - Oct 21 week started with Codeforces hosting Mail.Ru Cup 2018 Round 1 (problems, results, top 5 on the left, analysis). Despite the round's slightly longer 2:30 duration, the usual two hours were enough for mnbvmar to claim the first place. Congratulations!

TopCoder SRM 740 followed on Saturday (problems, results, top 5 on the left, analysis). With the win in this round, xudyh has joined tourist at the top of the TCO19 points scoreboard (link, click on "Stage 1") and made sure it's just the two of them fighting for the single TCO19 direct qualification spot in the final October SRM a bit later. Well done!

My solution for the hard problem has failed the system test, and I was trying to recall why when I'm writing this post now, two months later. I did not remember, so I've decided to look at the diff between my solution during the round and the one I got accepted afterwards:

31,33c31,33
<     matrix[limbo][start * 2 + startState] += old;
<     if (matrix[limbo][start * 2 + startState] >= MODULO)
<         matrix[limbo][start * 2 + startState] -= MODULO;
---
>     matrix[limbo][start + 2 * startState] += old;
>     if (matrix[limbo][start + 2 * startState] >= MODULO)
>         matrix[limbo][start + 2 * startState] -= MODULO;

When I first saw this diff today, there were also a few spurious formatting diffs here and there, and I could not actually notice that this one is meaningfully different. I guess this is what happened during the round as well, and is similar to what happens when reading those "jumbled" English sentences: we most likely don't read the programs character by character or token by token, but rather read the statements as a whole, and thus can assume parts which are not there. Anyway, enough psychology speculation, the diff is: the first block has "* 2 +", and the second one has "+ 2 *" (the former is correct).

Finally, one more Codeforces round, the 517-th one, took place on Sunday (problems, results, top 5 on the left, analysis). It was Radewoosh this time who earned enough points for the first place just one hour into the contest, which was a bit more risky in this round given that ainta did in fact solve a hard problem that Radewoosh did not. Congratulations on the victory!

In my previous summary, I have mentioned a few problems. First one was from TopCoder: you are given a number n between 3 and 500. You need to generate any simple (not necessarily convex) polygon with n vertices, where all vertices have integer coordinates between 1 and 25, inclusive, and which has the smallest possible area among such polygons.

The mathematical part of the solution is rather standard: Pick's theorem tells us that to minimize the area it is necessary and sufficient to have no integer points inside the polygon, and no extra integer points except the n vertices on the boundary of the polygon.

Now we need to figure out a way to draw such polygon without extra integer vertices on a relatively small grid. This picture by fjzzq2002 demonstrates a very good approach to do that.

The second mentioned problem from AtCoder has a very good editorial (problem D "Chords" there), I don't have much to add to it.

Finally, there was an Open Cup problem which is actually not explained in the corresponding analysis: you are given a 50x50 grid where some cells are empty, and some are walls. There are also walls surrounding the grid. Some empty cells are marked as targets, and there's also a ball in one of the empty cells. You can move the ball in each of the four cardinal directions, but once it starts rolling, it rolls in the same direction until it hits the wall, at which point you can pick a new direction, and so on. Can you roll the ball in such a way that it passes through all targets in some order?

Here's the key observation: suppose we roll the ball to the right at some point. Then we can immediately roll it to the left and to the right again, end up in exactly the same position, but be guaranteed to have covered an entire horizontal segment of the grid. Similarly, rolling the ball up or down can be viewed as traversing an entire vertical segment of the grid.

So instead of thinking in terms of moving the ball from cell to cell, we can enumerate all non-extendable horizontal and vertical segments in the grid, and think of our movement as jumping from one such segment to another. For example, from a horizontal segment we can jump to one of the two vertical segments containing the endpoints of the horizontal segment.

The key benefit from such formulation comes from the fact that every target belongs to just two such segments: one horizontal and one vertical. The number two points us towards reducing this problem to 2-SAT: let's introduce one variable per segment, which will be true if our path visits this segment, and false otherwise. The condition about visiting all targets can now be encoded as a set of "one of those two variables must be true" clauses, which are permissible in 2-SAT.

The other condition that we must enforce is that all visited segments can be put on one path that starts from the starting position. In order to achieve that, we add two types of restrictions:

1. If a segment is not reachable from the starting position, the corresponding variable must be false.
2. For each pair of segments such that none is reachable from the other, at least one of the two corresponding variables must be false.

The second restriction guarantees us a total linear order of the visited segments, which is exactly what a path is, and the first one makes sure this path can start in the right place. Both restrictions are already expressed in the form of 2-SAT clauses.

Our 2-SAT problem has O(n²) variables and O(n⁴) clauses, where n=50 is the size of the grid. Since 2-SAT is solved in linear time, this is fast enough. One more potentially slow part is discovering all restrictions of the second type as we need to find the transitive closure of a graph with O(n²) vertices. However, the number of edges in the graph is also O(n²), so the transitive closure can be found in O(n⁴) as well.

Thanks for reading, and check back for more!