Wednesday, August 4, 2004 Match summary After winning Division II on Saturday, TopCoder member _ went two for two, winning Division I by a margin of over 140 points. _ is now red, with a ranking of 2378 after competing in only two matches. SnapDragon came in second, the only other coder to solve all three problems. Rounding out the top five were Eryx, jms137, and radeye. In Division II, anikov took the title by a margin of almost 200 points of alsomagic. These top two were the only coders to solve all three problems. gmenhorn, ToadX, and lujo (the only other coder to solve the 1000point problem) took the 3rd, 4th, and 5th spots.
The ProblemsBitsUsed as: Division Two  Level One:
With b bits, computers can represent numbers in the range 0 to 2^{b}1. So, this problem is asking you to find the smallest b such that 2^{b} > n. This can be done by counting how many times you must divide n by 2 (throwing away the remainder) until you get zero: int b = 0; while (n > 0) { n = n / 2; b++; } return b; Others solved the problem by using Java's Integer.toBinaryString() method (or a similar function from their personal library of prewritten code), and returning the length of the string. OmahaLowUsed as: Division Two  Level Two: Used as: Division One  Level One:
Many people tried to solve this problem in clever ways, but this problem is most easily solved by brute force. Five nested loops can easily give you all possible combinations of 3 of the five shared cards and 2 of the player's four cards: for (int s1=0; s<5; s1++) for (int s2=s1+1; s2<5; s2++) for (int s3=s2+1; s3<5; s3++) for (int p1=0; p1<4; p1++) for (int p2=p1+1; p2<4; p2++) { string hand; hand += sharedCards[s1]; hand += sharedCards[s2]; hand += sharedCards[s3]; hand += sharedCards[p1]; hand += sharedCards[p2]; ... } Inside the loop, you sort the characters in the string (high to low), make sure it's a legal low hand, and then check if it's lower than the lowest low hand you've seen so far. That's not to say that there is anything wrong with clever solutions. SnapDragon made use of STL sort() and next_permutation() methods and noticed that a simple string comparison was sufficient to test of one hand was lower than another, and coded up an elegant solution in just over 5 minutes (the fastest time for this problem). UntypesetUsed as: Division Two  Level Three:
This problem was actually quite straightforward, and the example in the problem statement basically spelled out how to solve it. But, as evidenced by only 3 successful solutions (out of 5 submissions total), the implementation was a bit on the tricky side. This problem is best solved by recursion. You write a recursive function that takes an array of strings as input and returns an integer. This function determines if the input is an addition, division, or integer constant. If the input is an integer constant, the function simply returns the value of that integer. Otherwise, the input is addition or division, and the function breaks the array of strings into two subexpressions (the left and right for addition, or the top and bottom for subtraction). It then recursively calls itself on the two subexpressions, adds or divides the two results, and returns that value. To determine if the input is an integer, addition, or subtraction, loop over all the rows and see if any contain only '' characters. If so, then it is division. Otherwise, loop over all columns and see if any contain a row of only spaces except for a single '+' character. If so, then it is addition. Otherwise, since the input is guaranteed to be legal and wellformed, it must be an integer constant. Dealing with the spaces inserted around subexpressions can be done at the top of the recursive function, by simply trimming all blank rows and columns along the 4 edges. See anikov's solution for an example of a nice implementation of this solution. SensorGridUsed as: Division One  Level Two:
People tried many approaches to solving this problem, from a bruteforce O(n^5) search to some very clever algorithms. It was my intention that the input size would be too large for O(n^5) searches, but they squeaked by in the time allowed. Computers are just too fast these days... A helpful observation is that the largest rectangle will be bounded on all four sides by a defective sensor or the edge of the grid. The O(n^5) search loops over all points (and relevant edge) for each of the 4 sides. Then with a 5th loop, it checks that no other points are inside this rectangle. If there are none, then it checks if this rectangle is larger that the largest rectangle found so far (or higher if they have the same area, or further to the left if they have the same area and vertical position, or wider if they have the same area and upperleft position). For an example of this approach see Ruberik's solution, which he coded in under 11 and a half minutes for the fastest time on this problem. jms137 improved this search to O(n^4) with three loops to bound the left, right, and top sides of the rectangle, and then a fourth loop to find the highest point inside this region to give the bottom edge. _ and SnapDragon both implemented elegant O(n^3) solutions which are worth taking a look at. Cosmin.ro claims to have an O(n^2) solution, which I hope he will share with us in the forums. HexagonIntersectionsUsed as: Division One  Level Three:
This problem was simple to state, but the solution was elusive. When dealing with geometry, you should be very worried about using floatingpoint numbers in your solution, as they can lead to numerical inaccuracies. You should be even more worried when you see a problem that requires some exact math as this one does: you must count hexagons if the line segment passes through the interior, but not if it only intersects an edge or a corner. Nonetheless, _ got his solution to work using floating point for the fastest time for this problem. On the other hand, SnapDragon, the only other coder to solve this problem, used integer math. That is what I had in mind for this problem, and I will describe how this works below. The first important thing to realize is that you can convert the hexagonal grid so that the corners lie on integer coordinates. An affine transformation (translation, scaling, rotation, shearing, and reflection) applied to any twodimensional figure will preserve straight lines. That is to say, you can draw a straight line on a hexagonal grid, and then rotate, scale, and shear the image all you want, and the hexagons will still have 6 straight edges, and the line will still be straight and pass through the same hexagons as it did before. By scaling the grid vertically and shearing it horizontally, you can get an equivalent grid shown in the figure below: The transformation from coordinates identifying hexagon centers given in the problem to coordinates on this grid is: x^{'} = x + y To simplify things a bit, you can first translate the line so that it starts at the origin (by subtracting (x0,y0) from (x1,y1)). Then, using symmetry, you can reduce the range of directions of the line to limit the number of cases you need to consider. In my solution, I rotated the line so that it would always point in the the range shown by the blue arrows in the figure below. Once everything is set up, you start at the origin and walk from hexagon to hexagon until you reach the destination. Deciding which hexagon to move to can be done by checking what sides of the current hexagon's corners the line passes. Referring to the figure above:
Note that the range of possible directions for the line limit the number of cases you need to consider to those cases above. Testing which side of a point the line passes is done with a twodimensional cross product: c = (x1 * corner_y)  (y1 * corner_x)If c is negative, the line passes to the left, if c is positive the line passes to the right, and if c is zero, the line passes through the point. 
