The March 21 - March 27 week was much more relaxed than previous ones.
TopCoder Open 2016, one of the most important tournaments of the year, kicked off on Saturday with Round 1A (problems, results, top 5 on the left). Top 250 contestants who have competed in at least one SRM in 2016 have been automatically qualified to Round 2, so Round 1s are often a chance for mostly retired contestants to come back in style. This time it was nika who combined very good problem solving with excellent challenging to get the first place — awesome job! Please tell your friends at MemSQL that they should come back, too :)
The first problem mentioned in the previous summary, about high-school geometry, has an editorial explaining my approach, so I won't go into more detail here. The second problem, though, is worth discussing.
You were given a 8x8 grid, with three points on this grid designated as "houses", and three as "wells". You need to pick a positive integer d<=1000, subdivide each square of the grid into d times d small squares, obtaining a 8d times 8d grid, and then draw nine non-intersecting paths on this grid: from each house to each well. Of course, the problem as stated is impossible to solve since K3,3 is not planar; to make it solvable, the grid was toroidal: the left edge was identified with the right edge, and the top edge was identified with the bottom edge (picture on the left from the original problem statement).
This problem has two parts: topological and combinatorial. The topological part is concerned with laying out nine required curves on a toroidal square in such a way that they don't intersect; the combinatorial part is placing those paths on a (subdivided) grid.
The key insight for the topological part is that it's actually very easy, and there are a lot of ways to do it. Why? Because we can embed a much more complex graph into a torus: K7! Because of this, we can adopt the following approach for the topological part: let's draw the paths one by one in random order, and in case we fail, just try again. This is likely to work because there are so many possible topological configurations.
How do we draw the paths combinatorially? Let's start by simply drawing shortest paths using breadth-first search. Of course, this can fail - at some point there will be no path on the grid between the two points that we want to connect. But what can be the reason for that? There are two cases:
1) There's no path even if we forget about the grid restriction - the graph that we have drawn doesn't allow to connect the points, meaning that we've failed topologically.
2) There's a path, but as soon as we try to embed it into the grid, it disappears.
Our goal now is to avoid the failures of the second type. As mentioned above, in case we get a failure of the first type, we'll just restart the process from scratch with a different random ordering of paths.
The key idea now is that we can subdivide the grid as we go, instead of doing this at the start. In other words, first we build paths on the original grid. As soon as we can't build some path, we can subdivide each square of the grid into a 2x2 subgrid. As a result, now there will be free grid points between every two existing paths, and thus it's very unlikely that we can't draw a path because of combinatorial restrictions.
More precisely, the only combinatorial restriction that can still exist after that is around the endpoints of the path. If two existing paths enter an endpoint at 90 degrees to each other, then even after subdividing the grid we can't insert a third path between them. But since we need to draw only three paths for each endpoint, we can fix this issue by restricting the second path to exit it at 180 degrees compared to the first path. Then we will always be able to eliminate combinatorial obstacles by subdividing the grid!
I'm pretty sure there are many other approaches possible in this problem. Please share yours!
And of course, check back soon for the following week's summary, and don't forget to participate in the Google Code Jam 2016 Qualification Round — there are still a few hours left!
The first problem mentioned in the previous summary, about high-school geometry, has an editorial explaining my approach, so I won't go into more detail here. The second problem, though, is worth discussing.
This problem has two parts: topological and combinatorial. The topological part is concerned with laying out nine required curves on a toroidal square in such a way that they don't intersect; the combinatorial part is placing those paths on a (subdivided) grid.
The key insight for the topological part is that it's actually very easy, and there are a lot of ways to do it. Why? Because we can embed a much more complex graph into a torus: K7! Because of this, we can adopt the following approach for the topological part: let's draw the paths one by one in random order, and in case we fail, just try again. This is likely to work because there are so many possible topological configurations.
How do we draw the paths combinatorially? Let's start by simply drawing shortest paths using breadth-first search. Of course, this can fail - at some point there will be no path on the grid between the two points that we want to connect. But what can be the reason for that? There are two cases:
1) There's no path even if we forget about the grid restriction - the graph that we have drawn doesn't allow to connect the points, meaning that we've failed topologically.
2) There's a path, but as soon as we try to embed it into the grid, it disappears.
Our goal now is to avoid the failures of the second type. As mentioned above, in case we get a failure of the first type, we'll just restart the process from scratch with a different random ordering of paths.
More precisely, the only combinatorial restriction that can still exist after that is around the endpoints of the path. If two existing paths enter an endpoint at 90 degrees to each other, then even after subdividing the grid we can't insert a third path between them. But since we need to draw only three paths for each endpoint, we can fix this issue by restricting the second path to exit it at 180 degrees compared to the first path. Then we will always be able to eliminate combinatorial obstacles by subdividing the grid!
I'm pretty sure there are many other approaches possible in this problem. Please share yours!
And of course, check back soon for the following week's summary, and don't forget to participate in the Google Code Jam 2016 Qualification Round — there are still a few hours left!
No comments:
Post a Comment