Get Time
statistics_w  Match Editorial
2005 TopCoder Open
Online Round 1

August 20, 2005

Match summary

The first round of the TCO was as exciting as could be expected. Give or take a tricky case on the easy, most coders zoomed through the first two problems. The hard problem, which was difficult enough to appear in an onsite round, gave the reds plenty of trouble. The 11 correct submissions are a testament to how strong our current batch of competitors are. An early wave of solutions filled the leader board with high scores, but none would pass systests. Correct solutions came much later, either as resubmits or late submissions. ivan_metelsky and elizarov took the top two places, followed closely by Polish coders tomek and malcin. malcin, who has competed in only a single SRM, is definitely someone to keep an eye on. If this round's hard problem was any indication of the later rounds, we have a great competition ahead of us. Good luck to everyone!

The Problems

RectangleError discuss it
Used as: Division One - Level One:
Value 250
Submission Rate 609 / 661 (92.13%)
Success Rate 469 / 609 (77.01%)
High Score mathijs for 246.26 points (3 mins 30 secs)
Average Score 194.28 (for 469 correct submissions)

Each length we must find is the hypotenuse of a triangle. To make the longest possible hypotenuse we use the maximum top length. Then, we try to make the left and right edges finish as far apart as possible. To make the shortest possible hypotenuse we use the minimum top length. Handling the left and right sides is a bit more difficult. If the ranges for the left and right ends overlap we get a degenerate triangle with a height of 0. Otherwise, we take the mininum of the absolute values of the following differences: rightMin-leftMax, leftMin-rightMax. Java code follows:

boolean r(double v, double m, double M) { return v ≥ m && v ≤ M; }
public double bottomRange(double topMin, double topMax, 
                          double leftMin, double leftMax, 
           double rightMin, double rightMax) {
   double M = 0, m = 0;
   if (r(rightMin,leftMin,leftMax) || r(rightMax,leftMin,leftMax) ||
       r(leftMin,rightMin,rightMax) || r(leftMax,rightMin,rightMax) ) {
      m = topMin;
   } else {
      double x = min(abs(leftMin-rightMax),abs(leftMax-rightMin));
      m = sqrt(x*x + topMin*topMin);
   double y = max(abs(leftMax-rightMin),abs(leftMin-rightMax));
   M = sqrt(y*y+topMax*topMax);
   return abs(M - m);

FibonacciSum discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 606 / 661 (91.68%)
Success Rate 510 / 606 (84.16%)
High Score for 496.73 points (2 mins 18 secs)
Average Score 409.72 (for 510 correct submissions)

Most coders solved this problem using dynamic programming. First construct an array containing all of the Fibonacci numbers. Then iteratively build another array whose ith element stores the minimum number of Fibonacci numbers that sum to i. Interestingly, a greedy approach works. The largest Fibonacci number that doesn't exceed k can always be used in the sum. The proof, which is left to the reader, will probably turn up in the round tables.

VariableSolve discuss it
Used as: Division One - Level Three:
Value 1100
Submission Rate 75 / 661 (11.35%)
Success Rate 11 / 75 (14.67%)
High Score elizarov for 533.25 points (39 mins 36 secs)
Average Score 428.16 (for 11 correct submissions)

The problem guaranteed that no variable would have degree higher than 2. This allows us to focus on solutions to linear and quadratic equations with integer coefficients. As the first step, we enumerate all possible solutions to these equations that could result from an input of 50 characters. These values are stored in a set as doubles. For each such value, and each letter that occurs in the input, we plug in, and then use algebra to reduce the resulting equation. If the equation reduces to 0 = 0 we know we have found a solution. If more than 2 solutions are found for a given variable, we know there are an infinite number of solutions.

By brett1479
TopCoder Member