不同組合算法（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指出，帕特里克的總和實際上是XOR運算的總和。
• 再次像@Protostome指出的那樣，如果它是可解的，則所有糖果的異或將爲0.原因是這樣的：如果在兩個分區中可能具有相同的異或值，則將兩者的異或分區將是a xor a = 0。
• 如果可以分割，那麼所有糖果的xor總和爲0.但是，如果我們從整組糖果中移除一個糖果，它將變成非零。特別是，

。

也就是說，我們可以通過從整個集合中取出一個糖果來將它們分成兩部分。爲了最大化左半部分的算術總和，我們必須取最低值的糖果。所以，高堆糖果的算術總和是所有糖果的總和 - 最低的價值！

因此，我們有：

1. 如果所有糖果的XOR是零，它是可解
2. 如果它是可解的，總和爲整個列表的總和 - 最低值。