PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
Alice and Bob play a game with X piles of one stone each, Y piles with two stones each, and Z piles with three stones each.
On their turn, a player chooses one pile and removes one stone from it.
Alice isn’t allowed to choose the same pile twice in a row.
Alice wins if all stones are removed, and loses if she’s unable to make a move (with a positive number of stones remaining).
Find the winner under optimal play.
EXPLANATION:
It’s generally pretty hard to come up with a strategy for a game by just looking at it directly.
Instead, let’s perform a sort of retrograde analysis: look at Alice’s losing state, and work backwards to figure out what the initial position must have been from there.
Alice loses when she’s forced to pick from the same pile she just picked from.
This is clearly impossible when more than one pile remains, so there must be only a single pile left.
Alice picked a stone from it already, so it can’t have three stones: there must be either one or two remaining.
We’ll analyze both cases separately.
Case 1: The pile has two stones remaining.
It must’ve then had three stones initially (since Alice removed one); and Bob’s last move should’ve been on a different pile. This different pile must’ve had only one stone remaining since it disappeared after Bob’s move.
The piles must’ve hence been \{1, 3\} just before Alice’s previous move.
Now, in this state if Alice removes the 1 she wins, so she’ll always do this if possible.
For it to be impossible, her previous move must’ve been on the 1.
What about Bob’s previous move? There are two cases:
- Bob’s previous move was on a different pile.
This means the piles were \{1, 2, 3\} before Alice’s move of operating on the 2 (and then Bob took a stone from 1).
However, if the piles were \{1, 2, 3\}, Alice has a winning strategy by operating on the 3 first (which is always possible), so she’d never have operated on the 2 in the first place.
So, this branch is impossible, and we don’t need to analyze further. - Bob’s previous move was on the same pile.
This means the piles were \{3, 3\} before Alice’s move.
It’s easy to see that this is a losing state for Alice, so we must next analyze when exactly Bob can force this state to be reached.
When can Bob make Alice reach \{3, 3\}?
(Basically) never!
If the current state is \{3, 3\}, the state before Alice’s previous move must been either \{1, 1, 3, 3\} (where Alice and Bob both removed a 1), or \{2, 3, 3\} (where Alice made it \{1, 3, 3\} and then Bob removed the 1).
However, it can be verified that both \{1, 1, 3, 3\} and \{2, 3, 3\} are winning situations for Alice, if she just removes a stone from one of the piles with 3 stones first instead (which is, of course, always possible).
So, the only possibility for Alice to lose (in this case) is if the game starts out at \{3, 3\}, i.e. with X = Y = 0 and Z = 2.
Case 2: The pile has one stone remaining.
Analyzing in a similar fashion as above, the state just before Alice’s previous move must’ve been either \{1, 2\} or \{3\}.
First, we look at \{1, 2\}. Alice wins \{1, 2\} if she can remove the 1; meaning she wasn’t able to.
This means the state before that was either \{1, 2, 2\} or \{2, 3\}.
Again, Alice wins \{1, 2, 2\} if she can remove the 1; so the previous state must’ve been \{2, 2, 3\} or \{1, 2, 2, 2\} (again with Alice being unable to operate on the 1).
In general, it’s easy to generalize this further: if the current state is \{1, 2, 2, 2, \ldots, 2\} with Alice unable to remove the 1, she loses.
The only way to get to such a state is from \{2, 2, 2, \ldots, 2, 3\}: so Bob can now aim to reach such a state.
Note that the number of twos is irrelevant here, so we can ignore that value (Y) entirely.
Bob wants to give Alice a situation where X = 0 and Z = 1.
To see when this is possible, let’s look at the quantity (Z-X), i.e. the difference between threes and ones.
Note that the final state we want to reach has Z-X = 1 on Alice’s turn.
Now,
- If Z-X is even, it’s impossible for Bob to achieve his goal.
This is because any move made by a player will change Z-X by either +1 or -1; so if it starts off even then it’ll always be even on Alice’s turn.
In particular, this means it can’t ever be 1 on Alice’s turn. - If Z- X is odd, then Bob can achieve his goal if Z-X \gt 0 initially, and cannot do it otherwise.
Proof
Suppose Z - X \gt 0 and is odd.
Then,
- If Alice does 2\to 1 on her move, Bob will always do 1\to 0. This keeps the counts of Z and X the same after both moves.
- Suppose Z-X = 1.
If Z = 1 then Bob has already reached his goal of a winning (for him) state, so suppose Z \gt 1. Note that this then means X \gt 0.
Then,
- If Alice does 3\to 2, Bob does 1 \to 0, so that Z-X hasn’t changed after both moves.
- If Alice does 1\to 0, Bob does 3\to 2 instead - once again, the difference doesn’t change.
- Suppose Z-X \gt 1.
Then no matter what Alice does, Bob can do anything at all. Since the difference can only change by at most 2 after Alice’s and his moves, it will remain odd and positive, so go back to the start of this algorithm and repeat.
Next, suppose Z - X \lt 0.
Then,
- If Z = 0 Bob can’t ever get to the state of (X = 0, Z = 1) anyway so Alice is already safe and can do whatever she wants.
- If Z \gt 0, Alice can perform the move 3\to 2 instead. This reduces Z-X by one, so no matter what Bob does it’ll remain negative.
So, if Z-X \lt 0 Alice is always safe.
Let’s now go back a bit: everything above was obtained by analyzing \{1, 2\} as the “previous” state, but what if it was \{3\} instead?
Well, if it was \{3\} on Alice’s turn, then the turn before that it must’ve been either \{2, 3\} or \{1, 1, 3\}.
\{2, 3\} (and also starting with \{3\}) are already covered under our previous analysis of Z-X being positive and odd; so we only need to look at \{1, 1, 3\}.
However, \{1, 1, 3\} is clearly a winning state for Alice since she can just make it \{1, 1, 2\} and then remove a 1 on the next turn, so we don’t obtain any further losing positions for Alice.
So, putting everything together, we have the following cases where Alice loses:
- X = Y = 0 and Z = 2.
- Z-X is an odd positive integer.
In every other case, Alice wins!
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x, y, z = map(int, input().split())
if (z-x)%2 == 1 and z-x > 0: print('Bob')
elif x == 0 and y == 0 and z == 2: print('Bob')
else: print('Alice')