Wednesday, April 6, 2005 Match summary With the fastest time on the hard problem, Eryx finished first in division 1 by well over 100 points and moved up to number 3 in the overall ranking. Coders krijgertje and ivan_metelsky finished in second and third place, each by a comfortable margin. In division 2, karavanas took the top spot, followed by syntaxglitch and Kentaro in second and third. The ProblemsCardsUsed as: Division Two  Level One:
When possible, it's nice to have the solution's structure mimic what's actually occurring in the problem. Here we have that luxury. First set up the variable you will be returning (String[], vector<STRING>,...). Then loop through the deck, as a dealer would, and deal one to each player. The only extra bit of information, is to check whether to deal another round. Java code follows: public String[] dealHands(int numPlayers, String deck) { String[] players = new String[numPlayers]; java.util.Arrays.fill(players,""); //null Strings are annoying for (int left = deck.length(); left >= numPlayers; ) for (int i = 0; i < numPlayers; i++, left) players[i]+=deck.charAt(deck.length()left); return players; } An alternate way would use modulus: BoxUnionpublic String[] dealHands(int numPlayers, String deck) { String[] players = new String[numPlayers]; java.util.Arrays.fill(players,""); //null Strings are still annoying for (int i = 0; i < deck.length(); i++) { if (i%numPlayers==0 && deck.length()i<numPlayers) break; players[i%numPlayers]+=deck.charAt(i); } return players; } Used as: Division Two  Level Two: Used as: Division One  Level One:
One approach to computing the area of the union would be to loop over all squares, and count those that are inside of at least one rectangle. Unfortunately, because the maximum coordinate values are 20000, such a solution would be too slow. A better approach is to use the inclusionexclusion principle. Considering the example from the problem statement: you start by summing the area of the three rectangles individually: 4*3 + 5*3 + 4*4 = 12 + 15 + 16 = 43 Notice that we have overcounted the squares where any two rectangles overlap. To correct this, we subtract the area of the intersection of each pair of rectangles: 43  1*2  3*1  2*2 = 43  2  3  4 = 34 But now consider the area where all three rectangles overlap. We counted this area three times in the first step, and then subtracted it three times in the second step. To make sure it gets counted exactly once, we need to add the area of the intersection of all three rectangles back in: 34 + 1*1 = 34 + 1 = 35 And this is the correct answer. More generally, you compute the area of the intersection of all nonempty subsets of rectangles (with three rectangles, there are 7 nonempty subsets). If the subset contains an odd number of rectangles, you add its area to the total, and if it contains an even number of rectangles, you subtract it from the total. Notice that we only ever need to find the intersection of rectangles, which is easier than finding the union because the intersection of two rectangles is always either empty or another rectangle. To intersect two rectangles, you simply take the maximum of their left coordinates, the maximum of their bottom coordinates, the minimum of their right coordinates, and the minimum of their top coordinates. MirrorPathUsed as: Division Two  Level Three:
This problem is solved in two steps: finding the location and direction to begin in, and then tracing the path through the maze. To find the initial square, you simple loop over all boundary squares until you find a '.' character. There will be exactly 2, and it doesn't matter which one you select. The initial direction will depend on which side of the maze you found the '.' character. You don't need to worry about what to do if you start in a corner, because this is specifically disallowed in the problem statement. Tracing the path through the maze involves implementing a simple state machine. At each step, you decide what to do based on the character at that location of the map. If it is a '.', you replace it with either a '' (if the laser is currently traveling left or right) or a '' (if the laser is currently traveling up or down). If it is a '/' mirror, you change direction: left <> down, right <> up. If it is a '`' mirror, you change direction: left <> up, right <> down. If it is a '' or '' character, you replace it with '+' (more on this below). You do not need to worry about hitting a '#', as the problem statement guarantees that the path will exit the maze (and therefore not hit any walls). After each step, you update the laser's position by moving it one square in the current direction. Note that if you encounter a '' or '' character, the laser is crossing its own path. You can simply replace the character with a '+', without worrying about your current direction. Why? Because it is impossible for the laser to retrace any part of its own path, forward or backward. The only possible way for the laser to enter the same square twice is if it is crossing in the perpendicular direction. It is impossible for it to enter the same square more than twice. See coder Kentaro's submission for a clean and easytounderstand solution to this problem. CakeDivisionUsed as: Division One  Level Two:
The key to solving this problem is to realize that there are a limited number of cuts you can make at any one time. To divide a rectangle into N equalarea pieces, you know that the first cut will divide the rectangle into two pieces with area proportional to 1 and N1, or 2 and N2, or 3 and N3, etc. Therefore, there are only N1 possible first cuts in the horizontal direction, and N1 possible first cuts in the vertical direction. Because of symmetry, you can eliminate about half of these. This leads to a nice recursive algorithm, where at each step you consider all possible cuts, and recurse on the two resulting pieces. The recursive function takes as parameters the width and height of the rectangle it is dividing and the number of pieces it is to divide it into. It returns the smallest possible maximum aspect ratio it has found of the resulting pieces. The base case for the recursion is when the number of pieces is equal to 1, in which case you simply return the aspect ratio of the rectangle. Although not necessary given the limits on the input for this problem, the recursive algorithm could be sped up with memoization. MirrorPlacementUsed as: Division One  Level Three:
The key to solving this problem is to convince yourself that it can be solved with a simple breadthfirst search, and that you do not need to keep track of the positions of any mirrors you have placed. I'll describe the search first, and then explain why this works afterward. After you have determined the starting square (either one will do), you perform a breadthfirst search starting at that square. The state is the laser's position and direction. At each step, the weights to neighboring states depend on (and only on) the characters given in the map:
Once you have searched the entire space, the distance associated with the ending square (in the direction pointing out of the maze) is the number of mirrors you would have had to add to arrive there. If you structure you search well, such that you consider all states in order of distance, you can stop the search as soon as you reach the exit square. Now, you may be wondering how you can get away with not remembering the locations of mirrors you have already placed. For example, when encountering a '.' character, it would be wrong to assume that you can go straight through it if you have already placed a mirror there. Or worse, it would be wrong to assume you can place a mirror if you have already placed one there oriented in the other direction. Finally, it seems that it would be important to know that the laser could bounce off the back of a previouslyplaced mirror "for free", without having to place it in the same square a second time. But there's no way to know this if you don't keep trace of the mirrors you've placed. All of these concerns vanish in a puff of logic when you consider what you are searching for: the number of mirrors in the optimal path from the start to end. An optimal path never does any of the following:
In other words, we don't have to disallow any illegal behavior because the breadthfirst search finds the optimal path, and the optimal path does not include anything illegal. The only time an optimal path were to enter the same square twice is if it were crossing itself perpendicularly, with no mirror in that square. 
