Match Editorial

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

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;
    }

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()];
    }
}

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}

    1 -> 4, 2 -> 2, 3 -> 1, 4 -> 3