Match Editorial

It was a damp, gray morning on the East Coast of the United States as TopCoder's earliest ever single-round match got under way, but the sun broke through over antimatter's head and crowned him with a victorious halo for dispatching the first two Division One problems in a quarter-hour. At the other end of the world, it was near bedtime in John Dethridge's Australian quarters, but he stayed up for a spell of coding that earned him a distant second. Meanwhile, back in Boston, jms137 misfired but a single neuron in the course of the match, leading to the measly two keystrokes that compromised his solution to the third and hardest problem, relegating him to third place.

The Problems

Value	250
Submission Rate	100 / 113 (88.50%)
Success Rate	87 / 100 (87.00%)
High Score	JongMan for 243.83 points (4 mins 32 secs)
Average Score	201.10 (for 87 correct submissions)

Given a list of existing usernames, we are to determine whether a newly requested username already figures among them. If so, we must append to it the lowest possible number to make a new username. An overly elaborate approach would be to look at the existing usernames and start compiling statistics that can eventually be used to determine the permissible set of new usernames.

A better way is to start by looking at the new username and, if it is taken, trying out numbers to append to it. The problem specifications imply that we should start from 1 and progress through the natural numbers until we've found a new username.

public String newMember(String[] existingNames, String newName) {
  String name = newName;
  int n = 1;
  while (true) {
    int i;
    for (i = 0; i < existingNames.length; i++)
      if (existingNames[i].compareTo(name) == 0)
        break;
    if (i == existingNames.length)
      break;
    name = newName+n;
    n++;
  }
  return name;
}

The above code uses the inefficient method of linear search to locate existing usernames, but it will do for the small problem instances we are dealing with. For more serious input sizes, you would want to use something much faster, such as binary search or hashing. You might like to study the documentation for the Java classes Arrays and HashSet to prepare for future problems of this kind.

Value	600
Submission Rate	59 / 113 (52.21%)
Success Rate	43 / 59 (72.88%)
High Score	JongMan for 539.21 points (9 mins 45 secs)
Average Score	355.33 (for 43 correct submissions)

Value	325
Submission Rate	106 / 114 (92.98%)
Success Rate	90 / 106 (84.91%)
High Score	antimatter for 309.84 points (6 mins 20 secs)
Average Score	241.89 (for 90 correct submissions)

The gist of this tedious problem statement is that we must find the lexicographically least woman's name, consider the men with whom she has the greatest number of answers in common, and take the lexicographically least of the men's names. The number of common answers can be found by a pairwise comparison of the characters in each answer string.

As for lexicographic ordering, Java's compareTo function and the C library's strcmp are wise to it. Heaven help you if you don't know your language's built-in facility for lexicographic comparison. You would lose precious seconds or minutes coding up a recursive function or some kind of loop to carry out this task.

Value	900
Submission Rate	12 / 113 (10.62%)
Success Rate	4 / 12 (33.33%)
High Score	JongMan for 678.70 points (17 mins 27 secs)
Average Score	493.82 (for 4 correct submissions)

Given a simple definition of weblinks, we are to replace each weblink in a piece of text with a numbered tag. The chief difficulty consists in identifying the spans of text that constitute weblinks. The hard way to go about this is to write a function that, starting from a given point in the text, looks for the longest substring that matches the weblink definition.

We would start by checking for the substring http://, optionally followed by the www. substring. If that failed, we would check for www. alone. If one of these prefixes matched, we would start looking just beyond it for the longest substring that looks like a domain. So if we found at least one valid character (letter, numeral, or period), we would continue scanning to the end of the longest such sequence of characters. Finally, we would look for one of the five permitted suffixes. If one of them were present, we would know that the span of text stretching from the start of the prefix to the end of the suffix was a weblink as defined in the text.

So, yes, we could do all this work ourselves, which would amount to coding a finite automaton by hand. Then again, high-level languages such as Java offer a formalism called the regular expression, or regex for short, that lets us express finite automata in a compact form and make the compiler do all the dirty work. If you're not already familiar with regex syntax, you should read up on it at earliest convenience. Any good computational-theory textbook will do, or, in a pinch, the Python reference.

Among the many possible ways to write the weblink pattern as a regex, we might choose the following.

public String clean(String text) {
  Pattern p = Pattern.compile(
    "((http://)?www[.]|http://)([a-zA-Z0-9.]+)[.](com|org|edu|info|tv)");
}

After compiling the regex, we repeatedly apply it to the text and substitute for each matching span a tag made with the help of the loop counter.

  int i = 0;
  while (true) {
    i++;
    String s = "OMIT"+i;
    Matcher m = p.matcher(text);
    boolean b = m.find();
    if (!b)
      break;
    text = text.substring(0, m.start()) + s + text.substring(m.end());
  }
  return text;

There are more concise ways to accomplish the above, as you will find after perusing the Java specifications and trying your hand at some examples. The next time a text pattern like this shows up in TopCoder or in a real-life problem, you'll be ready with the right tools.

