ONEORTWO - Editorial

PROBLEM LINK:

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

Author: utkarsh_25dec
Testers: tabr, iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are two piles of stones: the first with X, the second with Y.
Chef and Chefina alternate moves, with Chef moving first.

  • Chef can either remove one stone from both piles or remove two stones from the first pile.
  • Chefina can either remove one stone from both piles or remove two stones from the second pile.

Under optimal play, who wins?

EXPLANATION:

Note that Chef always removes at least one stone from the first pile, and Chefina always removes at least one from the second.
So, ideally Chef always wants there to be stones remaining on the first pile, while Chefina always wants there to be stones remaining on the second pile.

Intuitively, this should tell you that both players will use the “remove one stone from both piles” move as much as possible.

This fixes the set of moves of the game, and so it can be easily simulated to see who wins.
A little bit of casework should tell you that:

  • If X \geq Y+2, Chef will always win.
  • If X = Y+1, Chef will win if X is even and lose otherwise.
  • If X = Y, Chef will win if X is odd and lose otherwise.
  • If X = Y-1, Chef will win if X is odd and lose otherwise.
  • If X \leq Y-2, Chef will always lose.

This can be simplified into:

  • If X \geq Y+2, Chef wins
  • If X \leq Y-2, Chef loses
  • if |X-Y| \leq 1, Chef wins if and only if \min(X, Y) is odd

In fact, this intuition is correct, and the above cases solve the problem!

Detailed proof

Intuition is great to have, but can’t always be relied on. It’s good to get into the habit of proving your solutions.

Let’s prove the above cases by constructing a strategy for them.

  • When X \geq Y+2 the strategy is trivial: Chef always removes one stone from both piles if Y \gt 0, and two stones from his pile if Y = 0.
    No matter what Chefina’s move is, the inequality will be maintained so Chef will always have a move to make.
  • When X \leq Y-2, Chefina follows a similar strategy and cannot lose.
  • When X = Y, if either Chef or Chefina remove two stones from their pile, we enter the |X-Y| \geq 2 state and the other player immediately wins. This means that their best strategy is to alternate taking one stone from both piles.

This leaves the X = Y+1 and X = Y-1 cases, which are fairly similar.
Let’s look at X = Y+1 first.

  • If X is even, Chef can always win with the following strategy:
    • Remove one stone from both piles.
    • If Chefina now removes 2 from hers, |X-Y| \geq 2 and Chef can win.
    • So, Chefina is forced to remove one from each pile.
    • Since X is even and greater than Y, on Chef’s move Chefina’s pile will become empty and she will lose.
  • If Y is even, then Chefina can always copy Chef’s move to preserve the equality, ensuring that she will never lose.

X = Y-1 is similar.
Chef can’t remove two stones from his pile on the first move, or he instantly loses. So, he’s forced to remove one from each.
We’re now in the X = Y+1 situation from Chefina’s perspective, so simply apply that analysis to see who wins and we’re done.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    x, y = map(int, input().split())
    if x > y + 1: print('Chef')
    elif x == y+1: print('Chef' if x%2 == 0 else 'Chefina')
    elif x + 1 < y: print('Chefina')
    elif x+1 == y: print('Chef' if x%2 == 1 else 'Chefina')
    else: print('Chef' if x%2 == 1 else 'Chefina')
3 Likes