Tuesday, December 4, 2007 Match summarySRM 380 wasn't a usual match, it was a challenger's good dream. All problems, except for Div2Easy provided excellent opportunity to gather a lot of points during the challenge phase. In division 1, all 3 coders, who were in the top 3 after the challenge phase, have lost points on the systyem testing and have been dropped from their high positions. vividmxx, who was 3rd before the system testing, managed to enter his name into challenge success for a single match statistics of the TopCoder algorithm competition record book thank to 14 frags. Finally, tomekkulczynski won the match, ploh finished on the 2nd place and lyc1977 rounded the top 3. Division 2 was been confidently won by Alefas, who managed to show the best time for the medium, make 6 frags and successefully solve the hard problem, which was solved by nobody else in the 2nd division. Notable performance! 2nd place is occupied by WSM, Louty settled on the 3rd place. The ProblemsLuckyTicketSubstringUsed as: Division Two  Level One:
Let's just look over all substrings of even length, check for each substring if it is a lucky ticket and choose the longest one. If the length of the given string is n, then it has O(n ^ 2) substrings of even length. If a string has length m, then it can be checked for "lucky ticket" condition in O(m) complexity. So, the total complexity is O(n ^ 3), ehich is more than small enough for n <= 50. C++ code follows: struct LuckyTicketSubstring { int maxLength(string s) { int ret, n, i, j, k, x; n = s.size(); ret = 0; // i is the left end of a substring for (i = 0; i < n; i++) // j is the length of a substring (always even) for (j = 2; i + j <= n; j += 2) { for (x = k = 0; k < j; k++) // if a digit is from left half, add it to x // if it is from right half, subtract it from x if (k < j / 2) x += s[i + k]  '0'; else x = s[i + k]  '0'; // if the substring is lucky ticket, x must be zero if (x == 0) ret = max(ret, j); } return ret; } };LameKnight Used as: Division Two  Level Two: Used as: Division One  Level One:
This problem requires to determine the cases and treat all of them accurately. These cases are:
See OgieKako's solution for clear implementation. CompilingDecksWithJokersUsed as: Division Two  Level Three: Used as: Division One  Level Two:
Such low success rate surprised me. I can't realize why so many contestants submitted totally wrong solutions, obviously without whatever seriuos testing. The problem can be solved in several ways, we will discuss the binary search approach, beacuse it contains very few pitfalls in cotrast to greedy approaches. It's clear that if we can compile x decks, then y decks can also be compiled if y < x, where x and y are both nonnegative integers. So, the problem could be solved using binary search if we only could implement a boolean function f(x), which is true if x decks can be compiled and false otherwise. Well, imagine, that we are to compile x decks. Let's try to compile x decks without using any jokers. It can be done only if there are at least x cards of each type. Possibly, it will be not enough cards of some types. We need to calculate the total number of missing cards (these cards should be replaced by jokers). It is the sum of amounts of missing cards of each kind. The only conditions that must be satisfied to compile x decks are the following 2:
See Revenger's solution for clear implementation of the binary search approach.
Exercise: Used as: Division One  Level Three:
Several days after TCO06 I had an interesting dream: I was solving a geometrical problem on some TC onsite contest. I didn't manage to solve it during the dream. This problem was NestedDiamonds. I apologize for this mathoverburden problem, but its beauty did not allow me to hold it in the cage for more than 1.5 years.
Let's take a close look on the topright quarter of a diamond.
Here a is a square of the length of the diamond's side, x
and y are the squares of halfs of its corresponding diagonals.
Approach 1  Analitical solution of set of inequalities.Each diamond applies one constraint to y_{1} of the following form: l_{i} ≤ y_{1} ≤ r_{i} (for the ith diamond). l = max(l_{i}), r = min(r_{i}), for all i = 1, 2, ..., n. So, in order to compute l and r we just need to construct n inequalities of the mentoined form: one per diamond. Let's do it:
0 ≤ y_{1} ≤ a_{i}/2, for i = 1 a_{i}/2 + [sum of all a_{j} with even j < i]  [sum of all a_{j} with odd j < i] ≤ y_{1} ≤ a_{i} + [sum of all a_{j} with even j < i]  [sum of all a_{j} with odd j < i], for even i (2 ≤ i ≤ n) a_{i} + [sum of all a_{j} with even j < i]  [sum of all a_{j} with odd j < i] ≤ y_{1} ≤ a_{i}/2 + [sum of all a_{j} with even j < i]  [sum of all a_{j} with odd j < i], for odd i (3 ≤ i ≤ n) Notice, that multiplication of all x's, y's and a's by 2 enables to solve the set of inequalities in integers (using 64bit signed integer type). C++ code follows: struct NestedDiamonds { double minHeight(vector <int> sides) { vector <long long> a; long long l, r, li, ri, t; int n, i, j; // sort the diamonds in the neccessary order sort(sides.begin(), sides.end(), greater<int>()); n = sides.size(); // check for equal side lengthes for (i = 0; i < n  1; i++) if (sides[i] == sides[i + 1]) return 1; // prepare array a for (i = 0; i < n; i++) a.push_back(sides[i] * (long long)sides[i]); // initialize l and r with constraints of the outside diamond l = 0; r = a[0]; t = 0; // t is the properly signed sum of all aj, j < i for (i = 1; i < n; i++) { if (i % 2) { // tall diamond li = a[i] + t; ri = 2 * a[i] + t; t += 2 * a[i]; } else { // wide diamond li = t  2 * a[i]; ri = t  a[i]; t = 2 * a[i]; } l = max(l, li); r = min(r, ri); } // if l > r, it means that there is no allowed value of y1 if (l > r) return 1; return 2 * sqrt(0.5 * l); } };
Approach 2  Modified binary search.Constraint l ≤ y_{1} ≤ r means that all allowed values of y_{1} lie on a contiguous interval of the number axis. Let's introduce the function f(z), its possible values are:

