Match Editorial

SRM 176 Division 1 had a total point value of 2000 for all three problems, probably the highest ever. The presence of a 600 as well as an 1150 may have daunted some coders, but certainly not bladerunner, who finished with a score of 1650, almost making it into the top ten highest totals ever. Tomek, finishing in second, continues to increase his rating, now to 3506. Eryx, a fairly new coder, extends his flawless record to three SRMs. Nothing too unusual in Divison 2, acki2003 took first, not far behind were tp1 and slanc, two first time coders whose performance earned them yellow ratings.

The Problems

Value	250
Submission Rate	169 / 183 (92.35%)
Success Rate	112 / 169 (66.27%)
High Score	Tak-kun for 242.77 points (4 mins 55 secs)
Average Score	182.41 (for 112 correct submissions)

If you've ever messed around with any cool graphics programs (like Photoshop) you may be familiar with the inverse of colors. You may also be aware that when you try to take the inverse of grey, you get grey, which isn't so hot when you're trying to make the grey stand out. This problem attempts to fix that with a simple check for shades of grey. All that was required for this problem was to create the color's complement in the standard way, check to see if all components were too close to their corresponding components in the original color, and if so, return an alternate complement.

vector<int> getComplement(vector<int> v) {
    vector<int> ret(3);
    bool grey=true;
    for (int i=0;i<3;i++) {
        ret[i]=255-v[i];
        if (ret[i]-v[i]>32 || ret[i]-v[i]<-32)
            grey=false;
    }
    if (grey)
        for (int i=0;i<3;i++)
            ret[i]=(v[i]+128)%256;
    return ret;
};

Value	500
Submission Rate	142 / 183 (77.60%)
Success Rate	130 / 142 (91.55%)
High Score	thegreensniper for 479.66 points (5 mins 54 secs)
Average Score	345.80 (for 130 correct submissions)

Value	250
Submission Rate	152 / 152 (100.00%)
Success Rate	146 / 152 (96.05%)
High Score	ZorbaTHut for 246.94 points (3 mins 10 secs)
Average Score	219.25 (for 146 correct submissions)

Based on a particularly fun card game, the task here was to determine the characteristics of the third card in a set based on the characteristics of the first two. At first glance it appears that this problem should be solved with a series of if-else clauses, but there is a more elegant solution. Each characteristic on each card is one of three different values. Each of these values can be numbered 0, 1, or 2, so the shape characteristic of a card, for example, would be 0, 1, or 2, instead of "SQUIGGLE", "DIAMOND", or "CIRCLE". Since a set requires all three cards to match or for none of the cards to match for a given characteristic, the only combinations of states for a set are {0,0,0}, {1,1,1}, {2,2,2}, or {0,1,2}. All three values of each of these combinations add to a multiple of three, so given the first two states we can find the third by determining which state will make the sum of all three a multiple of three. This makes for much cleaner code:

vector<string> findMatch(vector<string> a,vector<string> b) {
    string state[4][3]={{"CIRCLE","SQUIGGLE","DIAMOND"},
                        {"RED","GREEN","BLUE"},
                        {"SOLID","STRIPED","EMPTY"},
                        {"ONE","TWO","THREE"}         };
    vector<string> ret(4);
    for (int i=0;i<4;i++) {
        int val=0;
        for (int j=0;j<3;j++) {
            if (a[i]==state[i][j]) val+=j;
            if (b[i]==state[i][j]) val+=j;
        }
        ret[i]=state[i][(9-val)%3];
    }
    return ret;
};

For each characteristic, add together the values (0,1, or 2) of the states of the two cards, then find out what state will add to that to get a multiple of three. (-n)%3 will give a value that adds to n to make a multiple of three, but when using the % (modulus) operator on a negative number, you get a negative number back. This is the purpose of (9-val)%3, since 9 is a multiple of 3 already it will ensure that (9-val)%3 is a positive value that, when added to val, is a multiple of three.

Value	900
Submission Rate	35 / 183 (19.13%)
Success Rate	13 / 35 (37.14%)
High Score	robert1900 for 700.79 points (16 mins 8 secs)
Average Score	488.19 (for 13 correct submissions)

