Match Editorial

The competition before the first online TCO round had some surprising results. Aside from a devious 750 point problem in division 1, division 2 had a seemingly difficult level 1. In fact, some people in division 2 ended up gaining rating points with a final score of 0.

snewman continued his advance towards the top ten, with the most significant jump in rating for division 1. So far, he has submitted and passed everything that has been thrown his way. In addition, this is his first official division 1 competition, his first division 1 win, and I believe he is the first C# coder to do so. Division 2 saw an amazing 50 new coders, with one of them (Andrew_Lazarev) claiming 1st. Also of note is scn who got 250 points on 5 successful challenges.

The Problems

Value	300
Submission Rate	184 / 278 (66.19%)
Success Rate	93 / 184 (50.54%)
High Score	splurk for 284.75 points (6 mins 38 secs)
Average Score	216.87 (for 93 correct submissions)

Usually, the div 2 easy is a gimme. Not so this time. Only about half of the coders who submitted got points for it. At first glance, it seems like there is more than meets the eye. However, upon further examination, we happliy latch onto a correct greedy algorithm. There are two cases, one is if we can take pills on an optimal schedule. The second is if the sleep time is too long to fit within an optimal time period. In the first case, the answer is just (24 * 60) / k. In the second, we position times for taking the pills just before and after bedtime. Then, counting the gaps besides the sleeping gap, there are k - 1 gaps. So the answer in this case is (24 - sleepTime) * 60 / (k - 1).

One of the most common errors in this problem was to not cast the values to doubles before doing the division.

Value	500
Submission Rate	158 / 278 (56.83%)
Success Rate	115 / 158 (72.78%)
High Score	ggrot for 421.26 points (12 mins 47 secs)
Average Score	304.80 (for 115 correct submissions)

Value	250
Submission Rate	226 / 233 (97.00%)
Success Rate	205 / 226 (90.71%)
High Score	ZorbaTHut for 244.20 points (4 mins 23 secs)
Average Score	202.73 (for 205 correct submissions)

This was a simple simulation. The only tough part was to keep track of particles when they overlapped eachother. The two general methods used were to use a different character for when a L and R particle are overlapping, or keep track of each particle in a separate array. As an extension to the separate array method, you could use two 64-bit bitmasks to represent the left and right particles. This has the nice feature that the movement step is one line (just a bit shift), and worrying about overflow isn't necessary. The simulation is over when all the particles leave the string.

Value	900
Submission Rate	44 / 278 (15.83%)
Success Rate	16 / 44 (36.36%)
High Score	Andrew_Lazarev for 676.46 points (17 mins 35 secs)
Average Score	547.53 (for 16 correct submissions)

This problem was a search for the best breadth-first search return value. The straightforward solution is to run a bfs from each location and find the first point at which we reach another tree or a wall. If we iterate over the rows in the outer loop, and the columns in the inner loop, we can avoid having to break ties. Simply return the coordinates of the best bfs starting location.

Value	750
Submission Rate	110 / 233 (47.21%)
Success Rate	31 / 110 (28.18%)
High Score	snewman for 611.29 points (14 mins 13 secs)
Average Score	457.06 (for 31 correct submissions)

In my entire topcoder career, this is the first time I've seen a 750. Surprisingly, 31 people got it right (not including myself), and there were many scores over 500. As it turns out, this problem is one of those "oh, darn, if only I'd thought of that" problems. That's right, a simple property of the problem makes it very easy to comprehend a solution. The property is, given a list of numbers that starts at one value, and ends at another, the minimum sum of all the adjacent differences is acheived by sorting the points that are not on the end in either increasing or decreasing order. After they are sorted, the only two values which are important in the sorted list are the minimum and maximum. So, the minimum answer for a range of numbers with end values of A and B, minimum value L, and maximum value H is (in java):

H - L + Math.min(Math.abs(A - L) + Math.abs(B - H), Math.abs(B - L) + Math.abs(A - H));

1. left side sort ascending or descending (handled by the min statement above)
2. right side sorted ascending or descending (handled by the min statement above)
3. middle player on left or right
4. assistant coach 1 on left or right

Value	900
Submission Rate	80 / 233 (34.33%)
Success Rate	34 / 80 (42.50%)
High Score	Xu Chuan for 685.11 points (17 mins 4 secs)
Average Score	474.43 (for 34 correct submissions)

Don't you just hate problems where you have to rotate 3d objects in your mind? I know I do. I made the very big mistake in this problem of believing that multiple sides could have the same letter, even though an example showed otherwise. In any case, this problem consisted of two parts. One was determining if a roll given could match a cube with pre-assigned letters. The way I solved this is to establish two functions rotate() and flip(). The first rotates the cube around the top-bottom axis, the second rotates the cube around the left-right axis. With these two rotations, I can systematically place the cube in all 24 orientations that are possible, and see if the appropriate three letters match the roll.

The second part of the problem is to determine which letters should be on the other side of the first roll. We could just blindly assign all letters to the hidden sides, but why do that when we know which letters are required from the letters in the rolls. Alas, with 50 rolls, all the letters in the alphabet could be used, which brings us back to brute force. However, we can use a simple deduction to reduce our search space significantly. If any sequence of rolls has more than 6 distinct letters, then we know for sure that sequence is invalid. Therefore, there is no reason to try any more than 3 letters for the hidden sides. We simply use the letters from the largest sequence of rolls which does not exceed 6 letters. With only 3 letters to try, there are only 6 possible cubes that can be made. With our algorithm above, we can compare each of the 6 cubes with the given rolls, stopping if one doesn't match. We then return the maximum roll attained, or -1 if all rolls matched for one of the 6 cubes. In the case where less than 6 letters are specified in all the rolls, we simply assign invalid characters to the leftover sides. In my practice room solution I used lowercase 'x', 'y' and 'z' for any leftover spaces.