ASYMEAT - 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:

TBD

PREREQUISITES:

None

PROBLEM:

There are N jars of cookies, each containing between 1 and 3 cookies.
Alice and Bob alternate turns, Alice going first:

  • Alice will choose a jar and eat one cookie from it.
  • Bob will choose a jar and:
    • Eat two cookies from it if it has three.
    • Eat one cookie from it otherwise.

The winner is whoever eats the last cookie.
How many of Alice’s initial moves are winning?

EXPLANATION:

First, we must analyze when exactly Alice has a winning position.

Observe that for A_i \leq 2, Alice and Bob have the same move (eat 1 cookie), so the only real difference is for A_i = 3, where Alice eats 1 but Bob eats 2.

In particular, suppose that there are no jars with A_i = 3 at all.
Then, Alice and Bob will each eat one cookie on their move, so it really doesn’t matter what their exact moves are: if there are an odd number of cookies, Alice will definitely eat the last one and win, and if there are an even number, Bob will win instead.

Now, what if there are indeed some jars with A_i = 3?
It turns out that Alice can now always win!

How?

One way to look at the game is in terms of parity: specifically, parity of the number of jars with one cookie.

Suppose there are x jars with one cookie.
Then,

  • Taking a cookie from a jar with one or two cookies will always change the parity of x (it’ll either increase or decrease by 1).
  • If Alice takes a cookie from a jar with three cookies, x doesn’t change.
  • If Bob takes two cookies from a jar with three cookies, the parity of x changes.

In particular, note that Bob will always change the parity of x.

Now, suppose it’s Alice’s move, and x is odd.
This means there’s definitely a jar with one cookie in it - so Alice can eat this cookie and make x even.
Now, no matter what Bob does, x will change parity and go back to being odd on Alice’s move.
This means Alice can never lose the game.

What is x is even?
Now, if all jars have \leq 2 cookies, Alice and Bob are both forced to change the parity of x with each of their moves; so it’s impossible for Alice to win.
If there’s a jar with 3 cookies though, Alice can take one from it: the turn passes to Bob without the parity of x changing!
After Bob makes any move, it’s back to Alice, but x is now odd - so Alice can win.

Let’s use this knowledge to figure out which of Alice’s moves are winning.
From above, we know that only two things really matter: the parity of the number of jars with one cookie (call this x, it’s either 0 or 1), and the number of jars with three cookies (call this y).

First, observe that if y \geq 3, then any move Alice makes is winning: after Alice makes her move, no matter what Bob does there will still remain at least one jar with three cookies on Alice’s next turn; so she can still win from there.

This leaves us with a limited number of cases: 0 \leq y \leq 2.
Let’s analyze each possibility.

  1. Suppose y = 0, so there are no jars with three cookies.
    Then, as noted at the very beginning, Alice’s and Bob’s moves don’t really matter at all: if the total count is odd Alice will always win, otherwise Bob always wins.
    So, the answer here is either N or 0, depending on the parity of x.
  2. Suppose y = 1.
    Then,
    • If x is even, Alice can eat one cookie from the jar with three cookies; and this is winning for her since everything is \leq 2 now, x is still even, and it’s Bob’s turn.
      No other move is winning - anything else she does, Bob can eat two cookies from the jar with three; and it’s Alice’s turn with all jars having \leq 2 cookies and x even, which is a losing state.
      So, the answer is 1 here.
    • If x is odd, the exact opposite holds: any move that’s not eating from the jar with 3 is winning, and eating from that jar is losing.
      The arguments are exactly the same with respect to parity.
      So, the answer is N-1 here.
  3. Suppose y = 2.
    Then,
    • If Alice eats from any jar that’s not a 3, after Bob’s move a 3 will still remain so Alice wins.
      This gives Alice N-2 winning moves.
    • If Alice eats from a 3 jar and Bob then chooses a non-3 jar, he’ll definitely lose.
      So, Bob must eat from the other 3 jar as well.
      The same parity arguments as before show that this is winning for Alice if and only if x was originally even.
    • So, if x is even the answer is N; otherwise it’s N-2.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    three = a.count(3)
    parity = a.count(1) % 2
    if three >= 3:
        print(n)
    elif three == 2:
        if parity == 0: print(n)
        else: print(n - 2)
    else:
        if parity == 1: print(n - three)
        else: print(three)
2

can anyone just explain why would alice always win when y>=3 please give me the proof?

3

It actually follows from the specific cases 0\le y\le 2. We see that Alice has winning strategies if y=1 or y=2 (the answer is never 0), so it’s enough for her to reduce y to those values.

After a turn (both have made their moves), y can only decrease by 0, 1 or 2. Thus, if y\ge3, then after the turn y will still be >=3, or is 2, or 1, never 0. So Alice will always win when y\ge3.