Value	500
Submission Rate	69 / 114 (60.53%)
Success Rate	50 / 69 (72.46%)
High Score	antimatter for 462.73 points (8 mins 11 secs)
Average Score	312.94 (for 50 correct submissions)

Given a number of military ranks and the number of soldiers in each rank, we are to calculate the number of ways these soldiers can be lined up, not counting reflected configurations. Since this number can range into the billions, we don't have enough time to generate all the permutations one by one. But we must also be careful in calculating the number directly. Although the final result is guaranteed to fit into a 32-bit integer, we should carry out the intermediate calculations using 64-bit variables in order to avoid overflow along the way.

If the total number of soldiers is N and the number of soldiers in the highest rank is n0, then the number of ways to place these soldiers in the line-up is C(N, n0), pronounced "N choose n0". Any combinatorics primer will tell you, if you don't know already, that C(N, n0) is N!/((N-n0)!*n0!). (For a quick technical summary, consult the Mathworld article.) Another way to write this is the following.

C(N, n0) = N*(N-1)*(N-2)*...*(N-n0+1) / (n0*(n0-1)*(n0-2)*...*1)

We can code up a Java function to compute this number with a pair of while loops.

long C(long m, long n) {
  long tot = 1;
  long i = m;
  while (i > m-n)
    tot *= i--;
  i = n;
  while (i > 1)
    tot /= i--;
  return tot;
}

After placing the highest-ranked soldiers, we want to place those of the second-highest rank, who number, let us say, n1. This can be done in C(N-n0, n1) ways. For the next rank, there are C(N-n0-n1, n2) ways, and so forth. The product of all these combinations is the total number of permutations of the soldiers, or the number of line-ups including reflections.

The Java code below computes the number of permutations and assigns it to tot. In the meantime, the variable odd tells us how many ranks have an odd number of soldiers.

long doit(int rankCounts[]) {
  long tot = 1, sym = 0, Np = 0, N, odd = 0;
  int i;
  for (i = 0; i < rankCounts.length; i++) {
    Np += rankCounts[i];
    odd += rankCounts[i]%2;
  }
  for (N = Np, i = 1; i < rankCounts.length; N -= rankCounts[i], i++)
    tot *= C(N, rankCounts[i]);

How do we calculate the number of reflected permutations? A nice way to go about it is to find the number of palindromes, which are line-ups that look the same forward and backward, meaning that they have no reflection. This will tell us, by negation, how many permutations are indeed reflected.

  if (Np%2 == odd) {
    sym = 1;
    N = Np/2;
    for (i = 1; i < rankCounts.length; N -= rankCounts[i]/2, i++)
      sym *= C(N, rankCounts[i]/2);
  }
  return (tot+sym)/2;
}

Half the original permutations were reflected, except for the ones that were palindromic, so we divide tot by two and add back to it half of sym to obtain the final result.

Value	1000
Submission Rate	3 / 114 (2.63%)
Success Rate	0 / 3 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

The friendly neighborhood raccoons have agreed to cover a rectangular lawn with rectangular turf strips laid at a specific angle. Our job is merely to calculate the minimum number of turf strips required. Since the problem stipulates that the strips' shorter edges are laid precisely end-to-end, their longer edges must form a series of parallel lines separated by the breadth of the turf strips. It is also implied that the placement of a single turf strip, for instance at the top left corner, determines the placement of all remaining turf strips. It may appear at first sight that an optimal layout will result if the upper edge of the top-left turf strip intersects the top-left corner of the lawn, but the second test case shows that this is not so.

A talented geometer will perhaps see a way to analytically calculate the optimal placement of the top-left turf strip. Given the coarse precision constraints of the problem, however, a numerical approach will do. We can start by fitting a turf strip tightly to the top-left corner of the lawn and calculating the number of pieces in the resulting layout, then nudging the top-left turf strip upward by a small increment and repeating the calculation. After we've nudged the layout enough times to return it to the original configuration, our final answer is the minimum number of turf strips over all iterations.

In a given iteration, once the top-left turf strip has decided the placement of the rows, we can push the leftmost turf strip within each row tightly against the left border of the lawn without loss of optimality. Now we can calculate the length of the whole row and divide by the length of a single turf strip, rounding up to the nearest integer, to find the number of pieces in this row. The length of the row, in turn, can be determined by trigonometrically locating a few crucial points along the lawn border and considering the distances they span.

