Match Editorial

Match summary

In 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 Problems

Value	250
Submission Rate	533 / 654 (81.50%)
Success Rate	505 / 533 (94.75%)
High Score	bozzball for 246.31 points (3 mins 29 secs)
Average Score	185.84 (for 505 correct submissions)

Cricket seems a simple enough game to those of us who live in cricket-playing 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 two-element 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.

Value	500
Submission Rate	263 / 654 (40.21%)
Success Rate	237 / 263 (90.11%)
High Score	lihuansen for 496.71 points (2 mins 19 secs)
Average Score	320.69 (for 237 correct submissions)

Value	250
Submission Rate	518 / 551 (94.01%)
Success Rate	512 / 518 (98.84%)
High Score	JongMan for 248.94 points (1 mins 51 secs)
Average Score	211.81 (for 512 correct submissions)

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)(1-p2)(p3)(1-p4). Then add each probability to the appropriate element of the output array.

Value	1000
Submission Rate	14 / 654 (2.14%)
Success Rate	3 / 14 (21.43%)
High Score	Ikki for 586.69 points (28 mins 29 secs)
Average Score	538.59 (for 3 correct submissions)

Wikipedia has a nice page with lots of information about UTF-8. One of the facts that can be found is that certain bytes never appear in a valid UTF-8 file: 0xC0 and 0xC1 are illegal because they would start a two-byte 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 one-byte character, and any value from 0xC2 to 0xF4 is a valid start of a multi-byte 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

• Values over 0x10FFFF. If the first byte is 0xF4, then the next byte must be at most 0x8F.
• Overlong sequences, which are values encoded using more bytes than they should (e.g., values less than 0x7FF encoded using 3 or 4 bytes). If the first byte is 0xE0, then the next byte must be at least 0xA0, and if the first byte is 0xF0, then the next byte must be at least 0x90.

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 UTF-8 is that the byte sequences are in lexicographical order, making it possible to binary search the list.

Value	500
Submission Rate	343 / 551 (62.25%)
Success Rate	126 / 343 (36.73%)
High Score	Abednego for 467.30 points (7 mins 37 secs)
Average Score	302.45 (for 126 correct submissions)

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.

Value	1000
Submission Rate	117 / 551 (21.23%)
Success Rate	100 / 117 (85.47%)
High Score	{dano} for 929.98 points (7 mins 54 secs)
Average Score	641.91 (for 100 correct submissions)

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 second-largest 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.