JOIN
 Match Editorial
2006 TopCoder Collegiate Challenge
Qualification Round 2

September 9, 2006

## Match summary

Despite 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 Problems

ProseFlip
Used as: Division One - Level One:
 Value 250 Submission Rate 667 / 719 (92.77%) Success Rate 651 / 667 (97.60%) High Score scotttiger for 249.77 points (0 mins 52 secs) Average Score 226.36 (for 651 correct submissions)

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:
 Value 500 Submission Rate 313 / 719 (43.53%) Success Rate 147 / 313 (46.96%) High Score lews for 490.56 points (3 mins 57 secs) Average Score 280.50 (for 147 correct submissions)

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:
 Value 1000 Submission Rate 94 / 719 (13.07%) Success Rate 32 / 94 (34.04%) High Score danielp for 705.51 points (20 mins 13 secs) Average Score 540.76 (for 32 correct submissions)

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.

For the second part of the problem, we need to figure out the least number of swaps to go from one tableau to another. To do this, we view a 4x4 tableau as a list of 16 numbers, and determine the permutation that sends one tableau into the other. That is, we see which position in the second list the first list element is sent to, then the second element, and so forth. For example, suppose we were dealing with the following lists (made shorter for clarity):

```    {3,4,2,1}     {2,4,1,3}
```
Then our permutation would be as follows:
```    1 -> 4, 2 -> 2, 3 -> 1, 4 -> 3
```
Once we have our permutation, we need to break it down into individual swaps. This is done by representing the permutation in disjoint-cycle notation. The above example has 1 cycle of length 3, and another of length 1. A cycle of length n requires n-1 swaps. So, summing over each cycle, we are able to compute the swap distance between two tableaux.

By brett1479
TopCoder Member