Geek Answers Handbook

Help understand the problem with Google Code Jam 2011 Candy Splitting

I am participating in Google traffic jam. First of all, I want to say that I do not want anyone to solve the problem of “winning” or something like that. I just want to help understand a problem that I could not solve in a round that was already completed.

Here is a problem link called Candy Splitting . I will not explain it here because it is nosense, I will not be able to explain it better than google does.

I would like to know some “good” solution to the problem, for example, I downloaded the first English solution and I saw that the code has only 30 lines !!! This is amazing! (Anyone can download it, so I think there is no problem with saying it: theycallhimtom solution is from here ). I can not understand the solution, even looking at the code. (My ignorance of Java does not help.)

Thanks!

+4
source share
1 answer

Google discusses problems and solutions on its own

See this link for the problem with the Candy configuration: http://code.google.com/codejam/contest/dashboard?c=975485#s=a&a=2

In principle, sweets can be divided into two equal values ​​(from Patrick's point of view), if

C[0] xor C[1] xor C[2] xor ... xor C[N] == 0.

One of these sections is the sum of all the candy values, except for one. To maximize the value of one pile, take the candy with the lowest value and place it in a pile.

Why is this so?

The way I thought about this is that, by definition, Patrick's complement is actually equal to the values ​​of hsoring. From the definition of the problem we want

 C[i] xor C[j] xor ... xor C[k] == C[x] xor C[y] xor ... xor C[z]

for some items on each side.

Adding RHS to LHS and RHS Outputs

 C[i] xor C[j] xor ... xor C[k] xor C[x] xor C[y] xor ... xor C[z] == 0

Since the xoring value with itself gives 0, and the order of xor operations is not important, RHS becomes equal to 0.

Any of the elements in the LHS can move on the right side and equality is still true. Selecting the item with the lowest value makes the best separation between piles.

+4
source

More articles:


All Articles