Qualification Round 2 September 9, 2006 Match summaryDespite the 763 registrants for qualification round 2, the competition went very smoothly. With 32 competitors solving the nontrivial hard problem, it is clear that the upcoming rounds will be exciting. anrieff won the match by a comfortable margin. Min,lu, although 70 points behind anrieff, finished approximately 140 points ahead of the rest of the competitors. Good luck to all competitors in the upcoming rounds. The ProblemsProseFlipUsed as: Division One  Level One:
Like many division 2 easy problems, the solution to this problem amounted to writing a few loops. Here we simply transpose the given character matrix by swapping indices as we loop. Java code follows: public String[] getFlip(String[] text) { int R = text.length, C = text[0].length(); String[] ret = new String[C]; for (int c = 0; c < C; c++) { ret[c] = ""; for (int r = 0; r < R; r++) ret[c] += text[r].charAt(c); } return ret; }CheapestTabComplete Used as: Division One  Level Two:
Here we have a standard dynamic programming problem. Since we cannot delete characters, at any point we must have some prefix of the target string in the buffer. Thus the current state is simply an integer describing the length of the buffer. From a particular state, our potential moves include entering the next character or pressing tab some number of times. Linearly filling in the "DP Table," we quickly arrive at the cheapest key cost for the entire target string. Java code follows: public int getFewest(String[] names, String w) { Arrays.sort(names); int[] best = new int[51]; Arrays.fill(best,1000); best[0] = 1; for (int a = 0; a < w.length(); a++) { best[a+1] = Math.min(best[a+1],best[a]+1); int cnt = 0; String curr = w.substring(0,a); for (String s : names) { if (!s.startsWith(curr)) continue; cnt++; if (!w.startsWith(s)) continue; best[s.length()] = Math.min(best[s.length()],best[a]+cnt); } } return best[w.length()]; } }QuickTableau Used as: Division One  Level Three:
This problem breaks down into two fairly distinct tasks. The first is efficiently generating all
Young tableaux. The second is computing the swap cost of going from one tableau to another. For
the first part, we recursively fill in a 4x4 array in numeric order. Since at any point we are
inserting the next lowest number, there are a limited number of slots where we can stick it. More
specifically, the spot we insert the value cannot have any empty spaces above it or to its left. For
example, there is only one place the value 1 can go, then only two places for 2, and only three
places for 3 once the 2 is placed. A potential speedup can be achieved by alternating between
placing the lowest remaining number and the highest remaining number.
{3,4,2,1} {2,4,1,3}Then our permutation would be as follows: 1 > 4, 2 > 2, 3 > 1, 4 > 3Once we have our permutation, we need to break it down into individual swaps. This is done by representing the permutation in disjointcycle notation. The above example has 1 cycle of length 3, and another of length 1. A cycle of length n requires n1 swaps. So, summing over each cycle, we are able to compute the swap distance between two tableaux. 
