PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: arnob918
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Alice and Bob play a game on N piles of stones.
On Alice’s turn, she chooses two piles whose indices have the same parity, and removes one stone from each.
On Bob’s turn, he chooses two piles whose parities are different and transfers a stone from one to the other.
Under optimal play, who wins if Alice starts first?
EXPLANATION:
Let’s get a trivial edgecase out of the way first: if N = 1, Bob can’t make any moves at all; so Alice wins if A_1 \geq 2 (so she can make a move and pass the turn) and loses otherwise.
Now, let’s look at N \geq 2.
Observe that as long as at least one stone remains, Bob can always make a move.
Further, only Alice can reduce the total number of stones, since Bob’s move only moves things around.
So, Alice can win only if she’s the one to remove the last stone.
In particular, since Alice removes two stones at a time; if the total number of stones is odd Alice can never win.
So, let’s look at the case when N \geq 2, and the total number of stones is even.
Let S_{\text{odd}} = A_1 + A_3 + A_5 + \ldots denote the number of stones at odd-indexed piles,
and S_{\text{even}} = A_2 + A_4 + A_6 + \ldots denote the number of stones at even-indexed piles.
Note that:
- Alice’s move subtracts 2 from either S_{\text{odd}} or S_{\text{even}}; and
- Bob’s move subtracts 1 from one and adds 1 to the other.
In particular, after Alice’s move the parity of both quantities doesn’t change, and after Bob’s move the parity of both quantities changes.
Further, since the total number of stones is even, both S_{\text{odd}} and S_{\text{even}} will have the same parity.
Notice that this essentially “uniquely” determines the process of the game, in terms of parities.
For instance, if initially S_{\text{odd}} is even, the game proceeds as follows:
where 0 means both quantities are even, and 1 means they’re odd.
Alice needs to make exactly \frac{\sum A_i}{2} moves (let this be X) to ensure she wins.
In particular, since she’ll make the last move, she needs to ensure that the parity is 0 after her last move.
From the pattern above, it can be seen that if the initial state is 0 and X is even, or if the initial state is 1 but X is odd, this is impossible: after X moves, the state will be 1 which can never be Alice’s win.
In the other two cases, Alice will win.
Proof
If the current state is 0, i.e, there’s an even number of stones at both the odd-index and even-index piles, Alice can always make a move: at least one set of piles will have a positive number of stones (since only Alice can remove stones), and since this number is even that set will have \geq 2 stones which Alice can remove two of.
If the current state is 1, there’s exactly one state when Alice will be unable to move: when there’s one stone at an even pile, and one stone at an odd pile.
However, via our parity argument, reaching such a state is impossible if:
- The starting state is 0, and Alice needs to make an odd number of moves (just before her last move, she would have made an even number of moves; so Bob would’ve done the same and the current state will be )); or
- The starting state is 1, and Alice needs to make an even number of moves (the same argument tells us that Bob would’ve made an odd number of moves; making the state 0 again).
Notice that those are exactly the states we’re claiming Alice to win!
Checking the required conditions is easy in linear time, since all we do is:
- Compute the sum of all piles and divide by 2 to find X, the number of moves Alice needs to make.
- Compute the sum of even-indexed piles to figure out the starting state.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define Q int totalcase; cin >> totalcase; for(int caseno=1; caseno<=totalcase; caseno++)
typedef long long ll;
int a[100005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
Q{
int n;
cin >> n;
int sum = 0;
int od = 0, ev = 0;
for(int i = 0; i < n; i++){
cin >> a[i];
sum += a[i];
if(i%2) od += a[i];
else ev += a[i];
}
if(n == 1){
if(sum >= 2) cout << "Alice\n";
else cout << "Bob\n";
continue;
}
if(sum % 2){
cout << "Bob\n";
continue;
}
if(sum%4 == 0){
if(od%2) cout << "Alice\n";
else cout << "Bob\n";
}
else{
if(od%2) cout << "Bob\n";
else cout << "Alice\n";
}
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n], sum[2];
memset(sum, 0, sizeof(sum));
for(int i=0;i<n;i++)
{
cin>>a[i];
sum[i&1]+=a[i];
}
if(n==1)
{
if(a[0]==1)
cout<<"Bob\n";
else
cout<<"Alice\n";
}
else if((sum[0]+sum[1])&1)
cout<<"Bob\n";
else if((sum[0]+((sum[0]+sum[1])/2) - 1)&1)
cout<<"Bob\n";
else
cout<<"Alice\n";
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
if n == 1:
print('Alice' if s >= 2 else 'Bob')
continue
if s%2 == 1:
print('Bob')
continue
req = s//2
par = sum(a[::2]) % 2
print('Alice' if par != req%2 else 'Bob')
.