Get Time
statistics_w  Match Editorial
SRM 203
Thursday, July 15, 2004

Match summary

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.

Brand-new contestant JongMan romped through Division Two with a 300-point win over his nearest competitor, weck. We'll see if this latest coding ace has the goods to make an impression in the major league. Rounding out the top three was andro, whose name means, I think, "man" in ancient Greek. Well done, man.

The Problems

UserName discuss it
Used as: Division Two - Level One:
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)
    if (i == existingNames.length)
    name = newName+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.

MatchMaking discuss it
Used as: Division Two - Level Two:
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)
Used as: Division One - Level One:
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.

UnLinker discuss it
Used as: Division Two - Level Three:
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(

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) {
    String s = "OMIT"+i;
    Matcher m = p.matcher(text);
    boolean b = m.find();
    if (!b)
    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.

TinSoldiers discuss it
Used as: Division One - Level Two:
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.

Palindromic line-ups are possible only if the number of ranks containing an odd number of soldiers is zero or one. Consider what would happen if two or more ranks contained an odd number of soldiers: at least one rank would have a different number of soldiers in each half of the line-up. Supposing there are no odd-numbered ranks, or only a single one whose odd man out stands in the center, the number of palindromes is the number of ways in which one half of the line-up can be constituted. This can be calculated in the same way as the total number of line-ups, but using half the number of soldiers.

  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.

TurfRoller discuss it
Used as: Division One - Level Three:
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))
    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)

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.

By Eeyore
TopCoder Member