Google Code Jam

Last Thursday, I saw a blogpost on a Python related RSS, mentioning about the Google Code Jam. I saw that it was a programming contest and took a look at it. Reading the rules, I saw that there was a 4 - 8 minute limit. At first I thought that it was the time to solve a problem that is given to you. I thought it was a crazy idea to solve a problem in 4 minutes and code it. As I was at the company, I put it off to the evening for details. When I came home, I did some stuff I needed to do and when I realized that the limit is not for solving but submitting the output after downloading the input, I was angry with myself. Why didn't you read it! There had been 4 hours left. It was 10 pm and the contest was going to end by 2 am. So I started to look at the questions. There were 3 questions of which I had to solve 1 of them correctly to qualificate to the first round. I needed to code to solve the problem and then download two (small and big) inputs and submit them.

I started with the first question, here you are a summary: "In a planet, there are some search engines. When you search the name of a search engine on itself, the planet explodes. So you shouldn't search for Gogool on the Gogool engine. Scientists developed a central system to prevent this. This system forwards the search requests to the engines other than the engine with the name in the request. The question is that with the least switch between the engines, how many switches are required to serve all the search requests."

I developed a greedy algorithm. First, I was going to determine the indexes of the engines where they were first seen. Then I was going to find the furthest one and serve the request before that with this engine. For example below, the furthest first seen engine is NSM. So I should handle the first 4 requests with NSM:

Yehhaw
Yehhaw
Gogool
Dont Ask
NSM
Gogool
DontAsk
DontAsk
Gogool
Yehhaw

Then I had to remove the indices below 5 which belongs to NSM. Then I looked ahead like having a new beginning from NSM:
Gogool
DontAsk
DontAsk
Gogool
Yehhaw

So, it is now obvious that the index 11, (i.e. Yehhaw) is the engine to be used for serving 5-10 (NSM-Gogool). And then the previous indices would be removed after that and so on. The input files were large with the 20 different cases in the number of various engines and the number of searches.

I coded this algorithm on Python and when I ran the sample input, it was successful. Then I downloaded the input file but it told me that my output was incorrect. After the contest, I learned that there were only 3 digits wrong, possibly caused by boundary checking or exceptional conditions.

After the wrong answers, I decided to look for the other questions and started the second question, the train question. There were two towns, A and B between which there were train routes. Input file consisted of the turnaround time for the trains, the timetable from A and timetable from B. The question is that with how many trains at minimum you can handle these timetables such a way that a train coming from A, after completing the turnaround can handle the closest train route on the timetable B to go back to A.

A: 9.00 - 12.30
Turns around in 5 minutes
B: 13.00 - 15.00
The turned around train undertakes the 13.00 route and goes to A. So there's no need to have an additional train to go from B to A at that time.

At first I did not have a clear algorithm but I thought it would be great if I could match the trains as complement and show the complement pairs on the screen so that I could draw inferences on it. Maybe I could develop a matching algorithm after marking them as complements. But the things were not the same as they seemed to be. When marking as complement, I fell into a infinite loop, the train from A matched B and the train from B matched A and A did the same, etc ... They matched each other again and again. Then I realized the time was nearly up. I could not do anything but to post my code and the small output. They were incorrect, of course. But at least a hope that they would look at the codes.

So, I could not qualificate to the first round. I wish I could know it before. For months, they had been practicing for the contest and I hadn't ever heard about it. It was the contest day (last day) when I saw it. So all I can do is this in four hours. Maybe I can do better next year, using all the 24 hours. :)