Wednesday, June 16, 2004 Match summary SRM 199 faced TopCoders with two of their most common fears: probability and geometry. venco took the top spot in DivisionI with the only (out of nine submitted) passing solution to the 1000point problem. A successful challenge by jonmac lifted him up into second place, over thirdplace nullspace who's rating is on track to shoot past the 2200 mark. In DivisionII, an unsuccesful challenge by Savior was not enough to knock him out of the top spot, as he solved the 1000point problem in only 12 minutes and saw his rating jump 348 to bring him within 5 points of DivisionI. loveislife and Sputnik finished second and third, separated by less than 20 points.
The ProblemsStringMultUsed as: Division Two  Level One:
This problem required a program to multiply a string sFactor by an integer iFactor, according to a provided definition for performing such a multiplication. The first step is to reverse sFactor if iFactor is negative. Then, to an empty string, concatenate abs(iFactor) copies of sFactor. In pseudocode: if iFactor < 0 { reverse sFactor iFactor = iFactor } ret = "" for i = 1 to iFactor { ret = ret + sfactor } return ret If implemented correctly, you do not need to worry about the special cases of the string being empty or the integer being zero, although sometimes it's easier to just code the special cases explicitly than to convince yourself that your program handles them correctly. TriangleCountUsed as: Division Two  Level Two: Used as: Division One  Level One:
To solve this problem, coders had to write a program to return the total number of triangles (of any size) in a piece of a triangular grid. This is by no means an original problem  see the "Triangular Tiling" article on mathworld.wolfram.com. Some people solved this problem by counting the number of triangles for the first few sizes, and then entering them into the OnLine Encyclopedia of Integer Sequences to find the closedform solution. However, even without finding a closedform solution, it was a simple matter to loop over all the triangles and count them. See venco's program for a nice example of such a solution. TransposeUsed as: Division Two  Level Three:
Taking the transpose of a nonsquare matrix inplace sounds like a simple enough problem, but an elegant algorithm is elusive. The key is to come up with a formula that gives you, for a given index in the list, the new index that this element must be copied to. This formula can be derived as follows:
By iterating the above formula, you will eventually return to your starting element, and there will likely be many such cycles. Copying each element to its next position in a cycle of n elements requires n1 swaps. So, to compute the total number of swaps required to copy each element to its next position (and thus inverting the matrix), you simply must find all the cycles, subtract 1 from their lengths, and compute the sum. Note that since the sum of all the cycle lengths must be M*N, this is equivalent to M*N minus the number of cycles. See sputnik's program for a clean implementation of this solution. ChipRaceUsed as: Division One  Level Two:
Problems dealing with probability intimidate many people, but the nice thing about this problem is that once you figure out how to solve it, the program can actually be quite short and elegant. The probability of a player winning a chip is equal to the sum of the probabilities of all the different ways that can happen. That is, it is the probability that he will win the first chip, plus the probability that he will win the second chip, plus the probability that he will win the third chip, etc. The probability that he will win the first chip is the chance that he has the highest card, which is simply the number of cards he gets divided by the total number of cards. The probability that he will win the second chip is the chance that he has the highest card of those remaining after some other player wins the first chip. This can computed by looping over all the other players and taking the sum of the chance that that other player wins the first chip, times the chance that our first player wins the second chip (his number of cards divided by the number of cards remaining). The probabilities for winning the third and later chips can be computed similarly. This can be coded very succinctly as a recursive function. For a nice example, see gilbert's solution, who, incidentally, took an early lead after submitting his first two problems, only to knocked down later by a successful challenge to his 250point problem. The small limits to the input parameters allow a good recursive solution to work without the need for memoization. Of those who submitted this problem, over three quarters got it right. The most common reasons for failing were due to precision problems or timing out on the worst possible case (10 fours). ClosestPointsUsed as: Division One  Level Three:
At first, this problem seems simple: generate a bunch of random points and find the closest pair. However, the range of the input parameters (up to 150,000 points with coordinates 1,000,000 to 999,999, obviously prevents a simple brute force solution for running in under eight seconds. The key to many TopCoder problems is to identify which algorithm to use, but my goal for this problem was to emphasize selecting a good data structure. This problem can be solved with the use of a "spatial" data structure, which arranges the points based on their position in order to avoid testing pairs of points that cannot possibly be the closest. The simplest such data structure is a fixed grid, where space is divided up into a threedimensional array of boxes, and as points are generated they are sorted into their corresponding boxes. Provided that the boxes are sufficiently populated, points only need to be compared to other points in their box and to the points in the 26 neighboring boxes. Such a solution would fail if there were too few points, and the closest pair were not in neighboring boxes. It would also time out of the points were not evenly distributed, and all of the points ended up in just a few boxes. Fortunately, the pseudorandom number generator used in this problem distributes the points quite evenly. Another solution is to use an "octree" or a "kdtree", which are threedimensional versions of a binary trees. Each node of an octree is divided in x, y, and z, resulting in eight children. As points are inserted into the octree, nodes are adaptive subdivided when they contain too many points. Finding the closest pair of points can be accomplished by recursively comparing the octree to itself, and stopping the recursion early at each step when the two nodes being compared are farther apart than the closest pair found so far. A "kdtree" (used by venco for the only passing solution to this problem) is more efficient, splitting each node by a single plane, chosen to divide the points along the major axis of their bounding box. Several people attempted to solve this problem by sorting the points based only on their x coordinate. They then did an N^{2} comparison, but visited the points in sorted order, and broke out of the inner loop early when the difference of their xcoordinate was larger than the closest distance found so far. These solutions actually worked fine for the largest parameter values when the points were spread out far apart. But when the range of coordinates was reduced, and there were several thousand points with each possible x coordinate, these solutions still compared too many points. 
