JOIN
 Match Editorial
SRM 284
Saturday, January 21, 2006

Match summary

In Division 1, the problems were much easier compared to SRM 283, making coders vulnerable to any fault. Five targeteers competed in the SRM, with only three of them staying in 3000+ after the event. In a tough competition, Eryx, bmerry, radeye and rem finished at places from second to fifth, and misof got home his 7th SRM win. Taking into account Petr's weak performance, this allowed misof to climb at the first position in overall TC rating. Congratulations!

In Division 2, only 3 coders were able to get the hard problem correct. veskok won the Division by more than 80 points, followed by newcomers Tigran and AlixM. royappa, Archimedean1 and ourziks took the next three places.

It is worth mentioning that radeye updated his SRM Overall Winners page after staying idle for 11 SRMs. Petr won 5 of these 11 and passed his first milestone of 10 wins.

# The Problems

Used as: Division Two - Level One:
 Value 250 Submission Rate 378 / 446 (84.75%) Success Rate 339 / 378 (89.68%) High Score gauravj116 for 249.45 points (1 mins 20 secs) Average Score 204.70 (for 339 correct submissions)

To solve this problem you need to follow the instructions in the statement and utilize some recursion. If numCrates is not greater than loadSize, we return 1. Otherwise we split the crates into 2 smaller piles and recursively call our method for these piles. If numCrates is even, each of the smaller piles will contain (numCrates / 2) crates. If numCrates is odd, smaller piles will contain (numCrates / 2) and ((numCrates + 1)/ 2) crates. Java code follows:

```int numTrucks(int numCrates, int loadSize) {
if (numCrates <= loadSize) return 1;
}
```

Measures
Used as: Division Two - Level Two:
 Value 500 Submission Rate 193 / 446 (43.27%) Success Rate 90 / 193 (46.63%) High Score Archimedean1 for 458.07 points (8 mins 45 secs) Average Score 293.10 (for 90 correct submissions)

Low constraints for this problem allow us to apply a simple brute-force solution. We iterate throw all allowed numbers of beats per measure in ascending order (from 2 to 10). For each such number K, we check each of the first K beats for being an valid first beat for a measure. Lets look closely at this check.

To check whether the starting the first full measure from the f-th beat (with bpm beats per measure) is valid, we do the following:

• Find the total number of measures. If the first beat of the first measure is f, and the total number of beats is N, the number of full measures will be (N-f)/bpm. If we don't have any full measures, our check should return false.
• Find the total number of measures with a non-stressed first beat. Our check should return true if this number is not greater than 1/5 of total measures.
• Java code follows:
```boolean check(int[] loudness, int bpm, int f) {
int total = (loudness.length - f) / bpm;
if (total <= 0) return false;
while (f + bpm <= loudness.length) {
for (int i = 0; i < bpm; i++) isbad |= (loudness[first] < loudness[f + i]);
f += bpm;
}
return (bad * 5 <= total);
}

```

SnakeCount
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 21 / 446 (4.71%) Success Rate 3 / 21 (14.29%) High Score veskok for 587.20 points (28 mins 26 secs) Average Score 504.81 (for 3 correct submissions)

First of all, imagine we have found a head of a snake and want to check whether this snake is really valid. To do this, we run a DFS starting from the head, marking all visited cells and moving only to orthogonally adjacent pixels. At each step, if current cell has more than 1 non-visited neighbour, the snake is invalid. If we don't have unvisited neighbours anymore, we count the total number of visited cells. If it is less than 3 or greater than 20 - the snake isn't valid again. The last step is to check whether the picture contains a non-visited snake-colored pixel, which is adjacent to a visited one. (this can be done by a simple brute-force check over all diagonally adjacents pairs of cells). f we can't find any such pair (and we passed all previous checks), we count the snake as "valid".

As soon as we are able to figure whether a pixel is a head of a valid snake, we can use brute force for the remaining part of the problem. We try all pixels as a possible head of a snake and count the total number of "valid" snakes using the algo we described above. Since every snake will be counted twice (once for each of its ends), return the total number of divided by 2.

TriCount
Used as: Division One - Level One:
 Value 250 Submission Rate 257 / 342 (75.15%) Success Rate 241 / 257 (93.77%) High Score antimatter for 249.01 points (1 mins 48 secs) Average Score 166.89 (for 241 correct submissions)

At the first glance, the problem can be solved by three nested loops iterating from minLength to maxLength and counting the total number of triangles:

