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

Simple

PREREQUISITES:

None

PROBLEM:

There are N boxes of chocolates, box i has A_i chocolates.

Alice and Bob play a game.
If the total number of remaining chocolates is even, it’s Alice’s turn. Otherwise it’s Bob’s turn.
On their turn, a player chooses any one box and eats a positive number of chocolates from it.

Find Alice’s chocolate count if both players play optimally to eat as many as possible.

EXPLANATION:

Suppose it’s Alice turn currently.
Then, note that if she eats an even number of chocolates, it will still remain her turn afterwards; since the parity of the total count doesn’t change.
On the other hand, if she eats an odd number of chocolates, it will be Bob’s turn next.

The exact same applies to Bob: if he eats an even number the turn remains his; otherwise it shifts to Alice.

So, ideally a player just eats an even number of chocolates as many times as they can, before being forced to eat an odd number.

This can be done as follows:

  • If there’s a box with an even number of chocolates, eat all of them.
  • If there’s a box with an odd number of chocolates, eat all of them except one.

By repeatedly doing this, eventually the resulting state will be: every initially even box becomes empty; and every initially odd box will have exactly one chocolate left.
At this point, each player has no choice but to eat one chocolate at a time, repeatedly passing the turn to the other.

So, let’s define S = A_1 + A_2 + \ldots + A_N to be the total number of initial chocolates.

If S is even, Alice moves first.
She will eat all chocolates from even-sized boxes, and all but one from odd-sized boxes.
Then, the odd-sized boxes will alternate between her and Bob, with her going first.
Thus, if O denotes the number of odd-sized boxes initially, Alice will be able to eat

S - \left\lfloor \frac{O}{2} \right\rfloor

where \left\lfloor x \right\rfloor denotes the integer obtained by rounding down x.

On the other hand, if S is odd, Bob will move first.
The exact same logic applies: just that since Bob moves first he’ll eat the bulk of chocolates instead, leaving Alice with

\left\lfloor \frac{O}{2} \right\rfloor

That this strategy is optimal is not hard to prove: note that for any odd box, some player must eat an odd number of chocolates at least once in order to fully clear it.
Thus, the turn must definitely change at least as many times as there are odd-size boxes.
So, if Alice starts, Bob will definitely get at least \left\lfloor \frac{O}{2} \right\rfloor turns - and will eat at least one chocolate on each of those turns.
Our strategy for Alice ensures that Bob eats exactly \left\lfloor \frac{O}{2} \right\rfloor chocolates so is clearly the best Alice can do.
Similar logic holds for when Bob starts.

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()))

    s = sum(a)
    odd = 0
    for i in range(n):
        odd += a[i]%2

    if s%2 == 0: print(s - odd//2)
    else: print(odd//2)