INCGAME - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Alice and Bob play a game with two piles of stones, having sizes X and Y.
First, Alice will remove at most K stones from one of the piles.
Thereafter, each player must remove strictly more stones than the previous move from one of the piles.
Predict the winner.

EXPLANATION:

The “strictly larger” condition on each player’s next move is very limiting.
In particular, note that if a player is free to move, simply taking everything from the larger pile will result in their opponent being unable to make a move after that, so we should analyze when this is possible.

First, suppose X and Y are both \leq K.
Then, Alice can always win: her first move is now basically “free”, so she can take the larger pile entirely and Bob can’t do anything.

Next, suppose X and Y are both \gt K.
In this case, Alice will always lose: no matter what Alice does, one of the piles will be \gt K after her move, so Bob will always just take the larger pile and win immediately.

This leaves the case where one of X and Y is \leq K and the other one is \gt K.
For simplicity, let X \leq K and Y\gt K.
Then, note that if Alice makes her first move on the X-pile, Bob can just take the entire Y-pile and win.
So, Alice’s only hope of victory is to remove some stones from the Y-pile.
Simple analysis shows that:

  • If Y \leq 2K, Alice can win by just taking K stones from the Y-pile.
    Bob must now take more than K stones to win, which is impossible since both piles have size \lt K.
  • If Y \gt 2K, Alice can’t win no matter what: the Y pile will always have \gt K stones after her move, so Bob can take them all and win.

We thus have the following solution:

  • Alice wins if;
    • \max(X, Y) \leq K, or
    • \min(X, Y) \leq K and \max(X, Y) \leq 2K.
  • Bob wins otherwise.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x, y, k = map(int, input().split())

    if x <= k and y <= k: print('Alice')
    elif x > k and y > k: print('Bob')
    else:
        if max(x, y) <= 2*k: print('Alice')
        else: print('Bob')
2

void solve() {
ll x, y, k;
cin >> x >> y >> k;

ll min_h = min(x, y);
ll max_h = max(x, y);

if (max_h <= k) {
    cout << "Alice" << endl;
    return;
} else if (min_h <= k) {
    max_h -= k;
    if (max_h >= k || min_h >= k) {
        cout << "Bob" << endl;
    } else {
        cout << "Alice" << endl;
    }
} else {
    if (max_h <= 2 * k) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }
}

}
whats wrong here