Get Time
statistics_w  Match Editorial
SRM 118
Tuesday, October 29, 2002

The Problems

Popcorn  discuss it
Used as: Division-II, 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[i-1];
        return t;

Aliens  discuss it
Used as: Division-II, 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  discuss it
Used as: Division-II, 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: Division-I, 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  discuss it
Used as: Division-I, 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  discuss it
Used as: Division-I, 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