Wednesday, October 1, 2003 Match summary 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 ProblemsWorkshopUsed as: Division Two  Level One:
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; }BinaryCardinality Used as: Division Two  Level Two: Used as: Division One  Level One:
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 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; }ConvexPolygon Used as: Division Two  Level Three:
The trick to computing the area of a convex polygon is to note that it is easy to subdivide a convex polygon into nonoverlapping 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_{i}y_{j}  x_{j}y_{i}. One half the absolute value of the sum of these values over all pairs gives the area of the polygon. CircleBugsUsed as: Division One  Level Two:
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. LongNumberUsed as: Division One  Level Three:
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 singledigit integers, so they take up the first 10 * 1 positions. Then there are 90 twodigit integers, so they take up the next 90 * 2 positions. Then there are 900 threedigit 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 singledigit squares. Values above that that are less than the square root of 100 have twodigit squares. Values above that that are less than the square root of 1000 have threedigit 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. 
