Two people take coins, hacker solution
Puzzle:
There are n coins in the line, the coins have different meanings. Two players take turns taking a coin from one end of the line until there are more coins left. The player with the most money wins. If n is even, is there some hacking algorithm that can decide if the first player wins or loses in O (1) memory and O (n) time?
I solved the problem with dynamic programming, but I don't know what a hacky algorithm is. After searching, I found a solution 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
So far I can figure out if odd_s != even_s
, the first person will always win, but I just couldn't figure out the situtation odd_s == even_s
. How to prove the absence of a winning strategy if odd_s == even_s
?
source to share
It turns out I misunderstood the solution. Here's the complete solution:
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)
If odd_s != even_s
, then the first person will win for sure. if odd_s == even_s
, we don't know who will win, so go back to firstWillWinNormalCase
.
source to share