Match Editorial

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

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);
}   

Value	500
Submission Rate	606 / 661 (91.68%)
Success Rate	510 / 606 (84.16%)
High Score	Cosmin.ro 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.

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.