Match Editorials

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 Problems

TextProcessor
Used as: Division One - Level One:

Value	250
Submission Rate	124 / 130 (95.38%)
Success Rate	119 / 124 (95.97%)
High Score	Zuza for 249.63 points (1 mins 5 secs)
Average Score	226.04 (for 119 correct submissions)

This problem asks you to take a String and
1. Remove all of the non-letter characters (i.e., digits and spaces)
2. Convert the letters to lowercase
3. Sort the letters

Here is fpavetic's code (C++), which is nice and short:

    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
Used as: Division One - Level Two:

Value	500
Submission Rate	110 / 130 (84.62%)
Success Rate	95 / 110 (86.36%)
High Score	Zuza for 497.65 points (1 mins 57 secs)
Average Score	391.64 (for 95 correct submissions)

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 5-best;

EnclosingRectangle
Used as: Division One - Level Three:

Value	1000
Submission Rate	36 / 130 (27.69%)
Success Rate	14 / 36 (38.89%)
High Score	Zuza for 781.49 points (15 mins 59 secs)
Average Score	536.45 (for 14 correct submissions)

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 x-coordinate of the left edge of the smallest rectangle must be one less than the x-coordinate 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 x-coordinate of the right edge must be one more than the x-coordinate of one of the given points; the y-coordinate of the top edge must be one more than the y-coordinate of one of the given points (this assumes that the y-coordinate increases from bottom to top); and the y-coordinate of the bottom edge must be one less than the y-coordinate 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⁴ 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 smallest-area 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⁵) time, which would time out for N=100. (It was our intention to not have O(N⁵) solutions pass, and force the coder to find an optimization.)

There are probably many ways to optimize this O(N⁵) solution, and let me describe one of them. The idea of this optimization belongs to brett1479. First, sort the x-coordinates of the given points and call them x₀, x₁, ..., x_m. Next, sort the y-coordinates of the given points and call them y₀, y₁, ..., y_n. We keep a two-dimensional 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³) 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][c-1] - cnts[a-1][d] + cnts[a-1][c-1].

This value can be computed in constant time, thanks to the O(N³) precomputation of cnts. Thus, we have reduced the running time of the solution to O(N⁴), which runs within the time limits when N=100.