JOIN
 Match Editorial
SRM 380
Tuesday, December 4, 2007

## 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

LuckyTicketSubstring
Used as: Division Two - Level One:
 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;
}
};
LameKnight
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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.

CompilingDecksWithJokers
Used as: Division Two - Level Three:
 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)
Used as: Division One - Level Two:
 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.

NestedDiamonds
Used as: Division One - Level Three:
 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 > a2 > ... > an. Let's make some mathematical manipulations:
xi + yi = ai; 0 ≤ xi ≤ ai, 0 ≤ yi ≤ ai;
tall diamond condition: yi ≥ xi <=> ai/2 ≤ yi ≤ ai; yi = yi-1 <=> xi = ai - yi-1;
wide diamond condition (for non-outside diamond): xi ≥ yi <=> ai/2 ≤ xi ≤ ai; xi = xi-1 <=> yi = ai - xi-1;
outside diamond condition: 0 ≤ y1 ≤ a1/2.
Notice, that diagonals of every diamond can be expressed as a function from variable y1 (a1, a2, ..., an are all constants). Each diagonal of each diamond is constrained from both sides by some constants. Thus, y1 is constrained from both sides by some constants, i.e. l ≤ y1 ≤ r. It means that we need to just find l, which is the minimal allowed value for y1 (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.

Each diamond applies one constraint to y1 of the following form: li ≤ y1 ≤ ri (for the i-th diamond). l = max(li), r = min(ri), 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 ≤ y1 ≤ a1/2 a2/2 ≤ y1 ≤ a2 a3 ≤ a2 - y1 ≤ a3 a4/2 ≤ a3 - a2 + y1 ≤ a4 a5/2 ≤ a4 - a3 + a2 - y1 ≤ a5
<=>
 0 ≤ y1 ≤ a1/2 a2/2 ≤ y1 ≤ a2 -a3 + a2 ≤ y1 ≤ -a3/2 + a2 a4/2 - a3 + a2 ≤ y1 ≤ a4 - a3 + a2 -a5 + a4 - a3 + a2 ≤ y1 ≤ -a5/2 + a4 - a3 + a2
Let's generalize these formulas:
0 ≤ y1 ≤ ai/2, for i = 1
ai/2 + [sum of all aj with even j < i] - [sum of all aj with odd j < i] ≤ y1 ≤ ai + [sum of all aj with even j < i] - [sum of all aj with odd j < i], for even i (2 ≤ i ≤ n)
-ai + [sum of all aj with even j < i] - [sum of all aj with odd j < i] ≤ y1 ≤ -ai/2 + [sum of all aj with even j < i] - [sum of all aj 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 64-bit 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 ≤ y1 ≤ r means that all allowed values of y1 lie on a contiguous interval of the number axis. Let's introduce the function f(z), its possible values are:
1. f(z) = -1, if z < l;
2. f(z) = 0, if l ≤ z ≤ r;
3. f(z) = 1, if z > r.
Minima of y1 can be found using the modified binary search over this function: if f(z) = -1, move right, otherwise move left.

By gevak
TopCoder Member