不同的组合算法(Candy Splitting)

Question

昨天我参加了谷歌代码果酱竞赛.有糖果分裂的问题. http://code.google.com/codejam/contest/dashboard?c=975485#s=p2

我设计了一种算法,它基本上尝试了帕特里克桩和肖恩桩的所有不同组合,检查它们是否具有相同的帕特里克值,并最终选择最大化肖恩份额的组合.该算法适用于小型输入文件.对于大的,我遇到了内存问题,输出从未出现过.我相信这个问题的另一种方法是不需要考虑所有组合.有人可以帮忙吗？

Answer 1

对于小输入,糖果的数量很少(最多15个).搜索所有可能的情况将包括2 ^ 15 =种32768可能性,可以在一毫秒左右的时间内检查.但是有多达1000个糖果(大输入),可能的组合数量达到2 ^ 1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376.现在这个数字有点太大了,即使你运行这个程序几年,你也不会得到结果.

有一些观察结果有助于为此制定有效的计划:

• 就像@Protostome指出的那样,Patrick的总和实际上是一个xor操作.
• 再次像@Protostome指出的那样,如果它是可解的,所有糖果的xor将为0.原因是:如果两个分区中可能有相同的xor总和,那么取两个分区的xor将是a xor a = 0.
• 如果可以分区,则所有糖果的xor总和为0.但是,如果我们从整个糖果组中移除一个糖果,它就变为非零.尤其,

.

   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

也就是说,我们可以通过从整个集合中取出一个糖果来将该集合划分为两个.为了最大化左半部分的算术总和,我们必须采用最低值的糖果.所以,高桩糖果的算术总和是所有糖果的总和 - 最低值!

因此,我们有:

1. 如果所有糖果的xor为零,则可以解决
2. 如果它是可解的,则sum是整个列表的总和 - 最低值.