Match Editorial

Match summary

In division 1, the mid-match division summary had a familiar sight: Petr sitting at the top. However, coders were faced with a 500 that had a tempting but incorrect solution, and a 1000 with some subtleties that were not exposed by system tests, and by the end of the coding phase, Eryx was in the lead. The 500 proved a ripe opportunity for challenges, and by the end of system testing, only four 1000's had survived. gawry won the match and was the only contestant to solve all three problems, followed by krijgertje and JongMan, each with the 250 and 1000. asaveljevs was the only other coder to solve the 1000.

In division 2, the medium problem was simple to code but perhaps less simple to understand, while the hard problem was fairly challenging. Li_Mon won the match with a very quick solution to the hard, while newcomers ausgezeichnet and malekzadeh placed 2nd and 3rd.

The Problems

Value	250
Submission Rate	582 / 717 (81.17%)
Success Rate	551 / 582 (94.67%)
High Score	Delusion for 248.43 points (2 mins 15 secs)
Average Score	170.51 (for 551 correct submissions)

There are no tricks here: just process the string one character at a time, applying the rules. If a character c is not a space, then it is in the first group if c < 'a' + firstSize. In this case, it is replaced with 'a' + (c - 'a' + firstRotate) % firstSize. If it is in the second group, the code is similar but 'a' is replaced by 'a' + firstSize, firstRotate by secondRotate, and firstSize by 26 - firstSize.

3xP053r submitted a short but clear implementation.

Value	500
Submission Rate	512 / 717 (71.41%)
Success Rate	275 / 512 (53.71%)
High Score	Effect for 497.28 points (2 mins 6 secs)
Average Score	401.33 (for 275 correct submissions)

Value	250
Submission Rate	537 / 540 (99.44%)
Success Rate	451 / 537 (83.99%)
High Score	Soultaker for 249.50 points (1 mins 16 secs)
Average Score	230.42 (for 451 correct submissions)

Trying to make sense out of all the statements and from that work out which are true is a recipe for a complicated and probably incorrect solution. Instead, it is best to work backwards: take a guess at how many statements are true, then check if you're right. In fact, you'll find that a guess of T statements being true will fit the facts if and only if there are T statements that say Exactly T of these statements are true. All that is left is to try all possible values of T (0 to 50) and return the largest one that fits, or -1 if none of them do.

Value	1000
Submission Rate	35 / 717 (4.88%)
Success Rate	17 / 35 (48.57%)
High Score	Li_Mon for 715.68 points (19 mins 37 secs)
Average Score	473.14 (for 17 correct submissions)

The Towers-of-Hanoi problem is a classic problem used to illustrate recursion, and the variation in this problem is no exception. Let's start by working out the optimal strategy, as a recursive procedure. If the largest disc N is already in the right place, then it can be completely ignored. Otherwise, suppose the largest disc needs to move from A to C. We can do this as follows:

1. Move discs 1 to N - 1 to peg B.
2. Move disc N disc to peg C.
3. Move discs 1 to N - 1 to their target positions.

Now we need to turn this into an algorithm to find the state after moves moves. To do this, we just need to work out which of the recursive sub-problems above applies, and how many moves into that sub-problem we are. Since step 1 above will take 2^{N - 1} - 1 moves and step 2 takes exactly one move, this is not too difficult.

The only remaining complication is that when we are dealing with step 3 above, discs 1 to N - 1 are on peg B instead of peg A. This is easily handled by swapping the labels of pegs A and B in the target string, and restoring the original labels on the return value.

Value	500
Submission Rate	316 / 540 (58.52%)
Success Rate	43 / 316 (13.61%)
High Score	gawry for 420.18 points (12 mins 53 secs)
Average Score	249.97 (for 43 correct submissions)

There are two parts to this problem: identifying candidate roots, and testing which of them are actually roots. To start off with, if a₀ = 0 then we can note that zero is a solution and divide the whole polynomial by x. We can keep doing this until we get a non-zero value for a₀. Now let us write the polynomial as P(x) = a₀ + xQ(x). It's clear that the second term is always a multiple of x, so for P(x) to be zero, a₀ must be a multiple of x as well. A loop up to the square root of a₀ is a sufficient way to find all the factors, although some coders computed a complete factorisation into primes.

Next, we need to test these candidate roots. The obvious approach is simply to evaluate the polynomial for each candidate and check whether it comes out as zero. However, to make this calculation accurate, it is necessary to use big integers, and this makes the cost of testing each candidate quadratic in n. Since there can be up to 2688 candidates, this is too expensive.

A better alternative is to ask whether P(x) = 0, or more generally whether P(x) = y, without actually computing P(x). This is equivalent to asking whether y - a₀ = xQ(x). If x does not divide y - a₀ then the answer is of course no; otherwise, it is equivalent to asking whether Q(x) = (y - a₀) / x. This is a question of the same form, but of lower degree, so it can be answered recursively. See Smylic's solution for an implementation of this approach.

Most coders just evaluated the polynomial modulo some number, and hoped that it would never equal a multiple of that number. Variations included working implicitly modulo 2³² or 2⁶⁴ (by just ignoring overflow in 32- or 64-bit integers), modulo some prime, and modulo each of a collection of primes (which is equivalent to working modulo their product, but without the headaches of big integers). This is incorrect unless the modulus is astronomically large (larger than the maximum possible value of P(10⁹)), but there is no way to check for every possibility in the system tests. On the other hand, it made the challenge phase more important and more lucrative than usual, since it is relatively easy to construct a challenge case once you have the modulus.

Value	1000
Submission Rate	31 / 540 (5.74%)
Success Rate	4 / 31 (12.90%)
High Score	krijgertje for 592.78 points (27 mins 58 secs)
Average Score	508.42 (for 4 correct submissions)

The key to the problem is to consider each possible orientation of each room as a separate entity; call this an oriented room. Two oriented rooms A and B can be told apart if

• they are of different types (different number of passages); or
• corresponding passages from A and B lead to oriented rooms that can be told apart.

This definition is recursive and it is not clear where to start, since the definition may cycle back on itself. The trick is to start by assuming that oriented rooms of the same type are all indistinguishable, then use a flood-fill to propagate information about oriented rooms that are distinguishable. One way to formalise this is to see pairs of oriented rooms as nodes on a graph, the first condition as seed nodes, and the second condition as edges for flood-filling.

For it to be possible for two rooms to be told apart (regardless of orientation), it must be possible to tell them apart at any orientation. An easy mistake to make is to decide that isolated rooms (with zero passages, and thus perhaps zero orientations) can be told apart, whereas of course any sealed room looks the same as any other.

Implementing all this as described should pass system tests (as seen with gawry's solution), but it can be made more efficient. A simple optimisation is to note that rotating both rooms in a pair of oriented rooms does not really change anything, since the same pairs of passages will correspond. Thus the states in the graph can be described by two rooms and their relative orientation, rather than two rooms and two absolute orientations.

krijgertje used a variation on this approach. Initially, he marked every room as being of the same class. Then in each iteration, he looked at the classes of all the rooms connected to each room, and used this to generate a signature for the room (after normalising for orientation). Rooms that were of the same class but with different signatures are then labelled as being different classes. The algorithm terminates when no more relabelling is possible, and rooms are distinguishable if and only if they are of different classes.