```int ans = 0;
for (int i = minLength; i < maxLength + 1; i++)
for (int j = minLength; j < maxLength + 1; j++)
for (int k = minLength; k < maxLength + 1; k++)
if (i + j > k) ans++;
return ans;
```
This code is definitely wrong, because it will count some triangles more than once (for example, triangle (minLength, minLength, minLength + 1) will be counted thrice). To avoid this, we can represent each triangle by its side lengths sorted in ascending order. The code will change to:
```int ans = 0;
for (int i = minLength; i < maxLength + 1; i++)
for (int j = i; j < maxLength + 1; j++)
for (int k = j; k < maxLength + 1; k++)
if (i + j > k) ans++;
return ans;
```
This code will return the correct value for small inputs, so we need to make it faster for bigger ones. First of all, there is no need to continue the innermost loop as soon as k is greater or equal than (i + j). Another possible optimization is to stop as soon as we have found enough triangles:
```int ans = 0;
for (int i = minLength; i < maxLength + 1; i++)
for (int j = i; j < maxLength + 1; j++) {
for (int k = j; k < Math.min(maxLength + 1, i + j); k++)
ans++;
if (ans > 1000000000) return -1;
}
return ans;
```
The last step is to see that the innermost cycle increments ans once at each step, so the number of steps can be found as (Math.min(maxLength + 1, i + j) - j):
```
int ans = 0;
for (int i = minLength; i < maxLength + 1; i++)
for (int j = i; j < maxLength + 1; j++) {
ans += (Math.min(maxLength + 1, i + j) - j);
if (ans > 1000000000) return -1;
}
return ans;

```

Smooshing
Used as: Division One - Level Two:
 Value 500 Submission Rate 200 / 342 (58.48%) Success Rate 96 / 200 (48.00%) High Score antimatter for 454.36 points (9 mins 11 secs) Average Score 320.28 (for 96 correct submissions)

The best way to solve this problem is to strictly follow all instructions given in the statement. First of all, parse the input text and distinguish all identifiers from a "plain" text saving all idetifiers in a map structure along with their frequencies. Such parsing shouldn't be a problem for a regular TC member. The next step (assigning an abbreviation to each of identifiers) is the trickiest part of the problem. One may try to apply smooshing operation to the input, but this is a bad choice. Replacing identifiers with abbreviations, which may be equal to other identifiers, can cause a big mess. On the other hand, we don't need the smooshed text at all, we only need to know how much shorter it will be. As soon, as only smooshing identifiers may change the length of the text, knowing the abbreviation for each identifier is more than enough. Having that, for each identifier we can compute the difference between its length and the length of its abbreviation. Multiplying each difference by the frequency of the identifier and adding all these numbers, we get the total difference between the input text and its smooshed version.

Lets return now to assigning abbreviations. Instead of replacing identifiers in the text, we will keep all used abbreviations in a set. For each identifier, we build an abbreviation (as it described in the statement), calculate the difference between identifier's length and abbreviation's length, and add the abbreviation to our set. And last but not the least, calculate the total difference as described above and return the total value. See misof's solution for a clear implementation of the algorithm.

CantorSet
Used as: Division One - Level Three:
 Value 800 Submission Rate 126 / 342 (36.84%) Success Rate 82 / 126 (65.08%) High Score Eryx for 788.35 points (3 mins 27 secs) Average Score 563.26 (for 82 correct submissions)

Lets look closely at the process described in the statement. At step 1, we are to remove the open middle third of [0, 1], i.e. - all numbers from (1/3, 2/3). In other words, we are to remove all numbers which have '1' at the first place after comma in ternary notation (except 1/3, which can be written as "0.1" in ternary). Then we remove middle thirds for intervals [0, 1/3] and [2/3, 1], i.e. - remove all numbers which have '1' at the second place, and so on. Again, we don't remove numbers like 1/9, or 2/3 + 1/9 = 7/9, which have their only '1' as the last digit ("0.01" and "0.21" in ternary, respectively). In other words, to be removed from the Cantor's set before the K-th step, the number must contain a '1' among the first K digits in ternary notation and contain some non-zero digits after it.

To check whether the number has '1' as the first digit in ternary notation, we can just multiply the number by 3. After such multiplication, [0, 1] interval transforms into [0, 3] interval, and its middle third (1/3, 2/3) transforms into (1,2). So, if the result is greater than 1 and less than 2, the number has '1' as the first digit in ternary notation and will be thrown out of Cantor's set at the first iteration. To check whether the second digit is '1', we take the fractional part of the result, multiply it by 3, check whether it is between 1 and 2, and so on. The only exclusion from our rule are numbers which have exactly one '1' in their ternary notation, and don't have any non-zero digits after this '1' (like "0.1", "0.021", "0.22222221"). But neither of these numbers can be specified as a finite sequence of digits in decimal, therefore neither of them can be a valid input for our problem. This allows us to say the number is thrown out of Cantor's set at the step K as soon as we find a '1' in its ternary notation at position 'K'.

The only thing left is multiplicating a number by 3. This can be done digit-by-digit, see Eryx's solution for a clean implementation.

By Olexiy
TopCoder Member