This problem offered two obstacles, reducing fractions and tiebreaking. Given two frequencies, determining how harmonic they are when played together is done by determining the lowest possible integer that can be used in the denominator when the ratio is expressed as a fraction. This means the fraction must be reduced, and once it is reduced we choose the smaller of the two numbers (since it doesn't matter if the ratio is a:b or b:a). Reducing a fraction is a simple matter of dividing both numbers by the greatest common denominator of the two numbers. The GCD is found easily by using Euclid's GCD algorithm, which can be implemented as follows:

int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
};

Once we have the GCD of two numbers, we divide the smaller of the two numbers by it and we have the lowest number that can be used in the denominator of the fraction representing the ratio of those two numbers. All that was required of this problem was to loop through all combinations of three frequencies (this is O(n³), which isn't bad for an input size of 50), and keep track of the best chord. The following C++ code does this and figures all tiebreakers by exploiting the STL comparators for vectors as much as possible.

vector<int> mostHarmonious(vector<int> v) {
    sort(v.begin(),v.end());
    vector<int>bestFreq(3);
    vector<int>bestDen(3,1000000);
    for (int i=0  ;i<v.size();i++)
    for (int j=i+1;j<v.size();j++)
    for (int k=j+1;k<v.size();k++) {
        vector<int>curFreq(3);
        vector<int>curDen(3);
        curFreq[0]=v[i];
        curFreq[1]=v[j];
        curFreq[2]=v[k];
        curDen[0]=v[i]/gcd(v[i],v[j]);
        curDen[1]=v[i]/gcd(v[i],v[k]);
        curDen[2]=v[j]/gcd(v[j],v[k]);
        sort(curDen.begin(),curDen.end());
        reverse(curDen.begin(),curDen.end());
        if (curDen<bestDen || (curDen==bestDen && curFreq<bestFreq)) {
            bestFreq=curFreq;
            bestDen=curDen;
        }
    }
    return bestFreq;
};

To compare two chords, first the denominators of each chord are compared, greatest to smallest, and the first chord to have a smaller denominator is considered more harmonic. This is why the curDen and bestDen are reversed, the < operator for vectors will now do all the comparing we need. Similarly, the frequencies are sorted in increasing order and the < operator again does all of the work for us.

Value	600
Submission Rate	38 / 152 (25.00%)
Success Rate	37 / 38 (97.37%)
High Score	John Dethridge for 571.27 points (6 mins 26 secs)
Average Score	397.16 (for 37 correct submissions)

This problem asked for the number of permutations of a set of numbers in which none of the elements remained in their original position. This problem is solvable in more than one way. One way is memoized recursion, which is the approach that most coders took. The solution I give here, however, uses the principle of inculsion-exclusion.

The principle of inclusion-exclusion gives a way of counting the number of unique items in a set of sets of items. I will give a general idea of how it works, for a more rigorous explanation, click here. Consider the Venn diagram to the right that shows three circles representing the primary colors of light and how they add together. The principle of inclusion-exclusion says that the total area covered by the three circles will be equal to the sum of the areas of each circle, minus the area of each intersection of two circles, plus the area of the intersection of all three circles. The general idea is to add the intersection of each group of an odd number of sets, and subtract the intersection of each group of an even number of sets.

Now to apply this to deranged permutations. First we need to be able to calculate the number of uniqe permutations of a set S. If S contains n elements, all of which are unique, then there exist n! permutations of S. If S contains n elements and the value v _i occurs k_i times in S, for i=1 through m, then the number of distinct permutations of S is given by n!/(k₁!*k ₂!*...*k_m-1!*k_m!). If we want to calculate the number of permutations of S when a subset of the elements in S are held in their original positions we can just remove those elements from S and then calculate the number of permutations of S with those elements removed. To calculate the number of permutations for which no element remains in its original position, we calculate the number of permutations of S in which at least one element remains in its original position, and subtract that number from the total number of permutations of S. To calculate the number of permutations for which at least one element remains in its original position we use the principle of inclusion-exclusion. The following pseudo-code demostrates how to do this, see writer's solution in the practice room for an implementation of this in C++.

long long numDerangements(S)
   long long ret=numPermutations(S);
   for i from 1 to the number of elements in S
      for each combination, C, of i elements in S
         if (i is odd) ret=ret-numPermutations(S-C);
         if (i is even) ret=ret+numPermutations(S-C);
      end
   end
   return ret;
end

Value	1150
Submission Rate	32 / 152 (21.05%)
Success Rate	8 / 32 (25.00%)
High Score	WishingBone for 1045.00 points (9 mins 11 secs)
Average Score	740.45 (for 8 correct submissions)

An 1150 point problem can be quite intimidating, and I was pleased to see several coders solve this problem, and was even more pleased to see that several solved it without the use of a prewritten geometry library. Many coders tried Monte Carlo solutions, and John Dethridge even attempted to solve the problem using quad trees, though these approximations were not able to get the accuracy of 1e-5 that the problem required. The solution that I outline here involves finding Voronoi polygons, which happen to be exactly what the problem is asking for. Given a set P of n points in a plane, a Voronoi diagram partitions the plane into n regions (called Voronoi polygons) such that each region contains one point from P and contains all points in the plane that are closer to that one point than to any other point in P.

One way to construct the Voronoi diagram is to first create the Delaunay triangulation. This method, however, would require significantly more explanation than anyone would like to hear. If you want to read about and fool around with a cool applet demonstrating the relationship between Delaunay triangulations and Voronoi diagrams, click here.

If we restrict the Voronoi diagram such that no region extends outside the square region with corners at (0,0) and (100,100), then we will have a diagram that will solve our problem. In this case, each Voronoi edge is either the perpendicular bisector of the line segment between some pair of watchtowers, or it is one of the sides of the square region. If you don't realize that each edge of the Voronoi diagram of a set of points P is the perpendicular bisector of the line segment between some pair of points in P, take a moment to convince yourself of this.

What we need to find the area of each region, however, are the intersection points of the appropriate lines. For a watchtower w, find the perpendicular bisectors of the line segments between w and every other watchtower. Call the set of these lines along with the four lines defining the square region L. Now find the intersection point of every pair of lines in L and call this set of points T. Clearly T contains the set of points that define the Voronoi polygon around w, which I will now refer to as V. How do we find which points in T are also in V? Since each Voronoi region is convex (if you didn't know this already, take a moment to prove it) no line in L will come between w and a point in V. Also, every point in T that is not in V will be separated from w by some line in L. Knowing this, we can determine if a point in T is also in V by determining whether or not there is a line in L that separates it from w.

Determining if two points lie on the same side of a line is easy given the correct representation of a line. If we represent lines in the form Ax+By+C=0, then when we plug a point into that equation, it will be zero if it lies on the line, positive if it lies on one side, and negative if it lies on the other side. If for all equations for lines in L we plug in w and a point from T and both results have the same sign then that point in T is also in V. There are special cases for this, however. Since w can lie on certain lines (if it is located on border of the square region), we need to move w inside the square region slightly for the purposes of finding the points in V. Also, since points in V can lie on certain lines in L, we have to accept a point as being in V if it yields 0 when plugged into an equation for a line in L. Since we are using floating point numbers here, however, we have to actually make sure it is close to 0, a value of 1e-3 works fine for this.

Now that we have all of the points that make up the Voronoi polygon, we need to arrange them in either clockwise or counter-clockwise order. This can be done a number of ways. I prefer to sort them by the slope of the line that passes through them and an arbitrary point on the interior of the polygon. Once the points are sorted, the area of the polygon they form is given by the absolute value of (1/2)(x₁y₂-x₂y₁+ x₂y₃-x₃y₂+...+ x_n-1y_n-x_ny_n-1+ x_ny₀-x₀y_n).

The image here should give a general idea of everything I have said. The red dot is w, the three black dots are the other watchtowers. The black dashed lines are the line segments between w and the other towers, the blue lines are the corresponding perpendicular bisectors, the green points are intersection points in T, and the yellow points are intersections points that are in T and also in V. The highlighted region around the red dot is the Voronoi polygon around w.

Now that we can compute the area of the Voronoi polygon around a given watchtower, just do it for each watchtower, and sort them by area. The bulk of the time this algorithm spends is when it is determining which points are part of the Voronoi polygon. If there are W watchtowers, then there are O(W) lines in L and O(W²) points in T. Determining which points are part of the Voronoi polygons takes O(W³) comparisons, and this has to be done for each watchtower. So the algorithm i've outlined here is O(W⁴). Not great, but with an input size of 20 it runs plenty fast.