
Match Editorial 
SRM 167Tuesday, October 14, 2003
Match summary
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
EyeDrops
Used as: Division Two  Level One:
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.
Animation
Used as: Division Two  Level Two:
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)

Used as: Division One  Level One:
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 64bit 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.
Orchard
Used as: Division Two  Level Three:
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 breadthfirst 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.
TeamPhoto
Used as: Division One  Level Two:
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));
Now there is the question of which side of the head coach to put the team players on. As it turns out, if you sort the list of ALL the players (without the coaches), the minimum return value can be acheived if you split the players at the median. However, if there are an odd number of players, you have to experiment with putting the middle guy on either side of the head coach. All in all, you have 4 independent variables, each of which can be one of two values, which gives you 16 tests to do. The variables are:
 left side sort ascending or descending (handled by the min statement above)
 right side sorted ascending or descending (handled by the min statement above)
 middle player on left or right
 assistant coach 1 on left or right
AlphaDice
Used as: Division One  Level Three:
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 preassigned letters. The way I solved this is to establish two functions rotate() and flip(). The first rotates the cube around the topbottom axis, the second rotates the cube around the leftright 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.
By
schveiguy
TopCoder Member