Qualification Round 3 September 12, 2006 Match summaryChinese coders dominated this round, getting four spots in the top 6. kalakaba got the top spot by more than 350 points. gy was second, closely followed by Matei and pure_. modenl was fifth, only 3 points ahead of daisy in sixth place. The top 450 coders got their tickets to Online rounds, completing the list of 1500 qualifiers. Good luck to all of them on the way to San Diego! The ProblemsUsingStatsUsed as: Division One  Level One:
The solution can be split in two parts  computing the missing element and finding the median of the resulting set. The missing element can be found using the value of the mean. If the input array contains N elements, then the sum of all elements of the array with the missing element must be equal to (N + 1) * mean (since the mean is the sum of all elements divided by the number of elements). When we found the missing element, we add it to the array, sort the resulting array and return the middle element (Java implementation of this algorithm follows): public int getMedian(int[] vals, int mean) { int N = vals.length + 1; int[] v = new int[N]; int sum = 0; for (int i = 0; i < N  1; i++) sum += (v[i] = vals[i]); v[N  1] = N * mean  sum; Arrays.sort(v); return v[N / 2]; }CheckersBoard Used as: Division One  Level Two:
This problem only required an implementation of the approach described in the statement, though the coding could be made much easier by several tricks. To solve this problem, we count the number of black and white moves separately and return the sum of these values. Since white and black pieces move in different directions, we reverse the board before computing the answer for white pieces: public int numMoves(String[] board) { String[] s = new String[8]; for (int i = 0; i < 8; i++) s[i] = board[7  i]; return count(board, 'B') + count(s, 'W'); // see the implementation of method count later } To compute the number of moves for any color, we just iterate through all cells of the board. For any cell, which is occupied by a piece of the proper color, we check if it can slide or jump. We check two diagonal directions, for each of them checking if the piece can jump or slide in this direction. To simplify coding, we create an additional method isEqual, which checks whether the specified cell is occupied by the specifed piece (or empty). Also, this method will check for the cell being inside the board's bounds, to free us from checking this at every line of the code. Having this method, the implementation becomes easy: boolean isEqual(String[] data, int r, int c, int ch) { return (r >= 0 && c >= 0 && r < 8 && c < 8 && data[r].charAt(c) == ch); } int count(String[] data, char our) { int slide = 0; int jump = 0; for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) if (data[i].charAt(j) == our) { if (isEqual(data, i + 1, j  1, ' ')) slide++; if (isEqual(data, i + 1, j + 1, ' ')) slide++; if (isEqual(data, i + 1, j  1, 'W' + 'B'  our) && isEqual(data, i + 2, j  2, ' ')) jump++; if (isEqual(data, i + 1, j + 1, 'W' + 'B'  our) && isEqual(data, i + 2, j + 2, ' ')) jump++; } return (jump == 0) ? slide : jump; }MixedUpPrimes Used as: Division One  Level Three:
The very first thing to do when solving this problem is to implement the test for primality: boolean isPrime(int p) { if (p == 2) return true; if (p % 2 == 0  p < 3) return false; for (int i = 3; i * i <= p; i += 2) if (p % i == 0) return false; return true; } Since the input array contains only six elements, we can build all possible numbers which can be constructed using the input values. To do this, we implement a recursive method that returns the set of numbers which can be constructed using some subset of the input values. This method will try to split the input into two subsets in all possible ways. For each such split, we recursively run our method on both subsets, combining the results we get (i.e., applying all possible arithmetic operations). We aggregate all values for all splits into one big set, which will be returned from the method: set First we run method generate on the whole input set to receive set S, then we check each number in S for primality, finding the smallest and the biggest of them. See Matei's solution for a complete implementation of this approach. 
