Match Editorial

Match summary

SRM 371 had a record turnout, hitting the maximum of 1500 registrants well before the end of registration. In Division I, gevak opened the scoring with a lightning-fast submission on the 500. However, Petr returned to his usual form with the fastest submissions on the other two problems, leaving him at the top of the division at the end of coding. The challenge phase was fairly tame, with the top scorers largely unchanged. Petr won the match, with marek.cygan and andrewzta coming second and third respectively.

In Division II, coders faced a 250 that was more difficult to understand than usual, with a very low success rate. At the end of the coding phase, ariel08, zizavino and chinesesonic were the top three, but ariel08 lost all three solutions to challenges and chinesesonic made four unsuccessful challenges, leaving zizavino in first place by a comfortable margin. LostSoul came second and Mikhail_A came a close third.

The Problems

Value	250
Submission Rate	562 / 759 (74.04%)
Success Rate	201 / 562 (35.77%)
High Score	softhacker for 245.76 points (3 mins 44 secs)
Average Score	165.59 (for 201 correct submissions)

Possibly the hardest part of the problem is understanding exactly what was required. Once the problem is understood, implementation is relatively straightforward, the only catch being to watch out for < versus ≤.

Create an N by N table with the number of times each candidate is ranked ahead of each other candidate, initialised to all zeros. Then go through each voter and each table entry, and increment if necessary. At the end, check whether each candidate is a Condorcet winner by checking the appropriate table entries, remembering that the candidate does not have to beat himself. See LostSoul's solution as an example.

Value	500
Submission Rate	348 / 759 (45.85%)
Success Rate	260 / 348 (74.71%)
High Score	vijeth.d for 465.59 points (7 mins 50 secs)
Average Score	305.36 (for 260 correct submissions)

Value	250
Submission Rate	615 / 650 (94.62%)
Success Rate	575 / 615 (93.50%)
High Score	Petr for 246.76 points (3 mins 16 secs)
Average Score	188.73 (for 575 correct submissions)

A simulation that follows the spiral walk will suffice, but it is both slow and relatively complex (nevertheless, Petr's solution was the fastest and used this approach). A simpler solution is to note that after walking around all four sides, the situation is exactly the same except that a layer has been peeled off the outside. This makes for a simple recursion, with the base case occurring when either width or length is 1 or 2:

public class SpiralRoute {
    public int[] thronePosition(int W, int L) {
        if (L == 1) return new int[] {W-1, 0};
        if (L == 2) return new int[] {0, 1};
        if (W == 1) return new int[] {0, L-1};
        if (W == 2) return new int[] {0, 1};
        int[] res = thronePosition(W-2, L-2);
        res[0]++; res[1]++;
        return res;
    }
}

For the more mathematically inclined, there is also a constant-time solution. Suppose width > height, and height is even. The spiral will end with a Westwards section along row height / 2, and it is not hard to see that it will end in column height / 2 - 1. There are three other cases to handle, depending on which dimension is larger, and whether the other dimension is odd or even.

Value	1000
Submission Rate	102 / 759 (13.44%)
Success Rate	68 / 102 (66.67%)
High Score	zizavino for 912.08 points (8 mins 59 secs)
Average Score	664.96 (for 68 correct submissions)

The first step is to identify flat levels of the map, where water is free to flow back and forth. A depth first search is the simplest way to do this: keep track of which cells have been seen, and when you find one that hasn't, recursively find everything adjacent that is at the same height.

Having found the regions, it is simply a matter of placing a pump in every region that is lower than all its neighbours. For every pair of adjacent cells of differing heights, set a flag to indicate that the region owning the higher of the cells does not need a pump. A pump is required for each region that remains unflagged at the end.

Value	500
Submission Rate	508 / 650 (78.15%)
Success Rate	405 / 508 (79.72%)
High Score	gevak for 497.99 points (1 mins 48 secs)
Average Score	376.71 (for 405 correct submissions)

At first glance, this may appear to be the same problem as PlayGame, but the draws in this problem mean that the algorithm needs to be a bit more sophisticated.

Let's suppose you've decided that you're going to lose L games. You might as well lose those games by putting your worst L players against their best L players. For the remaining games, imagine that your players A and B (A > B in skill) respectively play their players X and Y (X ≤ Y in skill). By assumption, B does not lose, so B ≥ Y. It follows that A would beat Y, and B would do at least as well against X as he/she would against Y, so it would not reduce your score to swap A and B. Applying this idea repeatedly, you see that it is optimal, amongst the games that you do not lose, to put your players in the same order as their opponents (strong against strong, weak against weak). And since the order of your players in losing games is irrelevant, there is an optimal solution which involves simply rotating your ordered list of players when matching it to their ordered list of players.

The only remaining problem is to determine the optimum number of games to lose. This can be handled simply by trying all possibilities, in other words, all rotations of our players.

gevak chose to use heavy machinery in his solution: he took the scores of every potential game as edge weights on a bipartite graph, and used a pre-coded min-cost flow implementation to find the optimum assignment. andrewzta's solution also takes a heavy approach, using dynamic programming to find the best way of matching your best P players against their best Q players.

Value	900
Submission Rate	155 / 650 (23.85%)
Success Rate	61 / 155 (39.35%)
High Score	Petr for 785.32 points (11 mins 11 secs)
Average Score	491.01 (for 61 correct submissions)

Let's start by getting a solution that is correct but slow. Find a contestant that is not known to be behind any other, assume he/she is in first, and count the number of ways to order the remaining contestants ignoring the first one (recursively). Repeat with each possible winner, and you will have an answer. However, this is O(N!), which is far too slow. The first optimisation is to note that the number of ways to order any subset is always the same, regardless of the order of previous contestants. Thus, we can memoise on the subset to the ordered. This requires O(2^N) time and memory — still too slow.

The final twist is that although there may be up to 30 contestants in total, there are at most 16 in any component of the dependency graph. The algorithm may be applied separately to each component. If components with sizes M₁ and M₂ can be ordered in C₁ and C₂ ways respectively, then their union can be ordered in C₁C₂.c(M₁ + M₂, M₁) different ways, where c(n, r) is the number of ways to choose r out of n.

An alternative approach is to ignore components, but apply the DP keeping track of only which runners from first have been placed, together with the total number of runners placed. The insight is that if two runners do not appear in first and can both be placed, then they are interchangeable because placing them has no effect on which runners may be placed later on. See ploh's solution for a nice implementation of this approach.