math - 帮助理解 Google Code Jam 2011 Candy Splitting 问题

Question

我正在参加 google code jam。在此之前，我想说的是，我不希望任何人解决我“赢”的问题，或者类似的问题。我只是想要一些帮助来理解我在已经结束的回合中无法解决的问题。

这是问题的链接，名为Candy Splitting .我不会在这里解释它，因为它是胡说八道，我无法比谷歌更好地解释它。

我想知道这个问题的一些“好”解决方案，例如我下载了第一个英文解决方案，我看到代码只有30行!!!太棒了! (任何人都可以下载它，所以我认为说出来没有问题:来自here 的theycallhimtom 的解决方案)。即使看代码我也无法理解解决方案。 (我对 Java 的无知无济于事。)

谢谢!

Answer 1

谷歌自己提供有关问题和解决方案的讨论

有关糖果 split 问题，请参阅此链接:http://code.google.com/codejam/contest/dashboard?c=975485#s=a&a=2

基本上，糖果可以分成两个等值的堆(从帕特里克的角度来看)，如果

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

一种这样的拆分是除一个之外的所有糖果值的总和。为了最大化一堆的值(value)，把值(value)最低的糖果放在自己的一堆。

为什么会这样？

我的想法是，根据定义，帕特里克的加法实际上等于异或值。从问题的定义来看，我们想要

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

对于每一边的一些元素。

将 RHS 添加到 LHS 和 RHS yield

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

由于将一个值与自身异或得到 0，并且异或运算的顺序并不重要，因此 RHS 变为 0。

LHS 中的任何元素都可以移动到右侧，并且等式仍然成立。选择最低值的元素可以在堆之间进行最佳分割。