Get Time
statistics_w  Match Editorial
SRM 378
Tuesday, November 20, 2007

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

TwoRotationCypher rate it discuss it
Used as: Division Two - Level One:
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.

TrueStatements rate it discuss it
Used as: Division Two - Level Two:
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)
Used as: Division One - Level One:
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.

HanoiState rate it discuss it
Used as: Division Two - Level Three:
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 2N - 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.

SolvePolynomial rate it discuss it
Used as: Division One - Level Two:
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 a0 = 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 a0. Now let us write the polynomial as P(x) = a0 + xQ(x). It's clear that the second term is always a multiple of x, so for P(x) to be zero, a0 must be a multiple of x as well. A loop up to the square root of a0 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 - a0 = xQ(x). If x does not divide y - a0 then the answer is of course no; otherwise, it is equivalent to asking whether Q(x) = (y - a0) / 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 232 or 264 (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(109)), 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.

TwistyPassages rate it discuss it
Used as: Division One - Level Three:
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.

By bmerry
TopCoder Member