|
Match Editorial |
Wednesday, November 29, 2006
Match summary
More than 1,000 coders took the opportunity to practice their algorithmic skills and, with several targets competing, SRM 328 was bound to be an exciting event.In Division 1 the first two problems caused little trouble, but a difficult third tripped up a lot of coders. At the end, only two coders managed to solve all three problems. gawry took home the win after edging out the coder with the most SRM wins, SnapDragon. In third came CatalinT with the best time on the hard, while Revenger and WSX, with great times on the first two problems and some points in the challenge phase, rounded out the top five. The other two coders who solved the hard were Michael_Rybak and Abednego.
Division 2 was dominated by newcomers who took the top 3 spots: frankpzh, hust_yzf, lacungus. wefgef and _dP_ rounded out the top 5.
The Problems
MarbleNecklace
Used as: Division Two - Level One:
To solve this problem we have to consider all descriptions equivalent to the given necklace. At first consider only the first direction of iterating through the marbles. We do exactly what we are told in the statement: loop through all starting positions i and build the current description by concatenating the substring starting at i and ending at the last character of necklace with the substring consisting of the first i characters. To consider the second direction as well, we have to reverse necklace, and then follow the same steps as above. We pick and return the smallest of these strings. One can use the built-in string compare for this. See cypressx’s solution for an implementation of this algorithm. In his solution, ebd used the trick of concatenating the input string with itself. After that, the description considered at the ith step is simply the substring starting at i and with a length equal to the number of marbles.
Value 250 Submission Rate 428 / 528 (81.06%) Success Rate 297 / 428 (69.39%) High Score ebd for 247.65 points (2 mins 46 secs) Average Score 194.05 (for 297 correct submissions)
LightsCube
Used as: Division Two - Level Two:
Used as: Division One - Level One:
Value 500 Submission Rate 156 / 528 (29.55%) Success Rate 128 / 156 (82.05%) High Score lacungus for 427.75 points (12 mins 6 secs) Average Score 271.62 (for 128 correct submissions)
There are several ways to approach this problem. Most coders chose to simulate the process second by second. At every second, we iterate through all squares of the cube and turn on the lights that are off and are adjacent to at least one turned-on light. See tomek’s solution for an example of this approach.
Value 250 Submission Rate 387 / 414 (93.48%) Success Rate 361 / 387 (93.28%) High Score SnapDragon for 246.74 points (3 mins 16 secs) Average Score 175.93 (for 361 correct submissions)
A nicer approach, and quicker to implement, is to calculate for each light the time when it can take each of the colors in the input. Considering the way the lights spread through the cube, this is really the Manhattan distance between the positions of the two lights. We then pick the color with the minimum time, and in case of ties, the one with a lower number. See SnapDragon’s solution for a nice implementation of this algorithm.
The fastest solution is based on the breadth-first search on a graph whose vertices are the squares of the cube, and the edges correspond to adjacent squares. See Burunduk3’s solution.
ScoreDifference
Used as: Division Two - Level Three:
In this problem we are told the rules of a board game and we are asked to calculate the score difference at the end of the game assuming both players are following an optimal strategy.
Value 1000 Submission Rate 15 / 528 (2.84%) Success Rate 7 / 15 (46.67%) High Score frankpzh for 632.79 points (24 mins 55 secs) Average Score 550.31 (for 7 correct submissions)
To solve it, we will write a recursive function maximize that takes as input the current board state and returns the maximum score difference that could be obtained on this board by the player to move. We will consider every valid move (ie. a piece that can be removed from the board), perform it, and recurse on the new board state. The score difference that can be obtained with this move is the difference between the point value of the piece removed by the player to move and the score difference his opponent can achieve on the new board state. We have to use substraction here, since the score difference returned by the recursion is from the opponent’s point of view. In pseudocode, the function would look in the lines of:
maximize (boardState) score = -infinity for each valid move m newBoardState = performMove(boardState, m) score = max(score, moveScore(m) – maximize(newBoardState)) return scoreA board state must contain information about which squares are empty and which are occupied. As experienced coders have guessed, we can use bitmasks to efficiently describe a board state. We will use 16 bits, one for each square of the board. If a square is free, its corresponding bit in the bitmask will be 0, otherwise it will be 1. To determine if a move is valid, it is easiest to use a depth-first search on the graph where the vertices are the squares of the board, and the edges correspond to adjacent squares. Of course, we should memoise the function to avoid time-out. For a clean implementation of this algorithm, see wefgef’s solution.
BlockEnemy
Used as: Division One - Level Two:
This problem sounds as dynamic programming at first, but it has a greedy solution as well. Some of the more experienced coders have chosen to code the safer dynamic programming solution instead of looking/proving the greedy one. See tomek’s solution for an example. In his nice solution, gawry worked on this approach and turned it into a greedy one.
Value 500 Submission Rate 187 / 414 (45.17%) Success Rate 132 / 187 (70.59%) High Score gawry for 437.29 points (11 mins 5 secs) Average Score 287.43 (for 132 correct submissions)
Let’s associate a weighted undirected graph to the map described in the problem statement. The towns will be the vertices and the bidirectional roads between them will be the edges, with the weight equal to the effort. The vertices corresponding to the occupied towns will be marked. Note that the graph described in the statement is actually a tree. We are asked to remove some of the edges of the tree in order to disconnect any two of the marked vertices. After doing this we will end up with a number of smaller trees, possibly consisting of only one vertex. Each of these smaller trees will contain at most one marked vertex. In fact, it will contain exactly one marked vertex: if one tree without any marked vertex existed, we could add back one of the removed edges and merge it with another subtree, without adding a path between two marked vertices, and lowering the total cost. It is now easy to see that the number of edges that must be removed from the original tree is one less than the number of marked vertices.
Let us denote by e the edge with the smallest weight among the edges that, when removed, disconnects (at least) a pair of marked vertices. We will now prove that there exists an optimal solution in which this edge is removed. Let’s take an optimal solution in which edge e is not removed. If we remove it, we split one of the subtrees in two smaller subtrees, and only one of them contains the marked vertex. Since we do not allow subtrees that don’t contain a marked vertex, we have to merge this subtree with another one by adding one edge. Because of the way we have chosen e, this edge will have a weight greater or equal to e’s weight. Since we added one edge to the set of removed edges, e, and removed another with a greater or equal weight, we end up with a solution with a total cost less than or equal to the cost of the original solution. Since we assumed that solution was optimal, we conclude that the edges have equal weight, and the new solution with e removed will be optimal as well.
Based on the key observation above, we can build a greedy solution: choose the edge e as above, remove it, and then recurse on each on the two subtrees obtained. The base case is when the tree contains only one marked vertex and there is no need to remove any edge. There are a few ways in which this algorithm can be implemented, some more efficient than others. In his solution, Gigz iterated through the edges in increasing order of weight, and if an edge disconnected two marked vertices he removed it. Others coders solved a complementary problem: they found a set of edges that must not be removed, with a maximum total weight, using a variation of the Kruskal’s algorithm for finding a minimum spanning tree. See rgrig’s solution for an example of this. Another interesting approach was taken by Revenger, who iterated through all pairs of marked vertices, and, if necessary, removed the edge with the smallest weight on the path connecting them.
As a sidenote, the greedy algorithm does not work for general undirected graphs. If there are only two marked vertices we obtain an instance of the minimum-cut problem, solvable with max-flow.
BackyardTrees
Used as: Division One - Level Three:
This problem may look intimidating at first, but the observations and ideas behind it are not that difficult.
Value 1000 Submission Rate 17 / 414 (4.11%) Success Rate 5 / 17 (29.41%) High Score CatalinT for 507.63 points (36 mins 31 secs) Average Score 445.69 (for 5 correct submissions)
Of all the requirements of a way to plant the trees on the grid, the hardest to workaround is the one that all trees should be on the same line. To manage this, we will plant the first two trees at two points on the grid, and then plant the remaining ones on the segment connecting these two points. Next we need to calculate how many grid points are on this segment, and then the number of ways to plant the remaining trees on these points.
Say the two grid points are (x1, y1) and (x2, y2). We will enforce x1 &le x2, otherwise we would count solutions two times. The first part is easy: let w = x2 – x1 and h = y2 – y1. First perform a translation and move these points to (0, 0) and (w, h) (the second point is not necessarily a grid point, since the second coordinate could be negative). A point (x, y) on this segment must have: x/w = y/h which implies x * h = y * w. Let p = gcd(w, abs(h)). Constraining these points to be on the segment, and neglecting the two endpoints, we can prove that there are p - 1 grid points on the segment (if you can’t prove it, you may ask in the forums), and the distance between two adjacent grid points is sqrt(w/p*w/p + h/p*h/p).
For the second part, we first need to calculate the number s of grid points that must be skipped between two adjacent trees, in order to leave between them a distance of at least distance. We get s = distance / d. There is a corner case here: when d is an integer and distance is divisible by d, we should substract 1 from s.
We can now use either dynamic programming or a direct relation to count the ways the remaining points could be placed on the segment. For the former, let R[q][n] be the number of ways that q trees could be planted on n points, if we leave at least s free points between adjacent trees. There are two cases to consider: plant a tree at the nth point or not. This gives you the recurrence: R[q][n] = R[q-1][n-1-s] + R[q][n-1] (of course, one should work with modular arithmetic). Writing the base cases for this recurrence could be tricky, R[q][n] is 1 when q = 0 (including negative values for n) and 0 when q > 0 and n &le 0. However, there is a way to calculate R[q][n] directly using the binomial coefficient. Substract from n the number of points that will be skipped with certainty: (n-1) * s, and then choose any way to place the q trees on the remaining points, giving: R[q][n] = C(n - (n-1)*s, q).
We are not done, since fixing both endpoints of a segment would certainly time-out. We will fix the direction and the magnitude of the vector determined by the two endpoints (w and h from above) and then count how many pairs of points (x1, y1) and (x2, y2) from the grid could be its endpoints:
(width – w + 1) * (height – h + 1).
See Michael_Rybak’s solution for an implementation of the above algorithm. Slower DP solutions were implemented by CatalinT (code) and Abednego (code).