The diagram below illustrates these points for the first test case. Recall that we have a 60-by-90 lawn, with 60-by-25 turf strips laid at an angle of 39 degrees. Suppose that we lay the top-left turf strip flush against the top-left corner. The stretch of lawn that must be covered by this turf row stretches from a point on the left border, marked 0, to a point on the top border, also marked 0. If we consider that the bottom-left corner of the lawn is the origin of a Cartesian coordinate system, then the line running through the 0-points intercepts the y-axis, where x=0, at y=90-25/cos(39º). (We're denoting the angles in degrees here, but they should be converted to radians before being passed to standard math functions.) Furthermore, this line intercepts the top edge, where y=60, at x=(25/cos(39º))/tan(39º). As long as the turf row intercepts only the left and top borders of the lawn, the distance between these two points is exactly the length of the row.

In the next row, the leftmost turf strip cuts through the left border at a point 90-25/cos(39º) below the previous y-intercept. At the right end, however, the furthest extent of the turf row intersects the top-right corner of the lawn. It would be incorrect to take the right 2-point as the furthest extent of the second row. We can discover such cases systematically on the following principle. If a turf row's bottom edge intersects the right border while the previous row's bottom edge intersects the top border, then the salient point must be the top-right corner.

At the left end of the turf row, similarly, the salient point falls on the bottom-left corner if the bottom edge intersects the bottom lawn border while the previous row's bottom edge intersects the left border. In all other cases, we need only consider the intersection of the edge itself. Notice that the y-intercepts of each line are spaced at intervals of 25/cos(39º) starting from the top. This fact, together with the knowledge that the slope of each line is 39 degrees, is sufficient to calculate the intersections at all borders.

It is vital to observe that in turf rows where one extremity is marked by a corner of the lawn, the distance between the two points is longer than the length of the row. In our example, this is the case with point pairs 1 and 2. The remedy is to project the span onto a line angled at 39 degrees. By considering the triangle formed by the span and the bottom edge of the nearest turf strip, we see that this projection can be accomplished by taking the cosine of the difference between 39 degrees and the angle of the span. This latter is just the arctangent of its slope.

Before launching into any trigonometry, we can check for the special cases where turf strips are laid at right angles to the lawn. In such cases, we can compute the answer with integer division, as in the Java code below. Otherwise, we promote the input parameters to floating-point numbers and start the heavy lifting.

  if (stripAngle == 0 || stripAngle == 90) {
    int t = lawnWidth;
    if (stripAngle == 90) {
    lawnWidth = lawnHeight;
    lawnHeight = t;
    }
    t = lawnWidth/stripLength + (lawnWidth%stripLength==0 ? 0 : 1);
    t *= lawnHeight/stripBreadth + (lawnHeight%stripBreadth==0 ? 0 : 1);
    return t;
  }
  return doit(lawnWidth, lawnHeight, Math.toRadians(stripAngle),
    stripLength, stripBreadth);

In the following solution, we nudge the layout by an increment of 0.05 at each iteration. Further below, we shall refer to the loop counter i when we need to calculate the total amount by which the turf rows have been nudged upward.

int doit(double w, double h, double a, double l, double b) {
  double left_x, left_y, right_x, right_y, dy, dx, S, D;
  int min = -1, ct, i = 0, n = 0;
  while (true) {
    double nudge = (n++)*0.05;
    if (nudge > b/Math.cos(a))
      break;
    ct = i = 0;

The coordinates of the left point of intersection for the current turf row are called left_x and left_y, while those for the right point are right_x and right_y. We continue iterating and computing successive pairs of points until left_x falls beyond the right lawn border, where x=w.

    while (true) {
      left_x = 0.0;
      left_y = h - (++i)*b/Math.cos(a) + nudge;
      if (left_y < 0) {
        left_y = 0;
        left_x = h - (i-1)*b/Math.cos(a) + nudge >= 0.0 ? 0.0
          : (-h + (i-1)*b/Math.cos(a) - nudge)/Math.tan(a);
        if (left_x > w)
          break;
      }

In the above code, our first guess for the value of left_y is the y-intercept of the current turf row's bottom edge. If the y-intercept falls below the the bottom lawn border, we compute the actual point of intersection between the turf row's bottom edge and the bottom border. Next, we check whether this is the first such intersection we have computed. If so, we use the bottom-left corner instead. Similar reasoning applies in the calculation of the right point, shown below. The difference is that our first guess lies on the top lawn border, where y=h, and our second on the right border, where x=w.

      right_y = h;
      right_x = (i*b/Math.cos(a) - nudge)/Math.tan(a);
      if (right_x > w) {
        right_x = w;
        right_y = ((i-1)*b/Math.cos(a) - nudge)/Math.tan(a) <= w ? h
          : h - (i-1)*b/Math.cos(a) + nudge + w*Math.tan(a);
      }

We now consider the line segment defined by the left and right points. Its rise and run are computed below as dy and dx. Its length is D, but the length of its projection onto a line of angle a is S, which is precisely the length of the current turf row.

      dy = right_y - left_y;
      dx = right_x - left_x;
      D = Math.sqrt(dy*dy + dx*dx);
      S = D*Math.cos(Math.atan(dy/dx)-a);
      ct += (int) (Math.ceil(S/l));
    }

All that remains is to keep track of the minimum turf-strip count between nudges.

    if (min == -1 || ct < min)
      min = ct;
  }
  return min;
}

Raccoons are good at landscaping, but the trigonometry is best left to humans.