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 ProblemsTruckloadsUsed as: Division Two  Level One:
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)); }Measures Used as: Division Two  Level Two:
Low constraints for this problem allow us to apply a simple bruteforce 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 fth 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); }SnakeCount Used as: Division Two  Level Three:
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 nonvisited 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 nonvisited snakecolored pixel, which is adjacent to a visited one. (this can be done by a simple bruteforce 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. TriCountUsed as: Division One  Level One:
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:
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. CantorSetUsed as: Division One  Level Three:
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 Kth step, the number must contain a '1' among the first K digits in ternary notation and contain some nonzero 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 nonzero 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 digitbydigit, see Eryx's solution for a clean implementation. 
