Different Combinations algorithm (Candy Splitting)

Question

Yesterday I paticipated in the Google code jam contest. There were that candy splitting problem. http://code.google.com/codejam/contest/dashboard?c=975485#s=p2

I designed an algorithm that basically tries all different combinations for Patrick's pile and Sean's pile, checks if they have the same Patrick value, and finally choose the combinations that would maximize Sean's share. The algorithm worked well for the small imput file. For the large one, I got memory problems and the output never showed up. I believe there muct be another approach to this problem that wouldnt require considering all combinations. Can anyone help?

Answer 1

For the small input, the number of candies are small (upto 15). A search of all possible cases will consist of 2^15 = 32768 possibilities, which can be checked within a millisecond or so. But with upto 1000 candies (large input), the number of possible combinations go upto 2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376. Now this number is a little too big, and even if your run the program for a few years, you are not going to get the result.

There are some observations which help in making an efficient program for this:

• Like @Protostome pointed out, the sum that Patrick's sum is actually an xor operation.
• Again like @Protostome pointed out, if it is solvable, the xor of all the candies will be 0. Reason is this: if it is possible to have the same xor sum in the two partitions, then taking the xor of both the partitions will be a xor a = 0.
• If it is possible to partition, then the xor sum of all candies is 0. But, if we remove a single candy from the set of entire candies, it becomes non-zero. Particularly,

.

   c1 xor c2 xor ... xor ci-1 xor ci xor ci+1 xor ... xor cn = 0
=> c1 xor c2 xor ... xor ci-1     xor    ci+1 xor ... xor cn = ci

That is, we can partition the set into two, by taking out a single candy from the entire set. To maximize the arithmatic sum of the left half, we have to take the candy with the lowest value. So, arithmatic sum of candies in the higher pile is sum of all candies - value of lowest!

Therefore, we have:

1. If the xor of all candies is zero, it is solvable
2. If it is solvable, sum is sum of entire list - lowest value.