Match Editorial

Match summary

SRM 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 Problems

Value	250
Submission Rate	481 / 582 (82.65%)
Success Rate	404 / 481 (83.99%)
High Score	hysramp for 249.61 points (1 mins 7 secs)
Average Score	187.15 (for 404 correct submissions)

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

Value	500
Submission Rate	257 / 582 (44.16%)
Success Rate	78 / 257 (30.35%)
High Score	Alefas for 446.25 points (10 mins 6 secs)
Average Score	293.00 (for 78 correct submissions)

Value	250
Submission Rate	438 / 465 (94.19%)
Success Rate	273 / 438 (62.33%)
High Score	Eryx for 242.40 points (5 mins 3 secs)
Average Score	184.99 (for 273 correct submissions)

This problem requires to determine the cases and treat all of them accurately. These cases are:

1. height = 1. Knight can't move, answer is 1.
2. height = 2. Only 2 moves are available: (+2, +1) and (+2, -1). Alternate these moves while possible. Thus, the answer is min(4, (width + 1) / 2), because the knight misses only even columns and, at the same time, the "4 different moves" condition can't be hold.
3. height >= 3. Actually, if height is > 3, we can treat it as = 3, because each (+2, +1) move can be compensated with (+2, -1) move and each (+1, +2) - with (+1, -2). There are 2 subcases:
   1. width >= 7. Knight makes all kind of a move once (he stays at (7, 1) after it) and then, alternates (+1, +2) ans (+1, -2) moves. Thus, the anser is width - 2, because only two columns are missed (by (+2, +1) and (+2, -1) moves).
   2. width < 7. Knight can't make moves of all kinds at least once each, so he is allowed to make at most 3 moves. He alternates (+1, +2) and (+1, -2) moves. The answer is min(4, width).

See OgieKako's solution for clear implementation.

Value	1000
Submission Rate	142 / 582 (24.40%)
Success Rate	1 / 142 (0.70%)
High Score	Alefas for 633.66 points (24 mins 51 secs)
Average Score	633.66 (for 1 correct submission)

Value	500
Submission Rate	385 / 465 (82.80%)
Success Rate	67 / 385 (17.40%)
High Score	Revenger for 479.59 points (5 mins 54 secs)
Average Score	311.68 (for 67 correct submissions)

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 non-negative 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:

1. The number of available jokers must be not less than the total number of missing cards.
2. The total number of missing cards must be not more than x, because it's allowed to replace at most 1 card by joker in each deck.

See Revenger's solution for clear implementation of the binary search approach.

Exercise:
Design and implement a solution with O(n) complexity, where n is the number of types of cards. Assume that the given array (int[] cards) is already sorted in non-decreasing order.

Value	1000
Submission Rate	99 / 465 (21.29%)
Success Rate	24 / 99 (24.24%)
High Score	Vasyl(alphacom) for 654.54 points (23 mins 25 secs)
Average Score	477.40 (for 24 correct submissions)

Several days after TCO06 I had an interesting dream: I was solving a geometrical problem on some TC on-site contest. I didn't manage to solve it during the dream. This problem was NestedDiamonds. I apologize for this math-overburden 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 top-right 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.
Notice, that this three values are enough to describe every diamond. Here x + y = a. It's obvious, that diamonds must be nested in descent order of their side lengthes and nesting is impossible if there exists at least one pair of diamonds with equal side lengthes. Thus, the order of nesting is determined: the outer diamond has index 1, most inner diamond has index n, and a1 > a₂ > ... > a_n. Let's make some mathematical manipulations:
x_i + y_i = a_i; 0 ≤ x_i ≤ a_i, 0 ≤ y_i ≤ a_i;
tall diamond condition: y_i ≥ x_i <=> a_i/2 ≤ y_i ≤ a_i; y_i = y_i-1 <=> x_i = a_i - y_i-1;
wide diamond condition (for non-outside diamond): x_i ≥ y_i <=> a_i/2 ≤ x_i ≤ a_i; x_i = x_i-1 <=> y_i = a_i - x_i-1;
outside diamond condition: 0 ≤ y₁ ≤ a₁/2.
Notice, that diagonals of every diamond can be expressed as a function from variable y₁ (a₁, a₂, ..., a_n are all constants). Each diagonal of each diamond is constrained from both sides by some constants. Thus, y₁ is constrained from both sides by some constants, i.e. l ≤ y₁ ≤ r. It means that we need to just find l, which is the minimal allowed value for y₁ (the answer for the problem is 2 * sqrt(l)). We'll discuss 2 approaches of its computation.

Approach 1 - Analitical solution of set of inequalities.

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.

1. f(z) = -1, if z < l;
2. f(z) = 0, if l ≤ z ≤ r;
3. f(z) = 1, if z > r.