Google Code Jam 2011... lots of fun... so little time

I participated in the Qualifying Round of Code Jam 2011.
Knowing, that on a weekend the 4 Kids wouldn't leave me alone during the day, i waited for the start at 1am and solved Problem B until ~2.30am... small dataset was correct, so i figured the large one would be ok as well... turned out i was wrong ... more later.

During the day i kept thinking about Problem C and came up with a brute force solution... fine with max. 15 candies (small dataset)... but with 1000 it would take around 10^280 times the age of the universe (says Wofram Alpha)... just a tiny little bit too long for the 8 minutes i had for the large dataset...
With time running out (15 minutes to the deadline) i realized, that the solution was quite simple...
Patricks method of adding is simply an XOR, that was obvious...
I realized, that the nature of XOR is, that when summing two equal piles... the result must be 0!
In turn this means that removing any candy from the total pile that has a XOR sum of 0, results in the rest of the pile having a sum of the value of the candy just removed...
Its that easy ;)... just remove one candy with the lowest value, and Patrick is happy... and Sean has the maximum candies ;)
Coding that was quick and i submitted my solution 5 minutes before the deadline... for a total of 35 points and the qualification to Round 1 :-) (in 9007th place...)

In the meantime i also found out, why my solution to Problem B was incorrect... i implemented the lookup of combinations not via a HashMap or similar, but doing array accesses with the char value (this way i only needed to put the combination into the array once, since QA and AQ have the same sum... problem was, that it is also possible to combine the same element, i.e. QQ, and i did not check wether both elements were "base elements"... non-base elements had a value of zero... so looking up any base element and a non-base element could find a combination if the base-elements successor had a combination with itself. This is fixed in the github code for those interested...
So the correct solution for small dataset in Problem B was... well... pure luck :-D

All code can be found here: https://github.com/phueper/CodeJam2011
Much better explanations of the Problems an Solutions can be found here: Contest Analysis

That was a lot of fun... let's see wether i have time to compete in Round 1...

Patty

P.S. it amazes me, that the winners of the qualifying solved all 4 problems in ~40 minutes... that is really impressively fast... it took me somewhere around 3-4 hours thinking about and solving 2 problems... i guess i need to practice a little bit :-)