Match Editorial

Match summary

This was a very important match for the 140 coders that had the opportunity to earn a trip to Disney World, the chance to compete in the onsite rounds and the possibility to meet lots of other TopCoders. After the coding phase, bmerry, who had the fastest time on both the medium and the hard, was in first position. He was two challenges away from konqueror in second place and a less comfortable 4 challenges away from Petr in third place. During the challenge phase Petr made 5 successful challenges in a row, taking the lead. But he made another 3 unsuccessful challenges before looking at the score board. Two last challenges couldn't help and bmerry won the round, leaving Petr in second place and Zhukov_Dmitry in third place after konqueror's hard was successfully challenged. Congratulations to bmerry and everybody else who made it onsite!

The Problems

Value	250
Submission Rate	137 / 140 (97.86%)
Success Rate	76 / 137 (55.47%)
High Score	Revenger for 241.20 points (5 mins 27 secs)
Average Score	188.29 (for 76 correct submissions)

We have to find directions between two nodes in a Frabonacci tree, a structure closely resembling a Fibonacci tree. Doing this consists of two parts: finding the two points, and finding the directions between them. It's not too hard to solve both parts at the same time, but let's keep them separate for the purpose of simplicity.

Suppose we have a function that gives us the directions from the root node to a given node. Then we already have a path if we reverse the path to the first node and concatenate the path to the second node. Here reversing just means replacing every L or R with a U. But this path will probably not be a shortest path. In order to make the path as short as possible, we only need to use the directions from the point where both paths diverge. So if we already have a function directionsTo(), the solution is as follows:

public String shortestPath(int n, int startIndex, int finishIndex) {
    String toStart = directionsTo(n, startIndex);
    String toFinish = directionsTo(n, finishIndex);
    while (toStart.length() > 0 && toFinish.length() > 0 &&
           toStart.charAt(0) == toFinish.charAt(0)) {
        toStart = toStart.substring(1);
        toFinish = toFinish.substring(1);
    }
    return toStart.replaceAll(".", "U") + toFinish;
}

Now how do we find the directions from the root node to a given node? If the given node has index 1, then it is the root node, and we return "". If the index of the node is small, we go left, and if it's large we go right. Here small means less than or equal to the number of nodes in the left subtree plus one (the root) and large means greater than small. The rest of the path we can do recursively by subtracting the number of skipped nodes (1 for the root, plus maybe the size of the left subtree) from our index.

String directionsTo(int n, long index) {
    if (index == 1) return "";
    if (index > nodesInTree(n - 2) + 1) {
        return "R" + directionsTo(n - 1, index - 1 - nodesInTree(n - 2));
    }
    return "L" + directionsTo(n - 2, index - 1);
}

long[] nodesInTree = new long[51];
long nodesInTree(int n) {
    if (n < 2) return 1;
    if (nodesInTree[n] != 0) return nodesInTree[n];
    return nodesInTree[n] = 1 + nodesInTree(n - 1) + nodesInTree(n - 2);
}

SausagesProductionScheduler
Used as: Division One - Level Two:

Value	500
Submission Rate	120 / 140 (85.71%)
Success Rate	45 / 120 (37.50%)
High Score	bmerry for 442.97 points (10 mins 28 secs)
Average Score	289.56 (for 45 correct submissions)

In this problem we have to select an as large as possible subset from a given set of items (recipes), while staying within certain constraints. Sounds like knapsack, doesn't it? Except that we're actually filling two knapsacks at the same time because we have to take both ingredients into account, and we also have some freedom to change the size of our items (i.e. the amount of certain ingredient used).

A first important observation to make is that we can almost completely ignore the second ingredient because we always use 100 - x of it per sausage we make, where x is the amount we use of the first ingredient. We only have to make sure we translate the constraints on the second ingredient into constraints on the first ingredient. This means that, per sausage, the minimal amount of ingredient-1 used is possibly increased to 100 minus the maximal amount of ingredient-2 that is used. And the maximal amount of ingredient-1 used is possibly decreased to 100 minus the minimal amount of ingredient-2 that is used. Also if we make n sausages, we have to use at least 100 * n - limit[1] of the first ingredient to make sure we don't need to use more than limit[1] of the second ingredient. From now on, we will only consider the amount of the first ingredient we use. Let's call this ingredient meat.

After we've updated all the ranges of the recipes we are left with the following problem: Find the maximal n such that we can select n recipes that together allow us to use an amount of meat that is at least 100 * n - limit[1] and at most limit[0].

So given the number n of sausages we want to make, and the amount x of meat we want to use, we need to know whether there is some subset of recipes of size n that allows us to use exactly x meat. Now let canMake[n][x] be a boolean that tells us whether we can make n sausages, using x meat. If, before considering recipe i we have canMake[n][x] == true, then by considering recipe i we know that canMake[n + 1][x + y] must be true for every amount y of meat we can use to for recipe i. After we've completely filled canMake we can iterate through it to find the maximal number of sausage we can make with an amount of used meat between 100 * n - limit[1] and limit[0].

This solution has time complexity O(n * n * x * y), where n is the number of recipes, x is the maximal total amount of meat and y is the number of possible different amounts per sausage, i.e. at most 100. Petr's solution is a clean implementation of this idea.

There is also a solution with complexity O(n * n * x). The idea is not to try every possible amount for every recipe, but instead, to find a range of possible amounts and see if it overlaps with the range determined by the limits. Suppose we have to use at least haveToUse gram of meat. Using a specific recipe we can take care of part of this amount, but this also forces us to use at least the minimal amount needed for this recipe. Now if we can find the minimal amount of meat we must use (due to used recipes), based on the fact that we have to use a certain amount of meat (due to the limits), then we can check if we can use at least this amount. If we can, we know it's possible to make the assumed number of sausages. So if mustUse[i][n][haveToUse] is the amount of meat we are forced to use if we need to use at least haveToUse to make n sausages, while considering recipe i, the recurrence relation we get is

mustUse[i][n][haveToUse] = min(
    mustUse[i + 1][n][haveToUse],
    mustUse[i + 1][n - 1][haveToUse - maxUsed[i]] + minUsed[i]);

public class SausagesProductionScheduler {
    static final int INFINITY = 1000000;
    int n;
    int[] minUsed;
    int[] maxUsed;

    public int maxCount(String[] lowerPercentage, String[] upperPercentage,
                        int[] limits) {
        n = lowerPercentage.length;
        minUsed = new int[n];
        maxUsed = new int[n];

        for (int i = 0; i < n; i++) {
            Scanner in1 = new Scanner(lowerPercentage[i]);
            Scanner in2 = new Scanner(upperPercentage[i]);
            minUsed[i] = in1.nextInt();
            maxUsed[i] = in2.nextInt();
            minUsed[i] = Math.max(minUsed[i], 100 - in2.nextInt());
            maxUsed[i] = Math.min(maxUsed[i], 100 - in1.nextInt());
        }

        memo = new int[100 * n + 1][n + 1][n];

        for (int nSausages = n; nSausages > 0; --nSausages) {
            int haveToUse = 100 * nSausages - limits[1];
            int mustUse = mustUse(haveToUse, nSausages, 0);
            if (haveToUse <= limits[0] && mustUse <= limits[0]) {
                return nSausages;
            }
        }

        return 0;
    }

    int[][][] memo;
    int mustUse(int haveToUse, int recipesToUse, int currentRecipe) {
        if (currentRecipe == n && recipesToUse > 0) return INFINITY;
        if (recipesToUse == 0) {
            if (haveToUse > 0) return INFINITY;
            return 0;
        }
        if (haveToUse < 0) haveToUse = 0;
        int mem = memo[haveToUse][recipesToUse][currentRecipe];
        if (mem != 0) {
            return mem;
        }

        int result = mustUse(haveToUse, recipesToUse, currentRecipe + 1);
        if (minUsed[currentRecipe] <= maxUsed[currentRecipe]) {
            int used = mustUse(haveToUse - maxUsed[currentRecipe],
                               recipesToUse - 1, currentRecipe + 1) +
                minUsed[currentRecipe];
            result = Math.min(result, used);
        }
        return memo[haveToUse][recipesToUse][currentRecipe] = result;
    }
}

Value	1000
Submission Rate	7 / 140 (5.00%)
Success Rate	6 / 7 (85.71%)
High Score	bmerry for 614.66 points (26 mins 15 secs)
Average Score	519.94 (for 6 correct submissions)

If finding a common subsequence makes you think of dynamic programming, you have to be careful here because we're not looking for a longest common subsequence. We're looking for the lexicographically last common subsequence. But wait! This is TopCoder, aren't we supposed to be looking for the lexicographically first common subsequence? Hehe, that would be a bit too easy because it would be the empty string :-).

For now, ignore the fact that we have to return a suffix. We can just take the suffix of our result at the end. What would be the first character of the sequence we're looking for? Since we can choose the character with the largest value that is present in both strings as our first character and it's impossible to make a lexicographically larger string with another first character, that must be our first character. So how many of those will be at the start of our result string? There can't be more than the number of those characters present in the string that has the least of them. But we certainly can choose that number of those character as a subsequence. So we already know the first character of our result and how many times it's repeated and we didn't even need to cyclically shift either of the input strings.

