vexorian's blog: Google Code Jam 2012: Qualification round

vexorian's blog: Google Code Jam 2012: Qualification round

What a problem D. In an attempt to honor the difficulty spike, the first qualification had very easy problems, until problem D. I spent the whole afternoon coding a solution only to find out right now it was doomed to perish anyway.

Problem A: Speaking in tongues

The algorithmic part is easy. But you have to find out the actual rules to replace the alphabet. I was feeling lucky because it was just recently I participated in codeforces April Fools contest. Because I used the very same python script to quickly translate the input/output specification into a look up table. Some letters were missing, but you could get them from the statement. One letter was still missing, but since it was only one letter, there was only one possibility for what z meant...

I guess the point of this problem was to reward general problem solving skills.

Problem B: Dancing With the Googlers

This one looks like it was meant to test your basic knowledge . It was definitely the most standard of all the problems. B-small could have been solved by mere brute force. As for B-large, I used dynamic programming.

Let us say you have a score a+b+c. Is it possible its maximum is at least X assuming the triplet (a,b,c) is not surprising? Is it possible the maximum is at least X assuming the triplet (a,b,c) is surprising?. You can actually just build a table couldBe[a+b+c][p][surp] that is true if there is a triplet (a,b,c) such that its maximum is at least p, (a+b+c) is the sum and the triplet is surprising if and only if surf=1. Since individual judge scores are at most 10, it is easy to fill this table by actually trying all the triples possible.

After you get that table. You just need to do use the following recurrence: F(n,s, P), the maximum total of googlers with a maximum sub-score that is at least P if S of them were surprising among the N first googlers. So the overall result is F( total googlers, S, P). Now, let us say we want to solve F(n, s,P). We pick googler # (n-1). We know his score, and we can decide to assume his triplet was surprising or not (Assuming the previous table says the combination of total score, maximum and surprise is possible). This will lead to two sub-problems : F(n-1, S, P) and F(n-1, S-1, P) (S could have been reduced if you picked the googler to be surprising). If you solve both smaller sub-problems then you just have to pick the best between each of the choices.

Read full article from vexorian's blog: Google Code Jam 2012: Qualification round