PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh
DIFFICULTY:
1666
PREREQUISITES:
Observation
PROBLEM:
Alice and Bob play a game on a circle with black and white pieces. On their move, a player can choose any subarray of this circle and left-rotate it once. As an extra condition, a move is only valid if the number of positions i with A_i \neq A_{i+1} strictly increases after the move is made.
The person who cannot make a move loses. Determine who wins under optimal play.
EXPLANATION:
The main observation to be made here is as follows:
Let diff(A) denote the number of adjacent pairs of indices with different values in A. Then, any valid move increases diff(A) by exactly 2 - as such, a move is valid if and only if it increases diff(A) by 2.
Proof
This is not too hard to see.
Suppose we perform the rotate operation on the range [L, R]. This is essentially the same thing as deleting A_L from its position, and then inserting it between A_R and A_{R+1}.
Let’s analyze the deletion step:
- If A_{L-1} = A_{L+1}, deletion decreases diff(A) by either 0 or 2, depending on the value of A_L
- If A_{L-1} \neq A_{L+1}, deletion doesn’t change diff(A) at all, no matter what the value of A_L is.
So, deleting A_L either reduces diff(A) by 2, or leaves it the same.
The exact same analysis can be applied to the insertion step to see that insertion either increases diff(A) by 2 or doesn’t change it.
Thus, the only way to increase diff(A) is for the deletion step to not change it, and the insertion step to increase it by 2. Ergo, the only possible increase is +2.
With this observation, the solution is fairly simple:
- Let x be the initial value of diff(A).
- x can be easily computed in \mathcal{O}(N).
- Let y be the maximum possible value of diff(A)
- y can also be computed in \mathcal{O}(N). For diff(A) to be maximum, we would like 0's and 1's to alternate as much as possible. Upon constructing a string like this, it can be seen that y = 2\cdot \min(c_0, c_1), where c_i is the count of i in A. Alternately, you can construct this alternating string and directly compute its difference value in \mathcal{O}(N).
- The number of moves that can be made is then always exactly \frac{y-x}{2}.
- If this value is odd, Alice wins. Otherwise, Bob wins.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
int T,n;
int c[N],cnt[2];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
cnt[0]=cnt[1]=0;
if(c[1]==c[n]) cnt[c[1]]++;
for(int i=1;i<n;i++) if(c[i]==c[i+1]) cnt[c[i]]++;
printf("%s\n",(min(cnt[0],cnt[1])&1)?"Alice":"Bob");
}
return 0;
}
Tester's code (C++)
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
int c[2] = {0, 0};
for(int i = 0; i < n; i++) c[a[i]]++;
if(c[0] > c[1]) {
for(int i = 0; i < n; i++) a[i] = !a[i];
swap(c[0], c[1]);
}
int ans = c[0]*2;
for(int i = 0; i < n; i++) {
if(a[i] != a[(i + 1)%n]) ans--;
}
ans /= 2;
ans &= 1;
if(ans) cout << "Alice\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()))
cur = 0
for i in range(n):
cur += a[i] != a[(i+1)%n]
cur //= 2
mx = min(a.count(0), a.count(1))
print('bob' if cur%2 == mx%2 else 'alice')
