两个人拿硬币，hacky 解决方案

Question

谜题是：

There are n coins in a line, coins have different values. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. If n is even, is there any hacky algorithm that can decide whether first player will win or lose in O(1) memory and O(n) time?

我已经用动态规划解决了这个问题，但我不知道 hacky algorithm 是什么。经过搜索，我找到了here的解决方案：

def firstWillWinEven(self, values):
    """
    odd_s: sum of values at odd position
    even_s: sum of values at even position
    if odd_s == even_s, the first mover cannot win if the other player mimics the first player
    if odd_s > even_s, the first mover chooses the odd position values, and FORCE the other player choose the even
    position values. The strategy and outcome are similar when even_s > odd_s.
    """
    odd_s = 0
    even_s = 0
    for i in xrange(len(values)):
        if i%2 == 0:
            even_s += values[i]
        else:
            odd_s += values[i]

    return odd_s != even_s

虽然我能理解如果odd_s != even_s，先手总会赢，但我就是无法理解odd_s == even_s的情况。 如果odd_s == even_s如何证明没有必胜策略？

Answer 1

原来我误解了解决方案。这是完整的解决方案：

def firstWillWin(self, values):
    """
    :param values: a list of integers
    :return: a boolean which equals to True if the first player will win
    """
    n = len(values)
    if n%2 == 0 and self.firstWillWinEven(values):
        return True

    return self.firstWillWinNormalCase(values)

如果odd_s != even_s那么第一人必胜。如果 odd_s == even_s，我们不知道谁会赢，所以退回到 firstWillWinNormalCase。

两个人拿硬币，hacky 解决方案

Two people take coins, the hacky solution

puzzle

algorithm

game-theory