2012 Google Code Jam, Qualification Round

TL;DR version: Once again, I've qualified this year!

Here's last year's Qualification Round post for details on how the Google Code Jam works.

I was incredibly busy during the 25 hours Qualifcation round, and in fact for the third consecutive year I was out of town during the round. The cutoff was 20 points, achievable by solving the small and large inputs for one of the problems. My strategy was thus to log in shortly after the start, about 7pm Friday, and let the ideas roll around in my head all day Saturday so that I could spend a very short time coding during a brief break Saturday afternoon. Since the feedback from the codejam website doesn't reveal success or failure on the large input version until the contest is over, too late to try for more points. Even so, I was in a time crunch and so decided to trust I could get it right. Since I waited until near the end and solved the minimum, my rank was 15,158 out of the 15,193 that qualified. That's way more than the 9000+ that qualified last year. It feels like I just made it, but anyone who could earn enough points could make it. 17,803 earned at least some points, but 2,610 didn't get the 20 required.

I chose Problem B, Dancing With the Googlers, worth a total of 20 points, figuring it's the easiest one that had enough points to allow me to advance.

You're watching a show where Googlers (employees of Google) dance, and then each dancer is given a triplet of scores by three judges. Each triplet of scores consists of three integer scores from 0 to 10 inclusive. The judges have very similar standards, so it's surprising if a triplet of scores contains two scores that are 2 apart. No triplet of scores contains scores that are more than 2 apart. 

For example: (8, 8, 8) and (7, 8, 7) are not surprising. (6, 7, 8) and (6, 8, 8) are surprising. (7, 6, 9) will never happen. 

The total points for a Googler is the sum of the three scores in that Googler's triplet of scores. The best result for a Googler is the maximum of the three scores in that Googler's triplet of scores. Given the total points for each Googler, as well as the number of surprising triplets of scores, what is the maximum number of Googlers that could have had a best result of at least p? 

For example, suppose there were 6 Googlers, and they had the following total points: 29, 20, 8, 18, 18, 21. You remember that there were 2 surprising triplets of scores, and you want to know how many Googlers could have gotten a best result of 8 or better. 

With those total points, and knowing that two of the triplets were surprising, the triplets of scores could have been: 

10 9 10
6 6 8 (*)
2 3 3
6 6 6
6 6 6
6 7 8 (*) 

The cases marked with a (*) are the surprising cases. This gives us 3 Googlers who got at least one score of 8 or better. There's no series of triplets of scores that would give us a higher number than 3, so the answer is 3. 

Input 

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing integers separated by single spaces. The first integer will be N, the number of Googlers, and the second integer will be S, the number of surprising triplets of scores. The third integer will be p, as described above. Next will be Nintegers t_i: the total points of the Googlers.

I found this one rather easy, as it was just a quick math problem once I thought about it. In the regular case, seeking a best score of p would mean that the worst possible set of scores is p, p-1, p-1, and in the surprising case, p, p-2, p-2. Since scores couldn't be negative, I had to account for p being 0 or 1 as a special case. So the total for the regular case had to be at least 3p-2, and at least 0. In the surprising case, the total had to be at least 3p-4, and again, at least 0 (realistically, at least 2, with scores 2, 0, 0, or else it wouldn't be surprising).

I simply looped over the listed values, and if one was at least the regular total, it counted. If it wasn't, and S was still at least 1, and it was at least the surprising case total, it counted, and I subtracted 1 from S.

So, for the case of:
3 1 5 15 13 11
N S p t0 t1 t2

There were 3 Dancers to score. 1 had surprising scores (a spread of 2). I was to find how many could have a best score of at least 5. The regular target was 13 (5+4+4), and the surprising target was 11 (5+3+3). So, t0 and t1 qualified as regular, and t2 was the surprising case, and the answer was 4.

Rinse and Repeat for 100 cases and 1 to 100 competitors per case, and I solved the easy and hard versions rather quickly.

I'll post about Round 1A and if necessary, 1B and 1C later.