
Match Editorial 
2003 TopCoder Collegiate Challenge
Round 1  W and MW RegionalThursday, February 20, 2003
Summary
The first round for the students in the W/MW regions was maybe a little easier than for those competing two days
ago. The medium and the hard problem had low acceptance rate; the medium had several potential traps and special
cases that you could fall in, and the hard involved geometry, a topic that can scare any TopCoder. Luckily the
easy problem was easier, and since all that mattered was getting a positive score to advance to the next round
(due to the low number of competitors), you only had to solve this one to be safe. bigg_nate got the top
score, an impressive 1415.93 points, more than 200 points ahead of the runnerup.
The Problems
FleasFleas
Used as: Level 1:
Value  250 
Submission Rate  136 / 154 (88.31%) 
Success Rate  116 / 136 (85.29%) 
High Score  malpt for 246.22 points 
Reference implementation: malpt (room 11)
Implementation
This problem, which is recursive in description, can easily
be solved with a recursive approach. Let f(n,k) be the total
number of fleas. Of the n fleas, k are infested with n more fleas
of which k5 are infested etc. So the general case is
f(n,k)=n+k*f(n,k5). The terminal case if when k<=0 in which
f(n,k)=n (none of the n fleas are infested, so we have n fleas).
It remains to deal with the overflow. If the function ever
wants to return a number greater than 10 million or 1,
we return 1. We must make sure not to calculate n+k*f(n,k5)
right away  first we must check if f(n,k5) is 1, then
we can calculate n+k*f(n,k5).
LongestRun
Used as: Level 2:
Value  500 
Submission Rate  83 / 154 (53.90%) 
Success Rate  31 / 83 (37.35%) 
High Score  bigg_nate for 405.00 points 
Reference implementation: Yarin (practice room)
Implementation
This problem can be divided into two steps: either the longest run is in one string only, or it is in a
concatenation of strings. The first case is trivial, we simply loop through all strings, and for each string we
loop through all characters. If a character is the same as the previous character, we increase a counter with 1;
otherwise we reset it to 1. The best result found over all strings is stored in some variable.
If the longest run is in the concatenation of several strings, it will be in the following format:
startstring intermediatestring intermediatestring ... stopstring
Clearly the intermediate strings can only be strings containing only one character, namely the last character of
startstring and the first character of stopstring (these two characters must of course also be the same).
We can now bruteforce search for the startstring and stopstring with the following algorithm (pseudocode):
loop through all possible startstrings
loop through all possible stopstrings
if startstring and stopstring are different
if last char in startstring is the same as first char in stopstring
let c=last char in startstring
let count=number of c characters at the end of startstring +
number of c characters at the beginning of stopstring
loop through all remaining strings
if string only contains letter c
count=count+string length
end if
end loop
if count is greater than best found so far
update best
end if
end if
end if
end loop
end loop
Tether
Used as: Level 3:
Value  1000 
Submission Rate  28 / 154 (18.18%) 
Success Rate  8 / 28 (28.57%) 
High Score  bigg_nate for 780.13 points 
Reference implementation: dmwright (room 9)
Implementation
This problem reduces to the following geometry problem: given a circle and two points, of which one point lies on
the circle, calculate the shortest distance between them under the constraints that you may not "walk"
(or whatever) inside the circle.
One of the points was (0,r), where r is the radius of the circle, while the other point is x,y. Again there are
two cases to consider: either the circle interferes with the shortest path, or it doesn't. In the latter case
(which happens when y <= r) it's simply the Euclidean distance between the two points, calculated using
Pythagoras formula.
In the trickier case, we start at 0,r (point A) and walk along the circle perimeter, and then at some point
(call it P) continue straight ahead to x,y (point B)  see figure. Clearly we should try to walk as little as
possible along the circle and as soon as possible in a straight line.
Using the notation in the picture, we see that the OPB is a right triangle  this will always be the case for the
shortest path! We can now set up the following equations:
OB = sqrt(x*x + y*y)
OP = r
BP = sqrt(OB*OB  OP*OP)
cos(a) = OP/OB
tan(b) = x/y
t = p  a  b;
AP = t*r
AB = AP + BP
It's slightly trickier than this because you have to consider in which
quadrant B is. This can be solved using atan2 instead of atan, and taking
the absolute value of x (which won't affect the answer because of symmetry).
For implementation details, see the reference solution.