Monday, July 17, 2006 Match summary One hundred thirty coders participated in the TopCoder High School SRM 7. Zuza put on an impressive performance, getting the fastest times on all three problems, and leading the contest from start to finish. Weiqi was a close second, followed by twelve other coders who solved all three problems correctly. Congratulations to all of the participants. The first two problems turned out to be relatively straightforward, with the majority of the coders solving both. The third problem was a little trickier and required some thought as to how to make the program run within the time limits. The ProblemsTextProcessor
This problem asks you to take a String and string ret; for( int i=0; i < (int)text.size(); ++i ) if( isalpha( text[i] ) ) ret += tolower( text[i] ); sort( ret.begin(), ret.end() ); return ret; An alternative to calling a sorting routine is to keep track of the frequency of each letter (after converting the String to lowercase) and then loop from 'a' to 'z', printing each letter however many times it appears in the input. See duachuotbeo's solution for this approach.
StraightArray
This problem was inspired by the game of poker, where a straight is five cards of sequential rank. For this problem, we want to find an integer N such that the five numbers (N, N+1, N+2, N+3, N+4) contains the most numbers from the input. From that, we would be able to figure out the minimum number of integers that we need to add to the given array to make it a straight. One observation is that we only need to consider integers N where N is from the input. The reason is that we can keep "shifting" the straight to the right (i.e., increase it by one) until the first number comes from the input, and we lose nothing by this process. Since the input is limited to fifty numbers, this approach is feasible. Nearly all of the coders went with this approach or something similar. Pseudocode follows: int best = 0; for each int x from the input int count = the number of ints from the input that appear in (x, x+1, x+2, x+3, x+4) if (count > best) best = count; return 5best;
EnclosingRectangle
This problem had an unconventional input format because we wanted to be able to have one hundred points in the input. (Apparently, you can only pass in up to fifty ints in a TopCoder problem.) So the first step is to convert the input from Strings to integer points. A key observation is that we only need to consider certain coordinates for the corners of the rectangle. The xcoordinate of the left edge of the smallest rectangle must be one less than the xcoordinate of one of the given points. Why is that? If it was not the case, we could move the left edge of the rectangle to the right by one unit. The new rectangle would contain the same number of points but have less area, contradicting the claim that it was the smallest rectangle. Similarly, the xcoordinate of the right edge must be one more than the xcoordinate of one of the given points; the ycoordinate of the top edge must be one more than the ycoordinate of one of the given points (this assumes that the ycoordinate increases from bottom to top); and the ycoordinate of the bottom edge must be one less than the ycoordinate of one of the given points. If we let N be the number of points in the input, then we see that there are up to N^{4} rectangles to try out. For each rectangle, we count how many points lie in the interior. If that number is at least N/2, then we calculate the area of the rectangle, see if it is the smallest one we have seen so far, and update the smallestarea variable if necessary. A straightforward way to count the number of points inside a rectangle is to loop over all N points and compare the coordinates. This would yield an overall solution running in O(N^{5}) time, which would time out for N=100. (It was our intention to not have O(N^{5}) solutions pass, and force the coder to find an optimization.) There are probably many ways to optimize this O(N^{5}) solution, and let me describe one of them. The idea of this optimization belongs to brett1479. First, sort the xcoordinates of the given points and call them x_{0}, x_{1}, ..., x_{m}. Next, sort the ycoordinates of the given points and call them y_{0}, y_{1}, ..., y_{n}. We keep a twodimensional int array called cnts, where cnts[i][j] denotes the number of points on or inside the rectangle with corners at (0,0) and (x_{i}, y_{j}). This array can be computed in O(N^{3}) time by brute force. Then the number of points on or inside the rectangle with corners (x_{a}, y_{c}) and (x_{b}, y_{d}), where a<b and c<d, is cnts[b][d]  cnts[b][c1]  cnts[a1][d] + cnts[a1][c1]. This value can be computed in constant time, thanks to the O(N^{3}) precomputation of cnts. Thus, we have reduced the running time of the solution to O(N^{4}), which runs within the time limits when N=100. 
