Match Editorial

The first online elimination round in the TCCC caused no major upsets, as all the high seeds easily moved on. The problem set, containing three chess related problems, was fairly easy (compared to regular division 1 SRM's), and 22 participants solved all the problems. This number would have been much greater, had the last problem not contained a nasty (unintentional) surprise, causing many solutions to fail in the challenge phase and system tests.

After the challenge phase, krijgertje had a clear lead thanks to an impressively fast submission on the last problem. However, as was the case with many other hard submissions, it went down in the system tests, and instead veteran John Dethridge became top scorer, closely followed by Per.

The Problems

Value	325
Submission Rate	357 / 425 (84.00%)
Success Rate	320 / 357 (89.64%)
High Score	marian for 308.97 points (6 mins 32 secs)
Average Score	220.01 (for 320 correct submissions)

The easiest way to solve this problem is to not slavishly follow the algorithm in the problem statement, but to realize that we only need to do one single sort (instead of one for every distinct number of points).

If one uses C++, the sorting can be done using the pair<> template (see Per's solution). A more structured implementation is to create a class Player containing the data fields score, rating and index. This class should also implement the interface Comparable (Java) / IComparable (C#), which means that you write a method for the class which determines the order of two elements. If you don't know how to do this in your language, you should really learn it, since it's something that you have to do quite often in "real life" programming. For a Java implementation, see Cosmin.ro's solution. For a C# implementation, see DimaGer's solution.

Once the elements are sorted, we find the top scorers by looping from the top of the sorted list in steps of 2 until we reach a player with a lesser score than the first. An inner loop loops through half of these, assigning the appropriate opponents.

Value	450
Submission Rate	303 / 425 (71.29%)
Success Rate	283 / 303 (93.40%)
High Score	Im2Good for 443.55 points (3 mins 26 secs)
Average Score	365.01 (for 283 correct submissions)

When dealing with directions (and this happens almost once every SRM/tournament round), I recommend that you always create arrays containing the x- and y-delta values. There is really no reason not to do this; the code gets shorter, and much less error prone compared to copy-and-paste code (the latter is close to obfuscation in my eyes!). Usually the directions are limited to up, down, left and right (with or without diagonals). Here we have a chess knight's direction, so the delta arrays become like this:

int dx[] = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[] = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 };

Note that the second array is the same as the one above except that it's just two steps; knowing this both speeds things up and makes it easier to avoid mistakes.

Now for the actual problem. One can solve the problem either with dynamic programming or memoization; I will describe the DP solution here. The idea is to keep track for each number of moves the probability that the knight will be on a certain square. Initially the probability is 1 (100%) that it will be on the start square and 0 on all other squares. After one move, the probability is 0.125 that it will be on any of the eight squares a knight distance away from the start, and 0 on all the other squares. If any of these 8 squares is outside the board, it's simply ignored - it doesn't affect the probability for any of the other squares.

Generally, the probability that the knight will be on a certain square after n moves is the sum of the probabilities of it being on the 8 squares a knight distance away after n - 1 moves, divided by 8 (this is basic probability math). By first determining the probability of the knight being on all 64 squares after 1 move, then 2 moves etc, we get an efficient algorithm:

for(int i=1; i<=n; i++) // n = number of moves we want the answer for
    for(int x=0; x<8; x++)
        for(int y=0; y<8; y++) {
            double prob = 0.0;
            for(int d=0; d<8; d++) {
                if (x+dx[d] >= 0 && x+dx[d] < 8 &&
                    y+dy[d] >= 0 && y+dy[d] < 8)
                    prob += boardprob[i-1][y+dy[d]][x+dx[d]] / 8.0;
            }
            boardprob[i][y][x] = prob;
        }

The answer is then simply the sum of the knight being on the 64 squares after n moves.

Value	1000
Submission Rate	83 / 425 (19.53%)
Success Rate	23 / 83 (27.71%)
High Score	John Dethridge for 772.84 points (16 mins 26 secs)
Average Score	542.00 (for 23 correct submissions)

Since there can be 20 members in a team, trying all permutations is not feasible (as a general rule in TopCoder, you probably don't want to try all permutations in a set if the size of the set is greater than 10 or 11), so something else must be done.

Let us for the moment not consider the restriction in the ordering (i.e., that certain player must play before others depending on the rating difference). The idea is to split the problem into several smaller sub problems, solve those, and then merge those answers to get the answer to the original problem. The split consists of trying all n players on position 0 in the permutation (for each player we can calculate the expected score according to the given formula) and the sub problem consists of solving the same problem for the n - 1 players left.

If this is done naively without caching, we will end up testing all permutations. However, note that the input parameters to the sub problem is a set of players, namely the set of the players left. We do not have to know which position in the permutation we are at; this can be deduced from the set of players left (if there originally was 8 players, and we now have 6 left, we are at position 2). There are 2ⁿ sets of n players, which for n = 20 is about 1 million. Hence the input domain for the sub problem is small enough that we can cache the results ("memoize"). Some pseudo code:

double solve(int setOfPlayers)
{
    if setOfPlayers is empty, return 0
    if cache contains setOfPlayers
        return cache[setOfPlayers]
    int permutationPosition = totalNumberOfPlayers - size of setOfPlayers
    double best = -INFINITY
    foreach player in setOfPlayers {
        double e = expectedScore(player,opponent[permutationPosition])
        e = e + solve(setOfPlayers - player)
        best = max(best,e)        
    }
    cache[setOfPlayers] = best;
    return best;
}

I recommend using a bitmask for keeping track of the set of players. This also makes the next step easier: implementing the ordering restriction. The best way to do this is to precalculate for each player which other players (i.e. set of players) must appear before him in the permutation. That is, if player i has rating 2200, and lim is 100, then the set of players with rating greater than 2300 should be stored in pre[i]. When looping through all players in the code above, we can check if the current player can be at permutationPosition by verifying that none of the players in the "pre-set" is left among setOfPlayers. This check can be done with a bitwise-and operation if we use bitmasks.

The running time for this algorithm is O(2ⁿ * n). It turns out that one can get a O(2ⁿ * n²) solution (with two loops in the recursion above) to run fast enough as well, but only barely so. What caught many submissions though, is that you should precalculate the expectedScore function above, since the pow function in the math library (for both C++ and Java) is quite slow - no one who used it without precalculation passed the system tests (one solution that did pass used the less known pow10 instead, and apparently that was fast enough).

The lesson to learn from this is that you should always test your solution with the worst case, something apparently a lot coders didn't.