PUPPYGM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Vlad Mosko
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY

PREREQUISITES:

Game theory, Induction

PROBLEM:


There is a two player game which is played on two stacks of nuts. Players take moves alternately. The first player makes the first move. A valid move consists of two consecutive actions:
  1. Choose one stack and remove all nuts from it. It results in removing this stack from the game
  2. Split the remaining stack into two non-empty new stacks in any possible way

A player loses the game when he is not able to make any valid move.

Your task is to decide which player has a winning strategy if both of them play optimally.

QUICK EXPLANATION:


Consider all possible configurations of parity of the number of nuts in each stack. Based on that, figure it out which positions are winning and which are not. First player has a winning strategy if and only if the initial configuration of stacks is a winning position.

EXPLANATION:

Let’s call a configuration of stacks a position in the game. Notice that a configuration can be presented as an unordered pair of integers \{A, B\}, where A and B denote the number of nuts on stacks.

We will call a position a losing one if and only if there is no valid move which leads to victory from this position. Respectively, we call a position a winning one, if and only if there exists a move which leads to a losing configuration for the opponent. It is called a winning position, because the current player has an ability to make a move which force his opponent to lose the game no matter what the opponent does.

Let’s take a closer look to the problem by considering some small positions.

The smallest achievable position is \{1, 1\}, because you can never produce an empty stack in a valid move. A player cannot make any move from position \{1, 1\}, because there is no way to split a stack which contains only one nut (you have to remove the other one first).

Let’s consider another position, \{1, 2\}. The only valid move which a player can make is to remove the stack with one nut and split the other stack in half, which results in the configuration \{1, 1\}. We know that \{1, 1\} is a losing position, so \{1, 2\} is a winning one.

Similarly, \{2, 2\} is a winning position, because a player can remove any stack and split the other in half, which leads to \{1, 1\} - a losing position for the opponent.

What about \{2, 3\}? It is a winning one also. You can make a move similar to the previous two situations, i.e. remove the stack with 3 nuts and split the other in half, which leads to \{1, 1\} position.

But not every position other that \{1, 1\} is a winning one. Consider the position \{1, 3\}. If you decide to remove the stack with 3 nuts, you cannot split the other one, so this move is not valid. It follows that every valid move has to remove the stack with one nut first and split the other in some way. Unfortunately, there is only one way to split a stack of 3 nuts, and it results with \{1, 2\} which is a winning position for the opponent. We showed that \{1, 3\} is a losing position. From the same argument, it follows that \{3, 3\} is a losing position also.

What do the above losing position have in common? Well, in each of them both stacks have odd parity. Let’s try to prove the following lemma.

Lemma:

Position \{A, B\} is losing if and only if A and B are odd. Every other position is a winning one.

We will prove the lemma by induction on the greater number in the position. Let \{A, B\} be any game position, where A \leq B. We showed that the lemma is true for B \leq 3. Let \{A, B\} be any position where B \gt 3, and we assume that the lemma is true for all positions \{C, D\} where C \leq D and D \lt B. We will show that it is also true for \{A, B\}.

There are two cases to consider:

  1. A and B are both odd.

    No matter which stack is removed
    first, the remaining stack has an
    odd number of nuts in it, so in any
    valid configuration formed by
    splitting it, one stack will have an
    odd number of nuts while the other
    will have an even number of nuts on
    it. Moreover, both these stacks will
    have less nuts than B, so from our
    assumption, we know that the just
    formed position is a winning
    position, so the position \{A, B\} is
    a losing one.

  2. At least one stack have an even
    number of nuts on it.

    It this case, we have to show that
    this position is a winning one. To
    make a desired move, we can split
    the stack with even number of nuts
    on it, so we remove the other one
    first (if there are two stacks with
    an even number of nuts, we can
    remove either one). Now we are about
    to split the stack in two new stacks
    and we can always do this to form
    two new smaller stacks with odd
    number of nuts on both of them. This
    is possible, because our original
    stack has even number of nuts. It
    follows from the assumption, that we
    can make a move which leads to a
    losing position for the opponent, so
    our position is a winning one.

Based on the lemma which we just proved, it follows that the first player has a winning strategy if and only if at least one initial stack has an even number of nuts in it.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

3 Likes

the simplest solution is

from both stack if any of the stack % 2 == 0 then “Tuzik” wins else “Vanka wins”

Nice question :slight_smile:

This solution gave WA during the contest, but after the contest it got AC!!
Why did this happen?? puzzeled…

AC solution after the contest : https://www.codechef.com/viewsolution/7559807
WA during the contest : https://www.codechef.com/viewsolution/7555888

if both stacks have odd number then the second player wins /// else the first one

why did u keep a<=10^4 and b<=10^4. I did an O(a*b) dp and it passed easily . a<=10^9 and b<=10^9 would have been much better!

1 Like

@shashankgarg1: both players are playing optimally, so when 12 12 is contained by stacks, player1 will eat one stack and divide another into 7 5 (or any other pair contining odd nuts on both stack) since that is the optimal move and will make player2 stand at losing position.

“A player loses the game when he is not able to make any valid move.” - this statement is different from the end condition from the problem statement, where is written: “If a player can’t split it he loses (if stack contains only 1 nut)”. So, for example, player loses when all stacks have only 1 nut, although there are some non-empty stacks.

this problem seems to have weak test cases,for example if A=500 and B=500,then vanka should win,but tuzik wins. can anyone explain if I am wrong?

"Based on the lemma which we just proved, it follows that the first player has a winning strategy if and only if at least one initial stack has an even number of nuts in it. "

Can you post the link to your solution?

here it is : https://www.codechef.com/viewsolution/7550905