
Match Editorial 
SRM 118Tuesday, October 29, 2002
The Problems
Popcorn
Used as: DivisionII, Level 1:
Value

250 points 
Submission Rate

116 / 179 (64.80%)

Success Rate

55 / 116(47.41%)

High Score

fvolny4 for 227.89 points

Average Points

155.82

This problem was pretty simple conceptually. However, getting all of the number just right and avoiding special
cases turned out to be difficult, as evidenced by the low success rate. The basic strategy was start at the
3rd pop, and then go through the array 3/4 of the way, and find the maximum gap between two adjacent pops,
and then returning that maximal interval. Probably the biggest problem people had was avoiding off by one
errors, and handling the special case when there are one three pops
public int quietTime( int[] popTimes ){
int len = popTimes.length;
int num = (3*len)/4; if(4*num != 3*len) num++;
int t = 0;
for(int i=3; it) t=popTimes[i]popTimes[i1];
}
return t;
}
Aliens
Used as: DivisionII, Level 2:
Value

250 points 
Submission Rate

115 / 179(64.25%)

Success Rate

99 / 115 (86.09%)

High Score

dre2xl for 483.35 points

Average Points

367.61

To solve this, you have to do two things given a mapping from characters to digits. First, convert a string into a number, and then convert a number into a string. Both of these can be done with a few simple string operations. To convert a string to a number, start an int at 0 which will store the result. Scan the string left to right, multiplying the result by 10 for each character, and then adding the index of the character in the mapping to your result. To convert a number to a string, start with an empty string, and then convert one digit of the number at a time to a character (you can get the digits of a number by successively taking the number modulus 10 and then dividing the number by 10). This problem turned out to be easier for most people than the first problem.
StringFold
Used as: DivisionII, Level 3:
Value

500 points 
Submission Rate

18/179 (10.05%)

Success Rate

9/18 (50.00%)

High Score

Doomhammer for 687.25 points

Average Points

596.59

Used as: DivisionI, Level 1:
Value

250 points 
Submission Rate

85/118 (72.03%)

Success Rate

79/85 (92.94%)

High Score

John Dethridge for 234.65 points

Average Points

173.91

The simplest way to do this is to initialize a big character array (at least twice the length of the input string), and start by adding characters in the middle of the array in the forward (left to right) direction. Then, scan the input string one character at a time. If the character in the input matches the previous character in the input, then reverse direction, and overwrite the last character with its case switched. So, as you scan the input string, you set characters in your array in one direction or the other, and swap the case whenever you are going backwards. For a very clean implementation of this, see John Dethridge's solution.
SpaceDrone
Used as: DivisionI, Level 2:
Value

250 points 
Submission Rate

74/118 (62.71%)

Success Rate

56 / 74 (75.68%)

High Score

John Dethridge for 472.01 points

Average Points

341.34

One way to do this was to keep track of which direction the space ship was facing, and which direction was up, and then hard code all cases, and where a Y or an R will lead to next. However, this is a lot of work, and very error prone. A better way to do it is to note that when you turn, the direction that you are facing, is the opposite of the direction that you were previously facing, and the direction that is to your right is the direction that you were previously facing. Similarly, a Y command causes the direction that you are facing to become the opposite of the direction that was previously up for your space ship, while up become the direction that you were facing. This suggests that we should keep track of the direction up, forward, and to our right. Then a R command is just:
newRight = oldForward
newForward = oldRight
newUp = oldUp
A Y command can be implemented similarily, and a F command is just a matter of looking at which direction is currectly being faced. Again, John Dethridge had the high score, and used the method above.
MineMapper
Used as: DivisionI, Level 3:
Value

1000 points 
Submission Rate

35/118 (29.66%)

Success Rate

19 / 35 (54.29%)

High Score

Yarin for 767.99 points

Average Points

574.84

There wasn't really anything too tricky about this problem. You basically just have to follow the directions. A simple way to do this is to just start walking from every previously visited point, over and over again, until you learn nothing new. So, you just have to figure out, if you are currently at some point, what can you mark as a positively a mine or positively not a mine. If you count the number of adjacent squares that are mines, but not known, and the number of squares that are free, but not known, you can figure it out. Basically, if either of these numbers is 0, then you know that all the other unknown squares must be either mines or free (the detector will tell us which), and you can mark them as such.
See Yarin's code for an impressively short solution
By
lbackstrom
TopCoder Member