This week started with two competitions on Tuesday.
The first was Codeforces Round 207: problems, results. I didn't take part, so I don't have anything to share about the problems. Congratulations Gennady, and it's nice to see Bruce again in top 5!
Then, there was TopCoder SRM 594: problems, results, my screencast. The problemset composition was somewhat classical for TopCoder: a 250 that involves a careful check of all possibilities, a 550 that requires a standard algorithm - in this case König's theorem, and a 950 that nobody solves, although it does look quite tractable. This type of problemset places a huge emphasis on the challenge phase, and Gennady has again came out on top with 4 successful challenges.
The 550 allowed two approaches - minimum vertex cover in a bipartite graph and minimum cut in a network. The two approaches are, of course, very similar in this case. The first goes like this: let's make a bipartite graph, with the left part containing white cells, the right part containing the empty cells, and edges connecting adjacent cells from different parts. Consider a vertex cover in the graph - such set of vertices that every edge has at least one of its ends in this set. It's not hard to see that vertex covers correspond exactly to sets of cells that we can leave occupied at the end: if we put black stones to the empty cells from the vertex cover, then all white cells not from vertex cover will have all adjacent cells occupied and will be removed. Since we need to maximize the number of empty cells in the end, we need to minimize the number of occupied cells in the end, and thus minimize this vertex cover.
The second is: let's make a network consisting of source S, sink T, all white cells, and all empty cells. We draw edges from S to all white cells with capacity 1, from each white cell to its adjacent empty cells with infinite capacity, and from each empty cell to T with capacity 1. Why infinite capacity? It helps enforce the following property: for each finite cut A | B of this network, all neighbors of each white cell in A will also be in A - because otherwise there'd be an infinite edge from A to B and the cut would be infinite. Given this property, each cut gets a natural meaning: the white cells in A are those white cells that we will capture, and the empty cells in A are where the black stones will need to go. Finally, the capacity of the cut is the sum of the number of white cells in B and the number of empty cells in A, which is exactly the cells that will end up occupied, so we need to find the minimum cut.
This idea - adding appropriate infinite edges to the network to make sure each finite cut possesses the properties we require - actually comes up pretty often in algorithmic competitions.
Apart from the open competitions, this week featured quite a few ACM ICPC rounds for eligible university students. The ACM ICPC season is in full swing now, with subregionals and regionals happening across the world. Most regionals will happen in October or Novemeber, with a few slipping to December. There were several rounds this week featuring teams that will definitely challenge for medals in the World Finals, for example the NEERC Saratov Subregional (results) and the NEERC Moscow Subregional (results). Only teams from the corresponding geographical area can participate in each of those subregionals, but other teams can and usually do take part online and thus we get an early glimpse at the relative strength of the teams and determine the favorites for the regionals and World Finals.
The 550 allowed two approaches - minimum vertex cover in a bipartite graph and minimum cut in a network. The two approaches are, of course, very similar in this case. The first goes like this: let's make a bipartite graph, with the left part containing white cells, the right part containing the empty cells, and edges connecting adjacent cells from different parts. Consider a vertex cover in the graph - such set of vertices that every edge has at least one of its ends in this set. It's not hard to see that vertex covers correspond exactly to sets of cells that we can leave occupied at the end: if we put black stones to the empty cells from the vertex cover, then all white cells not from vertex cover will have all adjacent cells occupied and will be removed. Since we need to maximize the number of empty cells in the end, we need to minimize the number of occupied cells in the end, and thus minimize this vertex cover.
The second is: let's make a network consisting of source S, sink T, all white cells, and all empty cells. We draw edges from S to all white cells with capacity 1, from each white cell to its adjacent empty cells with infinite capacity, and from each empty cell to T with capacity 1. Why infinite capacity? It helps enforce the following property: for each finite cut A | B of this network, all neighbors of each white cell in A will also be in A - because otherwise there'd be an infinite edge from A to B and the cut would be infinite. Given this property, each cut gets a natural meaning: the white cells in A are those white cells that we will capture, and the empty cells in A are where the black stones will need to go. Finally, the capacity of the cut is the sum of the number of white cells in B and the number of empty cells in A, which is exactly the cells that will end up occupied, so we need to find the minimum cut.
This idea - adding appropriate infinite edges to the network to make sure each finite cut possesses the properties we require - actually comes up pretty often in algorithmic competitions.
Apart from the open competitions, this week featured quite a few ACM ICPC rounds for eligible university students. The ACM ICPC season is in full swing now, with subregionals and regionals happening across the world. Most regionals will happen in October or Novemeber, with a few slipping to December. There were several rounds this week featuring teams that will definitely challenge for medals in the World Finals, for example the NEERC Saratov Subregional (results) and the NEERC Moscow Subregional (results). Only teams from the corresponding geographical area can participate in each of those subregionals, but other teams can and usually do take part online and thus we get an early glimpse at the relative strength of the teams and determine the favorites for the regionals and World Finals.
No comments:
Post a Comment