Online Round 1 August 20, 2005 Match summaryThe 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 ProblemsRectangleErrorUsed as: Division One  Level One:
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: rightMinleftMax, leftMinrightMax. 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(leftMinrightMax),abs(leftMaxrightMin)); m = sqrt(x*x + topMin*topMin); } double y = max(abs(leftMaxrightMin),abs(leftMinrightMax)); M = sqrt(y*y+topMax*topMax); return abs(M  m); }FibonacciSum Used as: Division One  Level Two:
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. VariableSolveUsed as: Division One  Level Three:
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. 
