Match Editorial

This problem set consisted of some nice quality problems. There was a definite triangle theme going on in Division Two, with one problem asking whether three lines could make a triangle and another problem asking for the area of a convex polygon (which is composed of simple triangles). There were no subtle tricks in any of the problems, as evidenced by the relatively high success rates all around.

The leading scorers in Division One, SnapDragon, ZorbaTHut, and venco, obtained their scores solely through solving problems far faster than anyone else. Only a couple of contenders, such as NGBronson and haha, were knocked out of the running during the Challenge Phase. NGBronson didn't handle carrying overflow from additions to the right in LongNumber properly, which O_O picked up on for 50 points.

Divison Two was won by snewman, a newcomer. snewman squeaked ahead of two close runners up, Dumitru and andreicsibi, by successfully challenging someone else's solution.

The Problems

Value	300
Submission Rate	269 / 332 (81.02%)
Success Rate	227 / 269 (84.39%)
High Score	Jwalk for 297.05 points (2 mins 50 secs)
Average Score	226.01 (for 227 correct submissions)

There are two parts to solving this problem. The first is generating triples of values from the list of numbers given. The second is determining whether a given triple can form a triangle.

As the problem states, a triangle can be formed from three line segments if and only if the sum of the lengths of any pair is greater than the length of the third segment. That implies three comparisons, but we really only need to make one to determine if any three segment lengths can form a triangle. If we sort the lengths in ascending order, then we only really have to compare the sum of the first two to the third. The third value is larger than the other two, so it plus any value will always be greater than each of the first two.

If we sort the list of numbers we are given, we can easily generate triples that are already sorted. Thus this problem can be reduced to the following bit of code (in C++):

int Workshop::pictureFrames(vector<int> pieces)
{
    int result = 0;

    sort(pieces.begin(), pieces.end());
    for(vector<int>::const_iterator i = pieces.begin(); i != pieces.end(); i++) {
        for(vector<int>::const_iterator j = i + 1; j != pieces.end(); j++) {
            for(vector<int>::const_iterator k = j + 1; k != pieces.end(); k++) {
                if(*i + *j > *k) {
                    result++;
                }
            }
        }
    }
    return result;
}

Value	500
Submission Rate	217 / 332 (65.36%)
Success Rate	181 / 217 (83.41%)
High Score	snewman for 489.05 points (4 mins 16 secs)
Average Score	354.94 (for 181 correct submissions)

Value	250
Submission Rate	198 / 201 (98.51%)
Success Rate	192 / 198 (96.97%)
High Score	sjelkjd for 249.18 points (1 mins 38 secs)
Average Score	225.89 (for 192 correct submissions)

There are many ways to solve this problem. First, we need a way of computing the cardinality of a number. There are more ways of doing this than can be discussed (some good, some bad, some downright crazy), but here are a few ideas. First, we can use bitwise operators to determine whether or not any particular bit is set. So we could simply do:

    for(int i = 0; i < 20; i++) {
        if(value & (1 << i)) {
            cardinality++;
        }
    }

Or, we could use some mechanism in our language to convert the value to a string representation in base 2, and then count how many characters in the string are '1'. Another method is to repeatedly check if the value is odd and divide by 2, until it is 0. Each time the value is odd indicates a 1 bit. That is:

    while(value) {
        if(value & 1) {
            cardinality++;
        }
        value >>= 1;
    }

Next is the problem of sorting, which has probably as many methods. However, the best method is always to use the libraries available with your language of choice. Use an existing sort implementation that allows you to override the comparison function. Then just implement the comparison function so that it compares cardinality first and then value next if cardinality is equal. For example, in C++:

bool cmp(int x, int y)
{
    if(cardinality(x) == cardinality(y)) {
        return x < y;
    }
    return cardinality(x) < cardinality(y);
}

vector<int> BinaryCardinality::arrange(vector<int> numbers)
{
    sort(numbers.begin(), numbers.end(), cmp);
    return numbers;
}

