2011 Google Code Jam: Qualification Round

First, the most important detail: I Qualified!

There are 10,565 Qualifiers as of this writing, including - or should that be excluding - at least one above my rank (I started at 9912, now 9911) who has been disqualified.

I was a bit surprised when I logged in.  Google changed the format from solving one small and one large input to qualify, to needing 25 points. The first problem was worth 10 and 10, the next two were 10 and 15, and the last was 10 and 20.  This meant if I wanted to solve just one, it couldn't be the first.  It also meant if I wasn't too confident and I could only manage to solve the small version of the problem, I could pick up 2 more problems and solve their small input as well, and still advance.

I chose Problem B, as it looked fairly simple.

As a wizard, you can invoke eight elements, which are the "base" elements. Each base element is a single character from {Q, W, E, R, A, S, D, F}. When you invoke an element, it gets appended to your element list. For example: if you invoke W and then invoke A, (we'll call that "invoking WA" for short) then your element list will be [W, A]. 

We will specify pairs of base elements that combine to form non-base elements (the other 18 capital letters). For example, Q and F might combine to form T. If the two elements from a pair appear at the end of the element list, then both elements of the pair will be immediately removed, and they will be replaced by the element they form. In the example above, if the element list looks like [A, Q, F] or [A, F, Q] at any point, it will become [A, T]. 

We will specify pairs of base elements that are opposed to each other. After you invoke an element, if it isn't immediately combined to form another element, and it is opposed to something in your element list, then your whole element list will be cleared.

So basically, add a letter to a list, then see if it needs to combine with the previous letter to make a new one.  If not, loop over the whole list to see if the list needs to be cleared.  Looping over the list worried me a bit for the large input, as I would only have 8 minutes to solve it, and I've run out of time before when I wrote a quick and dirty, brute-force solution.  Luckily the Qualification Round usually isn't overly complex, so it worked out.

I also solved Problem A on paper, but I didn't have time to actually code, debug, and submit the solution.  I did go in and check my solution on Monday and found that sure enough, it worked.  I might have been pretty disappointed if the large input on problem B hadn't worked out but I had held back a problem A solution.  It runs in in O(n) time, where n is the number of button presses, so I was happy to at least have accomplished one "good" solution.

Now I get up to 3 tries to make the top 3000, next Friday, Saturday, and Sunday.  As I'm in the Central Time Zone, so I'll have to be pretty desperate to do Round 1C at 4am.