Qualification Round 3 Thursday, August 23, 2007 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 ProblemsComplementaryDNAChainsUsed as: Division One  Level One:
In order to solve the problem, we iterate over all positions i of characters in input strings. If ith character in first and ith 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; }ColorApproximation Used as: Division One  Level Two:
There are a total of 2^{24} = 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_{1}, X_{2}, ..., X_{N} are integers, m is min{X_{1}, X_{2}, ..., X_{N}} and M in max{X_{1}, X_{2}, ..., 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; }VectorMatching Used as: Division One  Level Three:
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_{1}], y[i_{1}]) > (x[j_{1}], y[j_{1}]), (x[i_{2}], y[i_{2}]) > (x[j_{2}], y[j_{2}]), ..., (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_{1}]  x[j_{1}]) + (x[i_{2}]  x[j_{2}]) + ... + (x[i_{n}]  x[j_{n}]), (y[i_{1}]  y[j_{1}]) + (y[i_{2}]  y[j_{2}]) + ... + (y[i_{n}]  y[j_{n}])) = ((x[i_{1}] + x[i_{2}] + ... + x[i_{n}])  (x[j_{1}] + x[j_{2}] + ... + x[j_{n}]), (y[i_{1}] + y[i_{2}] + ... + y[i_{n}])  (y[j_{1}] + y[j_{2}] + ... + 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; } 