Value	900
Submission Rate	128 / 332 (38.55%)
Success Rate	102 / 128 (79.69%)
High Score	snewman for 890.53 points (2 mins 56 secs)
Average Score	651.01 (for 102 correct submissions)

The trick to computing the area of a convex polygon is to note that it is easy to subdivide a convex polygon into non-overlapping triangles. There are a number of ways to do this, but the most common and simplest to implement involves the cross product. MathWorld gives a general formula for calculating the area of a convex polygon in two dimensions in this article.

The method consists of iterating over all adjacent pairs of vertices. For each pair (x_i, y_i), (x_j, y_j) we compute x_iy_j - x_jy_i. One half the absolute value of the sum of these values over all pairs gives the area of the polygon.

Value	650
Submission Rate	128 / 201 (63.68%)
Success Rate	87 / 128 (67.97%)
High Score	SnapDragon for 622.79 points (5 mins 59 secs)
Average Score	414.42 (for 87 correct submissions)

The primary obstacle in this problem is making it efficient enough. It is easy to generate each formation in the series. However, without some cleverness, it is too costly to determine whether a particular formation is the same as any of the formations in a large set of previous formations.

The problem is that there are multiple ways to represent what is really the same formation. A formation can be rotated or reversed. What we need is some way to transform any representation into a particular, canonical form. One method is to generate all the equivalent representations to a particular representation, and choose the one that is lexicographically minimal. Then we only need to store one string in our history for each formation generated, and thus only have to compare the n^th formation to n - 1 strings to see if it is a repeat.

Value	900
Submission Rate	34 / 201 (16.92%)
Success Rate	19 / 34 (55.88%)
High Score	SnapDragon for 629.17 points (20 mins 36 secs)
Average Score	428.62 (for 19 correct submissions)

Problems of this type appear every now and then in Division One. The problem consists of determining the k^th value in a simple, generated sequence, where k may be so large as to make linear search infeasible.

In this case, we have two sequences to search in. Fortunately, the sequences can be approached in more or less the same way. We can easily figure out the location of certain values. Let us examine the first sequence, consisting of consecutive integers concatenated together.

In this first sequence, we need a way of counting how many digits are taken up by the concatenation of a range of consecutive integers. We can do this by grouping integers by length. There are 9 single-digit integers, so they take up the first 10 * 1 positions. Then there are 90 two-digit integers, so they take up the next 90 * 2 positions. Then there are 900 three-digit integers, and so on. Given an arbitrary position k, we can determine the length of the integer that contains the digit referenced by k by successively subtracting 9, 90, 900, etc. from k until doing so would make k negative.

At this point we know the length x of the integer that contains the digit referenced by k, as it is the number of subtractions we were able to make (plus 1). We also know which position m refers to where the value 10^x begins. If we divide k - m by x, we get the integer that contains the digit referenced by k. If we take the remainder of k - m divided by x, we get the digit (counting from the left).

This seems easy enough for the sequence of consecutive integers. But how do we do the squares? We do it by generalizing the first case a bit. The first method works because we know how many consecutive numbers there are of any given length. The same can be done with squares. Values from 1 to the floor of the square root of 10 (which is 3) have single-digit squares. Values above that that are less than the square root of 100 have two-digit squares. Values above that that are less than the square root of 1000 have three-digit squares. And so on. The same method as above can be applied to find the square root (from which the value we want obviously follows) of the value that k points to.

Once we have a method for finding the k^th digit of each sequence, we can find the k^th digit of the sum. This will obviously be either the sum of the corresponding digits of the two sequences, or that sum plus one (due to overflow from the right). We are not finished until we have a method of determining whether or not there is overflow from the right.

To check for overflow from the right, we find the sum for the digits corresponding to k + 1. If this sum is less than 9, there cannot be overflow. If this sum is greater than 9, there must be overflow. If the sum is 9, then we must repeat the process to see if there is overflow to the right of k + 1 to cause overflow in k. This is a simple enough function to implement once we have the ability of choosing arbitrary digits from the two sequences we are adding.