Setter: Utkarsh Gupta
Tester: Aryan Choudhary
Editorialist: Taranpreet Singh

Easy

# PREREQUISITES

Combinatorial game theory, winning and losing states in game theory

# PROBLEM

Given a binary string S of length N, Alice and Bob play on this string, taking turns to apply the operation. The player unable to apply operation loses.

In an operation, the player chooses an index 1 \leq i \lt |S| such that S_i \neq S_{i+1} and erase either S_i or S_{i+1}. The remaining parts after erasing character are joined and become adjacent.

# QUICK EXPLANATION

• If the string contains only zeros or only ones, Alice cannot make a move at all, so Bob wins
• If the string contains exactly one occurrence of zero (or exactly one occurrence of one), then Alice can delete that one character, putting Bob in losing position.
• Otherwise, we can prove that the answer depends on the parity of N. Alice wins only if N is odd.

# EXPLANATION

Since this is a game theory problem, understanding of winning and losing states is crucial here. Refer this before reading further.

Let us tackle the easier cases. If the string consists of all zeros or all ones, no operation is possible, so it is losing position.

If the string contains exactly one occurrence of one of the characters, then Alice can delete that unique character, putting Bob in a losing position. Thus, if either 0 or 1 appears exactly once, Alice wins.

### General case

Let’s denote c_0 as the number of 0 in S, and c_1 as the number of 1 in S.

Now we can assume that c_0, c_1 \geq 2. In one operation, a player can delete either one occurrence of 0 or one occurrence of 1.

Let’s denote (c_0, c_1) as the state of string S, having c_0 zeros and c_1 ones. Then from state (c_0, c_1), we can only go to state (c_0-1, c_1) or (c_0, c_1-1). We can visualize it as a DAG of states.

For each state, we aim to determine whether it is a winning state or a losing state.

From base cases, we know that states (x, 0) and (0, x) are losing state for any x and states (1, x) and (x, 1) are winning states for any x.

What happens for state (2, 2), we can go to state (1, 2) or (2, 1), both of which are winning states. Hence, we cannot put our opponent in losing state. Hence, (2, 2) is a losing state.

Similarly, if we are on state (2, 3), we can put our opponent to (1, 3) or (2, 2). We know that (1, 3) is winning, but (2, 2) is losing. Hence, we can put our opponent to losing state by moving to (2, 2). Hence, (2, 3) is the winning state.

Proceeding like this, we get the following matrix where cell (i, j) denote whether state (i, j) is winning or losing.

00000000
01111111
01010101
01101010
01010101
01101010
01010101


It is easy to prove that except for base cases, the answer depends only on the parity of N. The state (x, y) is the winning state if and only if x+y = N is odd.

# TIME COMPLEXITY

The time complexity is O(|S|) per test case.

# SOLUTIONS

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
int cnt0=0,cnt1=0;
for(auto ch:s)
{
if(ch=='0')
cnt0++;
else
cnt1++;
}
if(min(cnt0,cnt1)==0)
{
cout<<"Bob\n";
return;
}
if(min(cnt0,cnt1)==1)
{
cout<<"Alice\n";
return;
}
if(n%2==1)
cout<<"Alice\n";
else
cout<<"Bob\n";
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T=1;
cin>>T;
int t=0;
while(t++<T)
{
//cout<<"Case #"<<t<<":"<<' ';
solve();
//cout<<'\n';
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester's Solution
/* in the name of Anton */

/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}

vi a(n);
for(int i=0;i<n-1;++i)
return a;
}

void assertBinaryString(const string s){
for(auto x:s)
assert('0'<=x&&x<='1');
}

// #include<atcoder/dsu>
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         e[u].pb(v);
//         e[v].pb(u);
//         d.merge(u,v);
//     }
//     assert(d.size(0)==n);
//     return e;
// }

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end())         m.insert({x,cnt});
else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt)            m.erase(jt);
else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a;
//priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
lli sumN = 2e5;
while(T--)
{
sumN-=n;
assertBinaryString(s);
vi cnt={0,0};
for(auto x:s)
cnt[x-'0']++;

if(min(cnt[0],cnt[1])==0){
//No moves for P1.
continue;
}

if(min(cnt[0],cnt[1])==1){
//P1 makes all chars identical.
continue;
}
}   aryanc403();
return 0;
}

Editorialist's Solution
import java.util.*;
import java.io.*;
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
String S = n();
int[] cnt = new int[2];
for(int i = 0; i< N; i++)cnt[S.charAt(i)-'0']++;
if(Math.min(cnt[0], cnt[1]) == 0)pn("Bob");
else if(Math.min(cnt[0], cnt[1]) == 1)pn("Alice");
else pn((N%2 == 1)?"Alice":"Bob");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always.

6 Likes

Can anyone explain how to apply Sprague-Grundy Theorem here
also why the answer does not depend on the number of the transition point? like how to prove answers of 0000111111 is the same as 1010101011

2 Likes

@taran_1407 Hey, the link to the editorial under the problem is broken. Not only this, the link for the editorial of BININV is also not working. Could you fix that?

Edit: Even for the PARPERM Problem.

Easier Version (CF) : Problem - 1373B - Codeforces

2 Likes