Introduction

This is the story of how I failed to qualify for round 2 to in the 2018 Google Codejam. Hopefully you find it interesting and learn some things you shouldn't do in Codejam.

Qualification Round

Qualification was fairly easy due to the ample time of 24 hours. I managed to solve everything correctly apart from the large dataset for the last question. I tried to see if anyone had done mathematical analysis of Madison Cube garden from Futuruma since that seemed closely related to the last question but to no avail.

Round 1A

The ideas to solve questions just did not come to me during this round. I only managed to solve the small set for question A.

What I learnt:

Eat a good breakfast before doing a competition in the morning.

Round 1B

I looked at question A and could not think of a correct approach. Then I looked at B and decided to work on it since it seemed simpler. I saw a the equations and coded a solution. The solution failed the sample test cases. Then I realised I had misunderstood what the question was asking. So I modified my code and it also failed the sample test cases. Turns out I still misunderstood the question. After I finally understood what the question wanted I was running low on time so decided to code a O(n²) solution to pass the small. This worked.

After looking at the other questions I decided it was best to spend the remaining time modifying the solution so it would not TLE on the large. I did some simple micro-optimisations then a beautiful two pointer style approach that would take my solution to O(n) came to me with roughly five minutes to go. I coded quickly and the solution passed the sample cases. I submitted it with less than a minute to go, however it failed the small test set. After the contest I managed to get my O(n) solution to work. Turns out the code I submitted was correct apart from two lines where I wrote i when I should have written i - 1. Also if I had got that solution to work I would have qualified for round 2.

What I learnt:

1. Read the question carefully before coding.

2. Be thankful for sites like csacademy that give you problems without stupid stories about jackasses looking at road signs.

Round 1C

Question A seemed fairly straightforward after a bit of thought. I considered using a prefix tree to be fancy and ensure a sufficiently low time complexity but my previously written prefix tree implementation was not well suited to the task. Looking at the limits I decided a binary search should be fast enough. I also suspected a two pointer style approach might exist but decided to stick with the binary search rather than look for it. Question A passed after I fixed how I handled an edge case in my implementation.

After a brief look at B and C I decided to attack the small C since it looked like a knapsack style dp approach should work. I was able to get C to work without too much trouble but knew there was no way my code would pass the large.

I had a look at the B and came up with a greedy approach. First I got an idleness limit exceeded. I realised I had to change the template I used for codejam problems since interactive problems have a different format for the expected output. Doing this allowed me to convert my idleness limit exceeded into a WA. Yay progress! Then I spent the rest of the contest fiddling with my greedy approach to no avail. After the contest I read the editorial and learnt my initial greedy approach was correct. I looked at my code found out when I altered my template I did not allow for multiple test cases. One simple for loop and I would have got AC. Like round 1B if I had this loop I would have qualified for round 2.

What I learnt:

Pay special attention to how you code interactive problems.

Conclusion

I didn't make it to round 2 of gcj this year. There were some interesting problems and I looking forward to seeing and upsolving the problems from future rounds. Best of luck to everyone who made it round 2.