Match Editorial

The Problems

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;
    }

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.

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

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.

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.

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