Match Editorial

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 Problems

Value	250
Submission Rate	193 / 207 (93.24%)
Success Rate	152 / 193 (78.76%)
High Score	nickel for 246.32 points (3 mins 29 secs)
Average Score	210.80 (for 152 correct submissions)

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:

public 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;
}

Value	500
Submission Rate	55 / 207 (26.57%)
Success Rate	29 / 55 (52.73%)
High Score	BhaGeera for 357.56 points (19 mins 39 secs)
Average Score	255.30 (for 29 correct submissions)

Value	250
Submission Rate	141 / 164 (85.98%)
Success Rate	128 / 141 (90.78%)
High Score	tomek for 240.95 points (5 mins 32 secs)
Average Score	174.43 (for 128 correct submissions)

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 inclusion-exclusion 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 non-empty subsets of rectangles (with three rectangles, there are 7 non-empty 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.

Value	1000
Submission Rate	31 / 207 (14.98%)
Success Rate	17 / 31 (54.84%)
High Score	syntaxglitch for 660.85 points (23 mins 0 secs)
Average Score	546.57 (for 17 correct submissions)

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 easy-to-understand solution to this problem.

Value	600
Submission Rate	71 / 164 (43.29%)
Success Rate	65 / 71 (91.55%)
High Score	evgeni for 554.00 points (8 mins 19 secs)
Average Score	387.69 (for 65 correct submissions)

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 equal-area pieces, you know that the first cut will divide the rectangle into two pieces with area proportional to 1 and N-1, or 2 and N-2, or 3 and N-3, etc. Therefore, there are only N-1 possible first cuts in the horizontal direction, and N-1 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.

Value	900
Submission Rate	14 / 164 (8.54%)
Success Rate	11 / 14 (78.57%)
High Score	Eryx for 719.89 points (15 mins 0 secs)
Average Score	471.74 (for 11 correct submissions)

The key to solving this problem is to convince yourself that it can be solved with a simple breadth-first 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 breadth-first 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:

• If the character is a '.', it can continue in the same direction with a cost of zero, or it can turn 90 degrees (i.e. placing a mirror) with a cost of 1.
• If the character is a '/' or '`', it hits a pre-existing mirror and must turn in the reflected direction, but with a cost of zero.
• If the character is a '#', you terminate that branch of the search.

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 previously-placed 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:

• retraces any part of its own path in the same direction (a cycle could never improve the optimality of a path)
• retraces any part of its own path in the opposite direction (backtracking would lead the laser back out the opening in which it started)
• requires placing two conflicting mirrors on the same square (this would cause part of the path to be retraced, which is non-optimal)
• bounces off both sides of the same mirror (replacing the mirror with the opposite mirror would lead to a more optimal path)

In other words, we don't have to disallow any illegal behavior because the breadth-first 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.