Tuesday, November 20, 2007 Match summaryIn division 1, the midmatch 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 ProblemsTwoRotationCypherUsed as: Division Two  Level One:
There are no tricks here: just process the string one character at a
time, applying the rules. If a character 3xP053r submitted a short but clear implementation. TrueStatementsUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 Used as: Division Two  Level Three:
The TowersofHanoi 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:
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 subproblems above applies, and how many moves into that subproblem 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. SolvePolynomialUsed as: Division One  Level Two:
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} = 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 nonzero value for a_{0}. Now let us write the polynomial as P(x) = a_{0} + xQ(x). It's clear that the second term is always a multiple of x, so for P(x) to be zero, a_{0} must be a multiple of x as well. A loop up to the square root of a_{0} 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_{0} = xQ(x). If x does not divide y  a_{0} then the answer is of course no; otherwise, it is equivalent to asking whether Q(x) = (y  a_{0}) / 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^{32} or 2^{64} (by just ignoring overflow in 32 or 64bit 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^{9})), 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. TwistyPassagesUsed as: Division One  Level Three:
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
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 floodfill 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 floodfilling. 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 
