The second round of voting for the new name of this blog happens in my Google+ - please help me choose!
TopCoder SRM 637 took place on Thursday (problems, results, top 5 on the left, my screencast). The hard problem in this round had an interesting blend of requiring both an algorithmic insight, and an "ad-hoc" insight making use of the fact that everything happens on a grid.
You were given a 30x30 grid, each cell colored using one of 62 colors in such a way that all cells covered by the same color form a single 4-connected region. Each color is given to exactly one of the two players. If the first player has a 4-connected path from the left side of the grid to the right side of the grid using only cells of his colors, she wins. If the second player has a 4-connected path from the top side of the grid to the bottom side of the grid using only cells of his colors, she wins. It's obvious that both players can't win at the same time. But is it possible that neither player wins, given the grid coloring?
One of the first ideas that come to mind from previous contest experience is that lack of 4-connected path from left to right is equivalent to existence of a 8-connected path from top to bottom (is there a canonical link that explains this duality?), so essentially we have to find two non-intersecting 8-connected paths, one from top to bottom, and one from left to right, such that each color is used in at most one path. Can you see how to proceed from here?
Codeforces Round 275 happened a day later (problems, results, top 5 on the left). Problem B was quite simply stated and presented a nice, if not very difficult, algorithmic challenge. There's a hidden array of 100000 non-negative integers up to 230-1, and the only things you know about it are bitwise ANDs of its consecutive subarrays, for at most 100000 subarrays each given by the left and right boundaries. You need to find at least one array with such subarray bitwise ANDs or report that none exists.
Quite a few official ACM ICPC competitions are also happening these days. In particular, NEERC Saratov (results, the participants of the offical competition are marked as "ghosts") and Moscow (onsite results, online results) subregionals had online mirrors that let us get an early glimpse at the relative strength of various Russian ACM ICPC teams this season. So far, the Tapirs team from the Moscow State University is the one to beat. Another interesting thing about those and other subregional scoreboards is the teams that are missing from them: the obvious one is that tourist's team did not participate in the online mirrors, but they are still planning to participate in the Northern subregional as far as I know; but there are actually two strong teams who look to be skipping this year's official ACM ICPC contests completely: the strongest Nizhny Novgorod State University team and the strongest Ural Federal University team, placed fourth and fifth in the latest Petrozavodsk training camp. This is an (unintended?) side effect from the rule that lets each person participate in the ACM ICPC World Finals at most twice.
Finally, let's come back to a puzzle from last week to explain the solution. The puzzle was: given an undirected graph where the degree of each vertex is at most 5, prove that it's possible to color its vertices using 3 colors in such way that each vertex has at most one adjacent vertex of the same color as itself. The approach we'll take is very straightforward: start from arbitrary coloring of all vertices using 3 colors, for example a completely random one, then gradually improve it until it satisfies the restriction of at most 1 adjacent vertex of the same color for every vertex. In order to improve, we pick any vertex that has at least 2 adjacent vertices of the same color, and fix its color. Since its degree is at most 5, there a color that at most one of its neighbors has, so we pick that color for the fix. One might even think that doing this once for each vertex is enough — but that's not true, since by fixing one vertex we might break its neighbor, more precisely the one with the color we're fixing our vertex to. Given this knowledge, it's not clear anymore why the fixing process terminates at all. That's when the magic happens: we can notice that each fix decreases the number of edges where both ends have the same color! We get rid of at least two such edges, and introduce at most one. Because of this, the total number of fixes does not exceed the total number of edges.
Thanks for reading, and see you next week!
You were given a 30x30 grid, each cell colored using one of 62 colors in such a way that all cells covered by the same color form a single 4-connected region. Each color is given to exactly one of the two players. If the first player has a 4-connected path from the left side of the grid to the right side of the grid using only cells of his colors, she wins. If the second player has a 4-connected path from the top side of the grid to the bottom side of the grid using only cells of his colors, she wins. It's obvious that both players can't win at the same time. But is it possible that neither player wins, given the grid coloring?
One of the first ideas that come to mind from previous contest experience is that lack of 4-connected path from left to right is equivalent to existence of a 8-connected path from top to bottom (is there a canonical link that explains this duality?), so essentially we have to find two non-intersecting 8-connected paths, one from top to bottom, and one from left to right, such that each color is used in at most one path. Can you see how to proceed from here?
Quite a few official ACM ICPC competitions are also happening these days. In particular, NEERC Saratov (results, the participants of the offical competition are marked as "ghosts") and Moscow (onsite results, online results) subregionals had online mirrors that let us get an early glimpse at the relative strength of various Russian ACM ICPC teams this season. So far, the Tapirs team from the Moscow State University is the one to beat. Another interesting thing about those and other subregional scoreboards is the teams that are missing from them: the obvious one is that tourist's team did not participate in the online mirrors, but they are still planning to participate in the Northern subregional as far as I know; but there are actually two strong teams who look to be skipping this year's official ACM ICPC contests completely: the strongest Nizhny Novgorod State University team and the strongest Ural Federal University team, placed fourth and fifth in the latest Petrozavodsk training camp. This is an (unintended?) side effect from the rule that lets each person participate in the ACM ICPC World Finals at most twice.
Finally, let's come back to a puzzle from last week to explain the solution. The puzzle was: given an undirected graph where the degree of each vertex is at most 5, prove that it's possible to color its vertices using 3 colors in such way that each vertex has at most one adjacent vertex of the same color as itself. The approach we'll take is very straightforward: start from arbitrary coloring of all vertices using 3 colors, for example a completely random one, then gradually improve it until it satisfies the restriction of at most 1 adjacent vertex of the same color for every vertex. In order to improve, we pick any vertex that has at least 2 adjacent vertices of the same color, and fix its color. Since its degree is at most 5, there a color that at most one of its neighbors has, so we pick that color for the fix. One might even think that doing this once for each vertex is enough — but that's not true, since by fixing one vertex we might break its neighbor, more precisely the one with the color we're fixing our vertex to. Given this knowledge, it's not clear anymore why the fixing process terminates at all. That's when the magic happens: we can notice that each fix decreases the number of edges where both ends have the same color! We get rid of at least two such edges, and introduce at most one. Because of this, the total number of fixes does not exceed the total number of edges.
Thanks for reading, and see you next week!
