BGME - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: pols_agyi_pols
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are N buckets, the i-th initially containing A_i balls.
Alice and Bob take turns; on their turn, a player removes exactly one ball from some bucket.
If the removed ball is the last one from that bucket, the player receives one point.

Under optimal play, find the winner.

EXPLANATION:

If there’s a single pile of stones (i.e N = 1), the answer is determined entirely by the parity of stones, since each player’s move is forced: if A_1 is odd, Alice wins; otherwise Bob wins.
This hints towards the idea that parity is important.

Next, we try to solve N = 2. It can be seen that:

  • If both piles are even, Bob wins.
    This is because, whenever Alice makes a move on some pile, Bob can make a move on the same pile - it was initially even, so it can’t become empty after Alice’s move.
    This ensures that Bob can always win both piles.
  • If one pile is odd and the other is even, Alice wins.
    Alice removes one stone from the odd pile on her turn; after which both piles are even but it’s Bob’s turn, so Bob will lose (Alice uses the stratagy above).
  • If both piles are odd, there’s a couple more cases to think about.
    • If both piles have \geq 3 stones, Bob will win.
      This is because, which pile Alice chooses on her move, Bob can choose the other one - then it’s Alice’s turn but both piles are even, so she loses.
    • If some pile has 1 stone, it’s a draw.
      Alice can choose the pile with 1 stone on her move, emptying it and getting one point.
      There’s only one pile left now with an odd number of stones, and since it’s Bob’s turn he will win it.

The strategies used above generalize to more than two piles too.
Broadly speaking, these were the ideas used:

  • If one player makes a move on an even pile, the other player makes a move on the same pile.
  • If one player makes a move on an odd pile, the other player makes a move on a different odd pile (if possible), turning them both into even piles.

With these strategies in mind, it can be seen that:

  • If the number of odd-sized piles is even, Bob will never lose.
    • Whenever Alice removes a stone from an odd pile, there will exist some other odd pile; and Bob will remove a stone from this. Both piles turn even after this, and there are still an even number of odd piles.
    • Whenever Alice removes a stone from an even pile, Bob will do the same - the number of odd piles thus doesn’t change.
    • In particular, the only piles Alice can win are the ones that are initially 1 - any other pile turns into a non-zero even pile after her move, and Bob’s strategy ensures that she can never make the last move on any such pile.
      This means, at best Alice can win half the odd piles; so Bob can’t lose.
  • If the number of odd-sized piles is odd, Alice will always win.
    • On her first move, she remove one stone from an odd pile.
    • Now there are an even number of odd piles but it’s Bob’s turn; and from our analysis above we know Bob can win at most half the odd piles.
      Alice will win at least the other half, along with the first pile she removed a stone from - which makes her score always strictly greater than Bob’s.

tl;dr the cases are as follows.
Let there be M piles of odd size, and K piles that are 1. Then,

  • If M is odd, Alice wins.
  • If M is even, Alice will get \left\lceil \frac{K}{2} \right\rceil points, and Bob will get everything else.
    If Bob’s score is greater than Alice’s, he’ll win - otherwise it’s a draw.

Note that \left\lceil \ \ \right\rceil denotes the ceiling function.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    //freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
    ll kitne_cases_hain;
    kitne_cases_hain=1;
    cin>>kitne_cases_hain;
    while(kitne_cases_hain--){          
        ll n;
        cin>>n;
        ll a[n];
        ll o=0;
        ll z=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(a[i]%2){
                o++;
            }
            if(a[i]==1){
                z++;
            }
        }
        if(o%2){
            cout<<"Alice\n";
        }else if(z>=n-1 && n==o){
            cout<<"Draw\n";
        }else{
            cout<<"Bob\n";
        }
    }
	return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    # even odds -> bob never loses
    # alice can get ceil(x+1/2) of the ones, bob everything else
    # odd odds -> alice always wins
    
    odds = sum(x%2 for x in a)
    if odds%2 == 1: print('Alice')
    else:
        ones = a.count(1)
        alice = (ones+1)//2
        if alice == n - alice: print('Draw')
        else: print('Bob')
2 Likes