Match Editorial

In Qualification Round 3 of TCCC07 there were only 455 participants. As this was less than the 550 available spots, any positive score was enough to advance. Thanks to the very solvable easy problem, 445 coders were able to solve it and to advance to the next round. First place was taken by Chinese coder daisy, while sephiroth79 and _kiwi_ from Viet Nam took the second and third spots. All of them (as well as 31 other coders) correctly solved all three problems.

In total, 1695 coders advanced to Online Round 1. Congratulations to them all, and good luck in the next rounds!

The Problems

Value	250
Submission Rate	447 / 455 (98.24%)
Success Rate	445 / 447 (99.55%)
High Score	BlueriF for 249.24 points (1 mins 34 secs)
Average Score	230.56 (for 445 correct submissions)

In order to solve the problem, we iterate over all positions i of characters in input strings. If i-th character in first and i-th character in second correspond to complementary proteins, then no replacements at position i are needed, otherwise we need 1 replacement to make one of the proteins complementary to another. One of the simplest ways to check whether two characters correspond to complementary proteins is to calculate the sum of their positions in string "ACGT" and check whether this sum equal 3 or not.

Java code follows:

public int minReplaces(String first, String second) {
    int res = 0;
    for (int i=0; i < first.length(); i++)
        if ("ACGT".indexOf(first.charAt(i)) +
            "ACGT".indexOf(second.charAt(i)) != 3)
            res++;
    return res;
}

Value	600
Submission Rate	152 / 455 (33.41%)
Success Rate	116 / 152 (76.32%)
High Score	marijnk for 534.91 points (10 mins 9 secs)
Average Score	325.07 (for 116 correct submissions)

There are a total of 2²⁴ = 16,777,216 different colors, so if we find some way to determine the distance between the given color and the given set of colors in constant time then we'll be able to solve the problem by iterating through all possible colors.

In order to calculate the distance in constant time, let's use the following observation. If X₁, X₂, ..., X_N are integers, m is min{X₁, X₂, ..., X_N} and M in max{X₁, X₂, ..., X_N}, then the maximum among differences |x - X_i| equals to either |x - m| or to |x - M|. Therefore, if minR and maxR are the minimum and the maximum red quantity values among all colors in the given set, minB and maxB are the minimum and the maximum blue quantity values, and minG and maxG are the minimum and the maximum green quantity values, then the distance between the color (R, G, B) and the given set of colors can be calculated as max{|R - minR|, |R - maxR|, |G - minG|, |G - maxG|, |B - minB|, |B - maxB|}.

Commented Java implementation of this approach follows:

// converts hexadecimal character to its decimal equivalent
public int toInt(char c) {
    return "0123456789ABCDEF".indexOf(c);
}

// converts decimal integer to hexadecimal character    
public String toHex(int x) {
    return "" + "0123456789ABCDEF".charAt(x);
}
    
public String bestApproximation(String[] colors) {
    int[] min = new int[] {256, 256, 256};
    int[] max = new int[] {-1, -1, -1};

    // parse the input and calculate minimum/maximum
    // red, green and blue quantities among all colors
    for (int i=0; i < colors.length; i++) {
        String[] S = colors[i].split(" ");
        for (int j=0; j < S.length; j++)
            for (int k=0; k < 3; k++) {
                int val = 16 * toInt(S[j].charAt(2*k)) + 
                               toInt(S[j].charAt(2*k+1));
                min[k] = Math.min(val, min[k]);
                max[k] = Math.max(val, max[k]);
            }
    }
        
    int bestDist = 256;
    int[] best = new int[] {-1, -1, -1};
    int[] cur = new int[3];

    // iterate through all possible answers
    for (cur[0]=0; cur[0]<256; cur[0]++)
        for (cur[1]=0; cur[1]<256; cur[1]++)
            for (cur[2]=0; cur[2]<256; cur[2]++) {
                int curDist = -1;
                for (int k=0; k<3; k++) {
                    curDist = Math.max(curDist, Math.abs(cur[k] - min[k]));
                    curDist = Math.max(curDist, Math.abs(cur[k] - max[k]));
                }
                if (curDist < bestDist) {
                    bestDist = curDist;
                    best = cur.clone();
                }
            }

    // format the result into String        
    String res = "";
    for (int k=0; k < 3; k++)
        res += toHex(best[k] / 16) + toHex(best[k] % 16);

    return res;
}

Value	900
Submission Rate	63 / 455 (13.85%)
Success Rate	44 / 63 (69.84%)
High Score	_kiwi_ for 851.62 points (6 mins 50 secs)
Average Score	632.82 (for 44 correct submissions)

This problem can't be solved by generating all vector matchings for a given set of points, as such a solution will easily exceed the time limit (for example, there are 670,442,572,800 different vector matchings for a set of 20 points). Therefore we need to find some property that will help us to prune the search space.

Let's consider some vector matching, consisting of vectors (x[i₁], y[i₁]) -> (x[j₁], y[j₁]), (x[i₂], y[i₂]) -> (x[j₂], y[j₂]), ..., (x[i_n], y[i_n]) -> (x[j_n], y[j_n]). The vector sum of all vectors in the matching will give us the vector ((x[i₁] - x[j₁]) + (x[i₂] - x[j₂]) + ... + (x[i_n] - x[j_n]), (y[i₁] - y[j₁]) + (y[i₂] - y[j₂]) + ... + (y[i_n] - y[j_n])) = ((x[i₁] + x[i₂] + ... + x[i_n]) - (x[j₁] + x[j₂] + ... + x[j_n]), (y[i₁] + y[i₂] + ... + y[i_n]) - (y[j₁] + y[j₂] + ... + y[j_n])) (1).

From formula (1) we see that if we fix the points that will be the start points of vectors in the matching, and which points will be end points, the vector sum of all vectors in the matching will not depend on the way that was chosen to connect start and end points by vectors. Therefore, we can solve the problem by generating all the subsets of start points (in the worst case of 20 points, there will be just 184,756 such subsets). All the vector matchings with fixed subsets of start points have the same vector sum of their vectors, which can be determined by formula (1). To get the answer, we choose the vector sum with the minimum length among all subsets of start points.

Java implementation below uses bitmasks to generate all the subsets of start points (1 bit encodes start point, and 0 bit - end point). If you are not familiar with bitmasks, please check this tutorial.

// calculates the count of 1 bits in the mask
public int bitCnt(int mask) {
    return (mask==0 ? 0 : bitCnt(mask & (mask - 1)) + 1);
}
    
public double minimumLength(int[] x, int[] y) {
    int N = x.length;
    double res = Double.MAX_VALUE;

    // iterate over all possible bitmasks with N bits
    for (int mask=0; mask < (1 << N); mask++) {
        // check that exactly half of bits are 1 bits
        if (bitCnt(mask) != N/2) continue;

        // calculate the vector sum using formula (1)
        long sumX = 0, sumY = 0;
        for (int i=0; i < N; i++) {
            int sign = ((mask & (1 << i)) > 0 ? 1 : -1);
            sumX += sign * x[i];
            sumY += sign * y[i];
        }

        // compare the length of the vector sum with the best one
        res = Math.min(res, Math.sqrt(sumX * sumX + sumY * sumY));
    }

    return res;
}