Match Editorial

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

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;
    return (numTrucks(numCrates/2, loadSize) + numTrucks((numCrates + 1)/2, loadSize));
}

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:

boolean check(int[] loudness, int bpm, int f) {
    int total = (loudness.length - f) / bpm;
    if (total <= 0) return false;
    int bad = 0;
    while (f + bpm <= loudness.length) {
        boolean isBad = false;
        for (int i = 0; i < bpm; i++) isbad |= (loudness[first] < loudness[f + i]);
        if (isBad) bad++;
        f += bpm;
    } 
    return (bad * 5 <= total);
}

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.

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;

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;

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;

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;

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.

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.