`

Google Code Jam Round H

Posted: 18 November 2018

It’s the last Code Jam of the year. I wanted to take part in the previous ones but didn’t make the time to do it. At least I managed to do the last one. Performance was really bad though, only managed to finish the first 2 questions - in a bad timing too. My overall rank was 881 out of 1765 participants. Around 50 percentile. Gotta keep improving!

The first question was pretty simple. I got the idea in 10 minutes, but had trouble coding the double for loop to find matching strings and prune the remaining forbidden prefixes to prevent double counting. Ended up finishing the question in 1 hour 16 minutes. Disappointing!

The second question was real simple too. The sliding window solution immediately came to mind, but I found it hard to convince myself that every window is a valid window. I was trying to find edge cases where certain windows won’t be valid, and hence we have to prune them. In any case, I was lazy and went for the simple Python solution. Iterate through the list and compute the sum of the window at every step. This is an O(n^2) solution and I knew it, and had suspicion that I would fail the large test case because it specifically mentioned 1 case being extremely large. I submitted the small case, got it all right, and downloaded the large one. I had 8 minutes to submit the answer and my code took forever to run. At this point in time, I realized that I had to implement the sliding window solution. The race was on as I only had one chance to submit the large solution. I blitzed through the implementation, and used my previous input and output as a checker. I used diff to spot the differences. I had off by one errors and exceptions thrown because I went out of the range of the list, and had to experiment and think harder on what the right indexes are. I finally got it right, and the diff was totally blank. I submitted the solution with 30 seconds to spare. A real close shave, but a very exciting Code Jam experience. At this point in time, I had 40 minutes left to finish Question C. I saw that it was some kind of combinatorics problem, and I knew I wouldn’t be able to solve it in time. Now that Code Jam is over, it’s time to review Question C and learn from it.