Google Code Jam LatinAmerica

So, about a week ago a friend told me about this event google was arranging, a programming contest, so I got into it.

I signed up and then went into the practice rooms, wow! it was not easy, problems were complex and time was short; I practiced for a bit and then left.

Well, finally, the time for the elimination round came; only 500 persons would pass to the first round. There were like 1600 people, if I remember correctly. So I went in to take part into the contest.

The google code jam event, powered by TopCoder, puts the codemonkeys into a specially crafted arena (made in Java by the way), where they can chat, access their problems and generally get stressed because of the results.

First comes a coding phase, where you have 1 hour to solve two programming/algorithm problems, one worth 250 points, the other 750. There’s an in-arena code editor where you can read the problem, compile and test, in different languages such as Java, C#, C++, Python..

The points are assigned depending on how much did it take for you to submit the problem.

The 250pt problem was kinda simple, which was good news to me as I didn’t want to leave the competition scoreless, so I went on and made it. It required to sort an array of int’s so I tried using Arrays.sort; “Couldn’t resolve name Arrays” he said, so I guessed it wouldn’t allow me to use such libraries, but I thought… “No problem! I will hack together a simple bubblesort, that will do!” and so did I.

I got 203 points, which was good enough for me, so I went on with the 750 pointer.

Well, it was a very “geometrical” problem, about finding how many integer coordinate pairs are inside a triangle given its three vertices. It was not very simple, and you had to know some geometrical formulas beforehand, so I went on to search the web for a clue, and slowly started to put together a working algo. Well, in the end it didn’t work for a reason I couldn’t discern.

I submitted it for about 250 points, knowing it would be trashed in…

…the System Test Phase, where all the submitted problems are compared against a set of test cases, and if they fail their score drops to 0.

I hoped I would remain inside the first 100 of my set, so I could advance to the next round and perhaps perform better.

Things were going well, by the 8 AM of the next day, 1 hour before closing the contest, I was standing on about place 90th with my 203pts.

Then came the system test, and then this happened

So, that was a quick farewell to this year code jam, all caused by a naive mistake on the sort method. The examples were tricky, or I was unlucky, as I got the correct answers because of the actual data on the prices array.

For those that dont understand the error, or are in a hurry and cannot see it:

in the sort method, in the inner loop, I had

if (x[i] > x[j]){

int temp = x[i];

x[i] = x[j];

x[j] = x[i];

}

Which incorrectly doubles the value of x[j], as the third assignment does nothing. I had to use the temp variable.

Lessons:

* For the elimination round, concentrate on the 250 pointer

* Make your own tests to your code, don’t rely on the provided examples

* Use utility libraries (if I had known this…)