Saturday, July 19, 2008 Match summaryIn both divisions, coders faced 1000point problems that were even tougher than I'd anticipated. In Division 1, the hard problem received only two submissions, neither of which passed. In the end, the battle was between Eryx and krijgertje. Eryx was ahead after the coding phase, and towards the end of the challenge phase both had three successful challenges. Unfortunately for Eryx, his next challenge failed, leaving him just two points behind krijgertje. Al.Cash, Petr and Gluk completed the top five. In Division 2, newcomer kmod looked strong at the end of the challenge phase, but with his hard problem failing system tests, had to settle for second place. This left snomak in first and li0n192 in third. iBob's was the only successful solution to the hard problem, but this left him with insufficient time to solve either of the others. The ProblemsContiguousCacheEasyUsed as: Division Two  Level One:
The problem describes exactly what needs to be done, so solving it is a matter of handling the details. Let's say that we have the endpoints of the current range stored in P and Q, with Q = P + k  1. When a new byte at address A is requested, we can consider three cases. In the first case, A < P, and so the new range start becomes P' = A. In the second case, A > Q, and the new range end becomes Q' = A, and hence P' = A  k + 1. Finally, if P ≤ A ≤ Q then nothing needs to be done. If the range moves, we have to calculate how many reads are required. Let d = P  P' be the distance of the move. If d ≥ k then the old and the new ranges have no overlap, so k reads are required. Otherwise, d reads are required. AddElectricalWiresUsed as: Division Two  Level Two: Used as: Division One  Level One:
To start with, let's assign a See dzhulgakov's solution for an example implementation. ClosestRegexUsed as: Division Two  Level Three:
Let's consider just the first character of the text and the first atom of the regular expression (regex). If the first atom is just a character, then there is only one option: the first character of the text must match it, and if it doesn't currently, it must be changed. Things are more interesting when the first atom is of the form x*. There are now two cases to consider: either the x* matches zero characters, and can be removed, or the first character of the text must be (or become) an x, and the rest of the text must match the original regex, including the x*. This leads to a natural recursive approach, trying both options in each case and taking the best, but it will be too slow. Fortunately, this can easily be handled with dynamic programming. The table for DP is indexed by the length of a suffix of the text (in characters) and a suffix of the regex (in atoms). ContiguousCacheUsed as: Division One  Level Two:
The key to this problem is to consider two types of cache moves: those that overlap the previous range and those that don't. In the former case, one will always want to move the range by the smallest amount: larger amounts may save reads later, but by at most the number of extra reads now. On the other hand, when moving to a nonoverlapping range, it may be advantageous to move the range further than necessary for now, to save on reads later. Let's start by just considering moves that always keep an overlapping range, and try to determine where to place the range for the first read. Obviously, we would like as many subsequent reads as possible to fall in this range. We can do this by tracking the highest and lowest address read, and when they fall too far apart to cover with one range, place the initial range to just cover the earlier read while being as close as possible to the later read. What about moves that split the range? It's not always clear where to use them, since in some cases they are not required in the present but are beneficial in the future. We can attack this with dynamic programming: let dp[i] be the minimum number of reads necessary for the first i reads. To compute dp[i], we first decide how many reads fall into this block of overlaponly moves (by trying all the options). If there are r reads in the current range, then the total cost is dp[i  r] plus the cost of the current range using only overlapping moves, solved as described above. Note that we don't need, in the DP, to keep track of where the range was left at the end of the block, since we assume that the initial range for the new block will not overlap it. krijgertje took a slightly simpler approach. He used dynamic programming, tracking the cost of doing the first i accesses and finishing with the range in position j. Normally this would be too expensive (since there are too many possible positions), but he noticed that the only useful ones are those at the very start and end of memory, and those with an endpoint that is accessed by the program. WifiPlanetUsed as: Division One  Level Three:
This problem consists of two fairly separate parts. In the geometric part, one needs to break the arbitrary polygon into simpler shapes whose area can be more easily calculated. In the second, numerical part, one must determine the number of lattice points inside a simple shape. Let's start with the geometry. One way to measure the area of a polygon to add up, for each edge, the signed area of the trapezium formed by that edge, two vertical sides and the X axis. The area of such a trapezium is 0.5(x2  x1)(y1 + y2). Of course, we're not interested in areas as such, we want to know how many lattice points fall within the polygon. Nevertheless, this will equal the sum of the numbers of lattice points inside each of the simple shapes (subtracting rather than adding when the area formula is negative), provided we are careful about the boundary conditions. We can count the number of lattice points in each vertical strip and sum them up. This will give an expression of the form for some integers a, d and m. If either a or d lies outside the range [0, m), then the integer part can be moved outside of the floor and summed in the usual way for an arithmetic progression. Also, if d = 0, then the summation is trivial. So let us assume that both a lies in [0, m) and d in (0, m). We arrived at this expression by counting vertical strips, but with this assumption, we can also count horizontal strips, and obtain the formula (proving it is left as an exercise to the reader) This is another expression of the original form, so you might think that we're no better off than when we started. However, we've replaced the denominator with a smaller one, in exactly the same way that the Euclidean algorithm efficiently finds the greatest common divisor. We will thus only need to perform a logarithmic number of these transformations before we find that d = 0 and we can terminate. Exercises:

