Match Editorial

Match summary

Round 2 of the 2007 TopCoder Collegiate Challege had to cut 900 competitors down to the 300 slots available in Round 3. In the battle to continue their quest for Disney World, coders had to face 3 problems of increasing difficulty. More than 20 of them finished the round with all three correct, proving themselves deserving of getting to Round 3. As it turned out, even a good time on the easy was enough to move forward.

The round was won by Vasyl[alphacom], who took first place ahead of many higher rated coders. bmerry followed closely, with krijgertje rounding out the top three.

The Problems

Value	250
Submission Rate	764 / 811 (94.20%)
Success Rate	536 / 764 (70.16%)
High Score	rahulgarg123 for 248.13 points (2 mins 28 secs)
Average Score	201.43 (for 536 correct submissions)

This problem can be solved by direct search. Let us fix number k and try to find whether there is a number between left and right, inclusive, that is the k-th power of some integer. To do this we can find x - the smallest number such that its k-th power is greater or equal to the left, and test whether x^k ≤ right. If it is, x^k is the k-th power of integer that is between left and right. In the other case, clearly, there is none.

To find x we can use either binary search (in this case we can use only integers), or use floating point math functions and, for example, test numbers around left^(1/k).

The last thing to note is that since 2^40=1099511627776 > 10^12, the answer doesn't exceed 39, so we only need to test k from 1 to 39.

The code follows.

    long power(long v, int k) {
        long r = 1;
        for (int i = 0; i < k; i++) {
            r *= v;
        }
        return r;
    }

    long root(long v, int k) {
        long l = 1;
        long r = Math.round(Math.pow(v, 1.0 / k)) + 1;
        while (l < r - 1) {
            long m = (l + r) / 2;
            if (power(m, k) > v) {
                r = m;
            } else {
                l = m;
            }
        }
        return l;
    }

    public int greatestPower(String left, String right) {
        long l = Long.parseLong(left);
        long r = Long.parseLong(right);

        for (int k = 39; k > 1; k--) {
            long vl = root(l, k);
            long vlp = power(vl, k);
            if (l <= vlp && vlp <= r) {
                return k;
            }
            vlp = power(vl + 1, k);
            if (l <= vlp && vlp <= r) {
                return k;
            }
        }
        return 1;
    }

Value	500
Submission Rate	435 / 811 (53.64%)
Success Rate	166 / 435 (38.16%)
High Score	Petr for 407.20 points (14 mins 15 secs)
Average Score	238.20 (for 166 correct submissions)

This problem turned out to be quite technical, so many coders had a hard time implementing its solution. Actually, as usually for such problems, it was needed to clearly understand about each statement in the program - what, how and why it does.

First, let us convert the representation of each number to the list of pairs (d_i, l_i), where the pair means that the digit d_i is repeated l_i times. After that we refactor these lists so that in both lists for a and for b corresponding l_i are equal (we can do it by splitting some of the pairs).

Now we sum the blocks, keeping the carry. Suppose that we add up the blocks (a_i, l) and (b_i, l), and the carry from the previous block is c. Then the last digit of the sum block is (a_i+b_i+c) mod 10, the carry inside the block is c'=(a_i+b_i+c)/10 (integer division), the digit inside the block is (a_i+b_i+c') mod 10, and the carry to the next block is equal to c'.

All we need to answer the questions now is to track which block each of the digits of the sum is in. Another thing not to forget is that the sum can contain one digit more if there is a carry from the last block.