So what will be the next character? Can we choose the second largest character present in both strings? Yes we can, and this is where the shifting comes in. If we shift one of the second largest characters to the end of both strings, we can still have our common subsequence start with the number of largest character we had decided on, and then take the last character of both shifted strings. We can even possibly take more of them if there are more after the necessary characters to start with. How many more does depend this time on the cyclic shift we use. But if we only care about the number of (second largest) characters we use, it can't hurt to put one of them at the end. And since any lexicographically largest subsequence will have the maximal amount of largest characters, we can greedily choose their number right now.

That's right, we can do it greedily. We just continue to append as many next largest characters as possible. For every cyclic shift we first skip the starting characters we've already decided on and then look for addition characters with the value we're considering right now. Then we take the maximum that's possible in both strings and continue. And when we're done, we just return the necessary suffix.

This solution might seem O(c * n * n) where c is the number of different characters to consider and n is the length of the input strings and the number of different cyclic shifts. But since we consider every character only once as the last character in a cyclic shift, it's actually O(n * n) which will run in time for n <= 2500.

Here's a solution that implements this idea:

public class CommonSubsequence {
    int[] counts = new int[128];

    public String maxLex(String[] A, String[] B, int suffixLength) {
        String a = join(A);
        String b = join(B);

        StringBuilder result = new StringBuilder();
        for (char c = 126; c >= 35; c--) {
            counts[c] = Math.min(maxCount(a, c),
                                 maxCount(b, c));
            for (int i = 0; i < counts[c]; i++) {
                result.append(c);
            }
        }

        if (result.length() > suffixLength) {
            return result.substring(result.length() - suffixLength);
        }
        return result.toString();
    }

    int maxCount(String s, char c) {
        int max = 0;
        int len = s.length();
        for (int shift = 0; shift < len; shift++) {
            if (s.charAt((shift + len - 1) % len) != c) continue;

            int i = shift;
            for (char prev = 126; prev > c; prev--) {
                int toFind = counts[prev];
                while (i < shift + len && toFind > 0) {
                    if (s.charAt(i % len) == prev) toFind--;
                    i++;
                }
            }
            int found = 0;
            for (; i < shift + len; i++) {
                if (s.charAt(i % len) == c) found++;
            }
            max = Math.max(max, found);
        }
        return max;
    }

    String join(String[] a) {
        StringBuilder result = new StringBuilder();
        for (String s: a) result.append(s);
        return result.toString();
    }
}

public class CommonSubsequence {

    public String maxLex(String[] A, String[] B, int suffixLength) {
        String a = join(A);
        String b = join(B);
        int[] skippedA  = new int[a.length()];
        int[] skippedB  = new int[b.length()];

        for (int i = 0; i < skippedA.length; i++) skippedA[i] = i;
        for (int i = 0; i < skippedB.length; i++) skippedB[i] = i;

        StringBuilder result = new StringBuilder();

        for (char c = 126; c >= 35; c--) {
            int n = Math.min(maxInRange(a, skippedA, c),
                             maxInRange(b, skippedB, c));
            if (n == 0) continue;

            for (int i = 0; i < n; i++) {
                result.append(c);
            }
            updateSkipped(a, skippedA, c, n);
            updateSkipped(b, skippedB, c, n);
        }

        if (result.length() > suffixLength) {
            return result.substring(result.length() - suffixLength);
        }
        return result.toString();
    }

    int maxInRange(String s, int[] skipped, char c) {
        int len = s.length();
        int result = 0;
        int from = 0, to = 0, count = 0;

        for (int i = 0; i < len; i++) {
            while (from < skipped[i]) {
                if (s.charAt(from % len) == c) count--;
                from++;
            }
            while (to < i + len) {
                if (s.charAt(to % len) == c) count++;
                to++;
            }
            result = Math.max(result, count);
        }
        return result;
    }

    void updateSkipped(String s, int[] skipped, char c, int n) {
        int len = s.length();
        int from = 0, to = 0, count = 0;
        for (int i = 0; i < len; i++) {
            while (from < skipped[i]) {
                if (s.charAt(from % len) == c) count--;
                from++;
            }
            while (count < n) {
                if (s.charAt(to % len) == c) count++;
                to++;
            }
            skipped[i] = to;
        }
    }

    String join(String[] a) {
        StringBuilder result = new StringBuilder();
        for (String s: a) result.append(s);
        return result.toString();
    }
}

Thanks, Mike Mirzayanov, for an interesting problem set and congratulation to everybody who advanced to the onsite rounds!