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

Google Code Jam Latin America 2007
Google Code Jam Latin America 2007

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…)

One thought on “Google Code Jam LatinAmerica

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s