QUCOATO - Editorial

PROBLEM LINK

Contest

Practice

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
2 Likes

@grebnesieh if u have added it to practice just add the link on contest page