Match Editorial

Match summary

Online Round 3 of the 2007 TopCoder Collegiate Challenge brought us something to think, something to code and a huge space for possible bugs. What else does a top coder need on a Saturday morning (or day, or night)? As a result, the cutoff was quite low - 175 points - so a fast, correct solution on the easy or 3.5 challenges were enough to advance.

The round was won by Petr with a really improbable score on the hard problem, followed by pashka, marek.cygan, kalinov and ACRush.

The Problems

Value	250
Submission Rate	293 / 296 (98.99%)
Success Rate	136 / 293 (46.42%)
High Score	JBoy for 245.05 points (4 mins 3 secs)
Average Score	197.91 (for 136 correct submissions)

This problem can be solved with a greedy algorithm. Mice are running away from the cat, so each of them is available for the first a[i] seconds only. It's always better to catch the mouse that will be available for less time with the hat that need less time to rest.

The code follows:

    public int maxMiceCount(int[] pos, int[] speed, int d, int[] rest) {
        int n = pos.length;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = 0;
            while (pos[i] <= d) {
                a[i]++;
                pos[i] += speed[i];
            }
        }
        Arrays.sort(a);
        int m = rest.length;
        Arrays.sort(rest);
        int t = 0;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (a[j] > t) {
                    res++;
                    a[j] = -1;
                    t += rest[i];
                    break;
                }
            }
        }
        return res;
    }

Value	500
Submission Rate	238 / 296 (80.41%)
Success Rate	79 / 238 (33.19%)
High Score	Petr for 423.69 points (12 mins 31 secs)
Average Score	282.85 (for 79 correct submissions)

This problem is quite technical. Coders need to find the easiest way to determine if the figure can be formed by three stripes. It is important in such problems to make the code short and easy and to avoid big copy-paste parts.

One easy way to do this is to use back tracking algorithms. First find the leftmost topmost cell of the bacteria. This cell should be the end of a stripe, horizontal or vertical. The stripe should be as long as possible. We can choose one of the variants, mark cells covered by the stripe and start back tracking on the remaining cells. Then unmark the cells, choose another variant and check it in the same way.

The code follows:

    int n;
    int m;
    boolean[][] a;
    boolean[][] b;
    int[][] c;

    public int howMany(String[] photo) {
        n = photo.length + 2;
        m = photo[0].length() + 2;
        a = new boolean[n][m];
        b = new boolean[n][m];
        c = new int[n][m];
        for (int i = 0; i < photo.length; i++) {
            for (int j = 0; j < photo[i].length(); j++) {
                a[i + 1][j + 1] = photo[i].charAt(j) == '*';
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j]) {
                    clear(b);
                    dfs(i, j);
                    if (bt(0)) {
                        res++;
                    }
                }
            }
        }
        return res;
    }

    private boolean bt(int q) {
        if (q > 3) return false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (b[i][j] && c[i][j] == 0) {
                    int ii = i;
                    while (b[ii][j]) {
                        c[ii][j]++;
                        ii++;
                    }
                    if (bt(q + 1)) return true;
                    ii = i;
                    while (b[ii][j]) {
                        c[ii][j]--;
                        ii++;
                    }
                    int jj = j;
                    while (b[i][jj]) {
                        c[i][jj]++;
                        jj++;
                    }
                    if (bt(q + 1)) return true;
                    jj = j;
                    while (b[i][jj]) {
                        c[i][jj]--;
                        jj++;
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private void clear(boolean[][] a) {
        for (boolean[] b : a) {
            Arrays.fill(b, false);
        }
    }

    private void dfs(int i, int j) {
        if (!a[i][j]) return;
        a[i][j] = false;
        b[i][j] = true;
        dfs(i - 1, j);
        dfs(i + 1, j);
        dfs(i, j - 1);
        dfs(i, j + 1);
    }

Value	1000
Submission Rate	30 / 296 (10.14%)
Success Rate	4 / 30 (13.33%)
High Score	Petr for 819.75 points (13 mins 58 secs)
Average Score	578.23 (for 4 correct submissions)

Let's call the substrings we need to find the "interesting substrings." It's shorter then "strings that belong to at least one such pair."

First we need to understand that all substrings of an interesting substring are interesting too. So, for each i there is a t[i], the longest interesting substring starting from i-th character. All other interesting substrings starting from the i-th character are prefixes of t[i].

How to calculate t[i]? Each interesting substring has a pair. Let's find it. We can check all pairs (i, j) and calculate r[i][j], the maximal length of matching substrings, starting from i-th and j-th characters. This can be done easily using n^3 time, but it's too much. We can make it faster using this simple idea: if we know the number of characters that differ in substrings [i..i+k] and [j..j+k], then we can calculate this number for substrings [i+1..i+k] and [j+1..j+k]. So we can use the value of r[i][j] to calculate the value of r[i+1][j+1] and make all calculations using n^2 time. Look at kalinov's solution for an implementation of this idea.

Now finally we need to count the number of different interesting substrings. This is a problem too, because we have too many substrings, and we cannot just put them into the hash set.

First solution (correct): All interesting substrings are prefixes of t[i]. Sort t[i] lexicographically, their common prefixes are now together and it is easy to skip them. Look at kalinov's solution for implementation.

Second solution (actually incorrect but useful): We can calculate the hash function of all interesting substrings as longs, sort this values and find the number of different. This solution fails if there are two different interesting substrings with same hash, but it happens not very often. Look at Petr's solution for implementation.