Google Code Jam Qualification Round 2012 Solutions | etc. and everything else
So yesterday I had a few hours free and decided to try the annual Google Code Jam qualification round. Typically, the questions at this stage are fairly straightforward and most people get them. We only needed 20 points (out of 100 possible points) to qualify, which equates to solving the small instances of two problems or both the small and large instance of one problem. I was able to solve three problems (small and large) for a total of 60 points. But the last one was quite challenging and I haven't been able to figure that one out yet. Anyway, here are my solutions and a bit of analysis for the first three.
Problem 1: Speaking in Tongues
This was actually a completely trivial question. I enjoyed it because they really made the question a bit out of the box. The solution was actually almost completely encoded in the problem statement and sample input! Once you made that realization, writing the actual code to solve an instance of basically any size was very easy. The main observation in this problem is that we are given the three mappings in the problem statement as well as a bunch of mappings in the sample inputs. We are told that the map is constant among all possible inputs so, I decided the easiest way to proceed was to just hard-code these mappings directly into my code. Doing a quick check revealed that we had received exactly 25 character mappings. At this point, I just looked through the list and realized that the mapping 'q' → 'z' was the only one missing. Adding that one in manually completed the cipher and you could just use that to translate everything else. The code is below.
Read full article from Google Code Jam Qualification Round 2012 Solutions | etc. and everything else
No comments:
Post a Comment