The code follows:

    class Pair {
        long l;
        int d;

        public Pair(long l, int d) {
            this.l = l;
            this.d = d;
        }
    }

    ArrayList decompress(String a) {
        ArrayList r = new ArrayList();
        for (int i = 0; i < a.length(); i++) {
            long l = 1;
            if (a.charAt(i) == '[') {
                int j = i;
                while (a.charAt(j) != ']') {
                    j++;
                }
                l = Long.parseLong(a.substring(i + 1, j));
                i = j + 1;
            }
            r.add(new Pair(l, a.charAt(i) - '0'));
        }
        ArrayList rr = new ArrayList();
        for (int i = r.size() - 1; i >= 0; i--) {
            rr.add(r.get(i));
        }
        return rr;
    }

    public int getDigit(String a, String b, long k) {
        ArrayList ap = decompress(a);
        ArrayList bp = decompress(b);

        ArrayList ai = new ArrayList();
        ArrayList bi = new ArrayList();
        int i = 0;
        int j = 0;
        while (i < ap.size() && j < bp.size()) {
            long d = Math.min(ap.get(i).l, bp.get(j).l);
            ai.add(new Pair(d, ap.get(i).d));
            bi.add(new Pair(d, bp.get(j).d));
            if (d == ap.get(i).l) {
                i++;
            } else {
                ap.get(i).l -= d;
            }
            if (d == bp.get(j).l) {
                j++;
            } else {
                bp.get(j).l -= d;
            }
        }
        while (i < ap.size()) {
            ai.add(new Pair(ap.get(i).l, ap.get(i).d));
            bi.add(new Pair(ap.get(i).l, 0));
            i++;
        }
        while (j < bp.size()) {
            ai.add(new Pair(bp.get(j).l, 0));
            bi.add(new Pair(bp.get(j).l, bp.get(j).d));
            j++;
        }

        long d = 0;
        int carry = 0;
        i = 0;
        while (d <= k && i < ai.size()) {
            Pair aa = ai.get(i);
            Pair bb = bi.get(i);
            long l = aa.l;

            if (d == k) {
                return (aa.d + bb.d + carry) % 10;
            } else if (d + l > k) {
                if (aa.d + bb.d + carry >= 10) {
                    return (aa.d + bb.d + 1) % 10;
                } else {
                    return (aa.d + bb.d) % 10;
                }
            }

            if (aa.d + bb.d + carry >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }
            d += l;
            i++;
        }
        if (d == k) {
            return carry;
        } else {
            return 0;
        }
    }

    public int[] getDigits(String a, String b, String[] k) {
        int n = k.length;

        int[] r = new int[n];
        for (int i = 0; i < n; i++) {
            r[i] = getDigit(a, b, Long.parseLong(k[i]));
        }

        return r;
    }

Value	1000
Submission Rate	116 / 811 (14.30%)
Success Rate	36 / 116 (31.03%)
High Score	NauCoder for 862.58 points (11 mins 43 secs)
Average Score	630.60 (for 36 correct submissions)

As the method name slightly hints, this problem is related to mincost flow. Suppose that the worker i is already performing t tasks and is assigned another one. In this case the total cost of completing all tasks increases by cost[i] * ((t + 1)² - t²) = cost[i] * (2 * t + 1).

Suppose that each worker completes a task he can perform in one hour. Then completing the task by the i-th worker on the k-th hour costs cost[i] * (2 * k - 1).

Create a bipartite graph where the vertex of the left part is the task, and vertex of the right part is the process of some worker completing some task on some hour. If worker i can perform task j, for all k from 1 to n we connect the vertex that represents task j with the vertex that represtents the k-th hour of worker j by an edge with capacity 1 and cost cost[j] * (2 * k - 1). The fragment of the graph with worker 1 is shown on the picture below.

Combining these fragments for all workers, and adding a source and a sink, we get the graph, the value of mincost flow for the cost of completing all tasks.

However, the size of the graph is too large. Although the solution which finds the mincost flow in the described graph actually passes systests, we cannot feel comfortable when looking for the mincost flow in the graph with 2500+ vertices. There are several ways to deal with that. One, as Petr's solution suggests, is to add vertices when needed, keeping only one vertex for each worker, besides saturated (although the solution failed systests, the idea is correct).

Another way is to reduce the size of the graph. Looking at the right part of the graph, we note that the cost of the edge entering some vertex is the same for all edges. So we can actually move this cost from these edges to the edge that goes to the sink. And now we can merge vertices corresponding to the same worker to one, getting parallel edges to the sink. We get the graph, as shown on the picture below. It has a vertex for each task, and a vertex for each worker. Each task is connected to each worker that can perform it by an edge with capacity 1 and cost 0, and each worker is connected to the sink by n edges with capacity 1 each, and costs cost[i], 3 * cost[i], ..., (2 * n -1) * cost[i], respectively.

And finally the most surprising idea is that we actually need no mincost flow at all! We can go with just a bipartite matching algorithm.

Looking again at the graph that we first constructed, we see that we actually need to find the minimal weight matching in the bipartite graph. And the cost of the edge only depends on its right end. Thus we can move the cost from the edge to the vertex. So we need to find the matching that has the minimal sum of costs of its right ends. This is exactly the problem of finding the minimal cost base in a transversal matroid (called matching matroid at Planet Math). This base can be found by a greedy algorithm. So we sort the vertices in the right part by their weight, and try to find the augmenting paths starting from the cheapest one. When all vertices in the left part are saturated, we are done. Look at pashka's solution for a nice implementation of this idea.