Saturday, July 21, 2007 Match summaryIn Division 1, ACRush made a strong start with the first submission on the 500, but fell behind as he was overtaken by competitors submitting fast 1000s. At the start of the challenge phase, Eryx was in first with a very fast submissions on the 250 and 1000. Unfortunately, his 500 failed system testing. This left andre.sp as the surprise winner and Minilek in second place, with reds Yarin, liympanda and domino rounding out the top 5. In Division 2, coders faced a harder than usual hard problem. Many of the submissions were successfully challenged, and system tests took down many of the rest. Only three submissions survived, and these put nu4nu, bozzball and Ikki in the top places. The ProblemsCricketScoresUsed as: Division Two  Level One:
Cricket seems a simple enough game to those of us who live in cricketplaying nations, but trying to explain it to the uninitiated turns out to be quite complex. Once you've understood the basics of the game, the coding is straightforward. You need a twoelement array to hold the two scores, and an index, which is either 0 or 1, to keep track of which batsman is going to face the next ball. After each ball, you add the runs to the appropriate array entry, then flip this variable (x = 1  x works nicely) if the number of runs was odd. You also flip it (possibly for the second time) after every sixth ball. DriveFailuresUsed as: Division Two  Level Two: Used as: Division One  Level One:
It is possible to solve this problem with dynamic programming, but the small constraints make it unnecessary. Simply consider every possible subset of the drives, and compute the possibility that exactly that subset is working. For example, the probability that drives 0, 1 and 3 out of 5 drives will work is (p0)(p1)(1p2)(p3)(1p4). Then add each probability to the appropriate element of the output array. UTF8DecodeUsed as: Division Two  Level Three:
Wikipedia has a nice page with lots of information about UTF8. One of the facts that can be found is that certain bytes never appear in a valid UTF8 file: 0xC0 and 0xC1 are illegal because they would start a twobyte sequence for a value that should be encoded with one byte, and 0xF5 and above would encode values greater than 0x10FFFF. Any value from 0x00 to 0x7F is a valid onebyte character, and any value from 0xC2 to 0xF4 is a valid start of a multibyte character, the rest of whose bytes must be in the range 0x80 to 0xBF. Unfortunately, this is not the end of the story, as we still need to take care of
This is the exact approach taken by nu4nu, but no other competitor succeeded with it. Rather than working out the rules, it is easier to write general code that determines whether a byte is valid. Suppose we have some bytes that we have accepted but not yet formed into a complete character, and we are examining a candidate byte. We can provisionally add this byte to the sequence, then check whether it is a prefix of a valid sequence. bozzball's elegant solution checks for the smallest and largest values that could be built from the partial character we have, and checks whether that range overlaps the valid range for the sequence length. Ikki's solution generates the encodings of all 1114112 characters in advance, then uses that to check whether a partial character is a prefix of any full character. He managed to make it fast enough using a linear search, but a feature of UTF8 is that the byte sequences are in lexicographical order, making it possible to binary search the list. CropCirclesUsed as: Division One  Level Two:
There are two ways in which the number of circles may be lower than expected: three points may lie on a straight line (and hence fail to form a circle), or four or more points may lie on the same circle. Armed with the cross product, it is a simple matter to identify straight lines. Let's see how to count the number of unique circles from those that remain. Let each circle be defined by the first (smallest index) three points that lie on it, in order. In order to check if an ordered triplet is in fact a defining triplet, it suffices to check whether these three points are concyclic with any point before the last of the three. So once we have a method for checking whether four points are concyclic, we can proceed. The circumcentre of a triangle can be found by taking the intersection of two perpendicular bisectors. So a straightforward approach is to use this to find the center of three of the four points, then of a different subset of three, and check if they coincide. The constraints are low enough that no fancy integer arithmetic is required. A more compact solution found by several competitors (see liympanda's solution for a clean implementation that works in integer arithmetic) is based on Ptolemy's theorem: ABCD is a cyclic quadrilateral if and only if AB.CD + AD.BC = AC.BD. BubbleSortIterationsUsed as: Division One  Level Three:
Start by considering just the smallest element: on each iteration of the bubblesort, it will move one place toward the front, until it is in the first position. So the number of iterations required for it is simply its original index. Now consider some arbitrary intermediate order, and the effect of running an iteration over it. The smallest element moves one place to the left, but it has no effect on what happens to the other elements  they end up in the same order as if the smallest element wasn't there. The number of iterations required for the secondlargest element is thus its index once the smallest element is removed. Put another way, it is the number of elements that are both larger than it and before it in the original array. The same logic can be repeated to remove each successive element in turn, and the same rule applies: the number of iterations required to correctly position X is the number of elements larger than X that occurred before X. The number of iterations required to sort the whole array is simply the largest of these values. This can be computed in O(N.log N) time using either a clever algorithm or a clever data structure, which was my intended solution, but many competitors noticed a simplification and makes this much easier to code. Consider the rightmost item which required the largest number of iterations. There cannot be any number after it which is no greater than it smaller, since otherwise that number would have at least as many larger numbers before it, and it would be better. This means that every time this item is swapped, which is every iteration, it will move to the left. The number of iterations is thus the distance between its initial and final positions. Thus, the answer is simply the maximum movement towards the front of any element. 
