PROBLEM LINK
Author: grebnesieh
Tester: krooonal
DIFFICULITY
Medium
PREREQUISITES
DP, Game Theory
PROBLEM
An alternate version of NIM with the restriction of number of objects removed being equivalent to a Fibonacci number, taking place simultaneously over several piles.
EXPLANATION
I love game theory, so this was one of my favorite problems in this contest. Let’s build a solution from the ground up.
First of all, since the piles only go as high as 10000 we don’t need any fibonacci numbers larger than that, so let’s pre-compute all fibonacci numbers <= 10000.
### generate fibonacci numbers ###
fib = [1, 1]
while fib[-1] <= 10000:
fib.append(fib[-1] + fib[-2])
Now that that is done. We can solve for a single pile.
By default an empty pile is a loss for alice. So we can build from 1 to 10000 iteratively as follows.
### pre-compute winning positions and moves required to reach them ###
winable = [False for i in xrange(10001)]
maxmoves = [0 for i in xrange(10001)]
for i in xrange(1, 10001):
winmoves, losemoves = 10001, 0
for x in fib:
if i - x < 0:
break
if not winable[i - x]:
winable[i] = True
winmoves = min(winmoves, maxmoves[i - x])
else:
losemoves = max(losemoves, maxmoves[i - x])
if winable[i]:
maxmoves[i] = winmoves + 1
else:
maxmoves[i] = losemoves + 1
The idea is that, for each i, if there exists a j = (i - x) (where x in a fibonacci number, j >= 0) that is a losing position, makes i itself a winning position.
Read that several times until you understand it.
As a consequence i = 1 is a winning position because you can send the other player to 0, a losing position by default. You can similarly calculate this for all the higher positions.
While you are at it, you can also store the minimum number of moves to win as shown in the code.
Now it is just a matter of iterating over all given piles and selecting the one that leads to the fastest win as follow:
for _ in xrange(input()): # loop over all test cases
n = input()
piles = map(int, raw_input().split())
fastestwin = 10001
pile = -1
for i, x in enumerate(piles): # loop over all piles and store the one with the fastest win
if maxmoves[x] < fastestwin:
fastestwin = maxmoves[x]
pile = x
if winable[pile]:
print "Alice", fastestwin
else:
print "Bob", fastestwin
Bringing us to a complete code of:
### generate fibonacci numbers ###
fib = [1, 1]
while fib[-1] <= 10000:
fib.append(fib[-1] + fib[-2])
### pre-compute winning positions and moves required to reach them ###
winable = [False for i in xrange(10001)]
maxmoves = [0 for i in xrange(10001)]
for i in xrange(1, 10001):
winmoves, losemoves = 10001, 0
for x in fib:
if i - x < 0:
break
if not winable[i - x]:
winable[i] = True
winmoves = min(winmoves, maxmoves[i - x])
else:
losemoves = max(losemoves, maxmoves[i - x])
if winable[i]:
maxmoves[i] = winmoves + 1
else:
maxmoves[i] = losemoves + 1
for _ in xrange(input()): # loop over all test cases
n = input()
piles = map(int, raw_input().split())
fastestwin = 10001
pile = -1
for i, x in enumerate(piles): # loop over all piles and store the one with the fastest win
if maxmoves[x] < fastestwin:
fastestwin = maxmoves[x]
pile = x
if winable[pile]:
print "Alice", fastestwin
else:
print "Bob", fastestwin