Saturday, October 13, 2007 Match summarySRM 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 lightningfast 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 ProblemsCondorcetVotingUsed as: Division Two  Level One:
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. SpiralRouteUsed as: Division Two  Level Two: Used as: Division One  Level One:
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[] {W1, 0}; if (L == 2) return new int[] {0, 1}; if (W == 1) return new int[] {0, L1}; if (W == 2) return new int[] {0, 1}; int[] res = thronePosition(W2, L2); res[0]++; res[1]++; return res; } } For the more mathematically inclined, there is also a constanttime 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. FloodReliefUsed as: Division Two  Level Three:
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. ChessMatchupUsed as: Division One  Level Two:
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 precoded mincost 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. RaceOrderingUsed as: Division One  Level Three:
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_{1} and M_{2} can be ordered in C_{1} and C_{2} ways respectively, then their union can be ordered in C_{1}C_{2}.c(M_{1} + M_{2}, M_{1}) 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. 
