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?

asked May 08 '11 09:05
#### Keeto

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:

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

answered Oct 14 '22 05:10
#### Raze

### Recent Activity

- Apple Pay - authorize.net returns error 153 only when live, sandbox works
- How to continue cursor loop even error occured in the loop
- python find all neighbours of a given node in a list of lists
- Fatal error: Call to a member function setColumn() on a non-object in Magento
- Count how many of each value from a field with MySQL and PHP
- Python 32-bit development on 64-bit Windows [closed]

If you love us? You can donate to us via Paypal or buy me a coffee
so we can maintain and grow! **Thank you!**