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 singleround 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 quarterhour. 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. Brandnew contestant JongMan romped through Division Two with a 300point 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 ProblemsUserNameUsed as: Division Two  Level One:
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. MatchMakingUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 Used as: Division Two  Level Three:
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 So, yes, we could do all this work ourselves, which would amount to coding a finite automaton by hand. Then again, highlevel 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 computationaltheory 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://)([azAZ09.]+)[.](comorgeduinfotv)"); } 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 reallife problem, you'll be ready with the right tools. TinSoldiersUsed as: Division One  Level Two:
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 32bit integer, we should carry out the intermediate calculations using 64bit 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 lineup is
C(N, n0) = N*(N1)*(N2)*...*(Nn0+1) / (n0*(n01)*(n02)*...*1)
We can code up a Java function to compute this number with a pair of
long C(long m, long n) { long tot = 1; long i = m; while (i > mn) tot *= i; i = n; while (i > 1) tot /= i; return tot; }
After placing the highestranked soldiers, we want to place those
of the secondhighest rank, who number, let us say, n1. This can be
done in
The Java code below computes the number of permutations and assigns
it to
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 lineups 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 lineups 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 lineup. Supposing there are no oddnumbered 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 lineup can be constituted. This can be calculated in the same way as the total number of lineups, 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 Used as: Division One  Level Three:
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 endtoend, 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 topleft turf strip intersects the topleft 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 topleft 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 topleft corner of the lawn and calculating the number of pieces in the resulting layout, then nudging the topleft 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 topleft 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 60by90 lawn, with 60by25 turf strips laid at an angle of 39 degrees. Suppose that we lay the topleft turf strip flush against the topleft 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 bottomleft corner of the lawn is the origin of a Cartesian coordinate system, then the line running through the 0points intercepts the yaxis, where x=0, at y=9025/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 9025/cos(39º) below the previous yintercept. At the right end, however, the furthest extent of the turf row intersects the topright corner of the lawn. It would be incorrect to take the right 2point 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 topright corner.
At the left end of the turf row, similarly, the salient point falls on the bottomleft 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 yintercepts 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 floatingpoint 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
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
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  (i1)*b/Math.cos(a) + nudge >= 0.0 ? 0.0 : (h + (i1)*b/Math.cos(a)  nudge)/Math.tan(a); if (left_x > w) break; }
In the above code, our first guess for the value of
right_y = h; right_x = (i*b/Math.cos(a)  nudge)/Math.tan(a); if (right_x > w) { right_x = w; right_y = ((i1)*b/Math.cos(a)  nudge)/Math.tan(a) <= w ? h : h  (i1)*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 = 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 turfstrip 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. 
