Nick Moline's Blog

This morning Google opened up a programming competition using the same system as Google Code Jam (they called it the Google Code Jam Sprint to I/O) to win the right to buy 1 of 100 tickets to Google I/O.  Normal Registration for the conference closed 20 minutes after it opened back on March 27th due to the incredible demand, so naturally those developers who couldn’t get in before were excited and ready to battle for the chance to buy a ticket.

The competition consisted of 2 problems, programmers could write their code in any language (as long as the compiler is free to use).  It would work like this, you would write a program according to their specifications of the problem, and then you would submit it.  When you submit it, google would provide you with a file of sample input data and then give you 1 minute to run your code against that sample data and then submit the output to them.  They would then run a validator across the output and tell you if you were correct or not.  If you were correct, it would accept your answer, if not, it would reject it.

The first question went like this (paraphrasing)

The Google Store has M new designs of android mini-statues available, and they have L of each design in stock.  You, an avid collector and generous gifter, want to buy a certain number of each of these new designs (K1, K2… KM). The problem is… the packages for these statues are all exactly the same, and don’t indicate what is inside, and you cannot open the package before purchasing.  What is the minimum number of packages you need to purchase to guarantee you have all of the statues you want in a worst-case scenario

The sample data was a list of lines in the following format for different test cases:
L M K1 K2 ... KM

For example:

5 3 4 2 1
5 3 5 5 5
5 2 1 5
6 4 0 0 0 0
2 4 5 1 2 3
0 3 4 1 2
9 5 1 1 1 1 1

Taking the first one (They have 5 each of 3 different designs, and you want 4 of the first, 2 of the second, and 1 of the third), the correct answer would be 14 (in order to guarantee you have at least 4 of the first, at least 2 of the second, and at least 1 of the third, you would have to buy enough that you would have ALL of all but 1 of them, and then the highest K for the remainder)
Answer = (L * (M-1)) + max(K)
The question also said that if it was impossible to get what you want, you should return -1 (like the 5th and 6th examples, you can’t buy more statues than they had available in the first place)

Now most programmers seeing something like the 4th test case there (6 4 0 0 0 0) would realize that if you don’t want to buy any of them, than the answer is 0 (minimum number to buy in order to get 0 statues is 0), so the basic pseudo code to solve this problem is:

function process_test_case(L = 0, M = 0, K = array()) {
     if (max(K) == 0) return 0
     elseif (max(K) > L) return -1
     else return (L * (M - 1)) + max(K)
}

There is just one problem… Google’s developers that came up with this test, didn’t think about the possibility where you don’t want any statues (max(K) == 0), so if you ran the above code and returned 0 on the sample 4, google’s validator would come across with “Incorrect”, on the other hand if you left that line out and only did the other 2 possibilities, it would say you were “correct”

Naturally a lot of the programmers who entered the competition were quite upset about this, and complained to Google via comments on the Google+ post that announced the competition.  Eventually google put up the following message saying that they realize they made a mistake:

We’ve made a mistake in problem A. The correct output is 0, but it is being judged as wrong because 4 of our problem writers have independently made the same bug in their solutions. We would like to apologize for the confusion this has caused. We will send an email to all participants shortly, announcing our plan to resolve this issue in the least unfair manner possible. We take a lot of precautions to prevent mistakes like this, but we have messed up this time

Now I did not enter this competition (I did the coding example just for the brain exercise, but I did not submit it) because I am already registered for Google I/O and didn’t need the additional ticket for myself, but some of my coworkers did enter the competition, and they received an email a little while ago which included the following:

As you know, we intended to provide an opportunity to buy Google I/O tickets to the top 100 scorers. In light of our mistake, we’ve decided instead to offer this opportunity to all participants who have submitted any solution to either of the two problems. Please watch your inbox for a registration code coming shortly.

That does indeed seem “least unfair,” everyone who tried the contest, gets to go to Google I/O.  If you are among those, (like my fellow coworkers), I look forward to seeing you in San Francisco on June 27th.