PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Utkarsh Gupta
Tester: Aryan Choudhary
Editorialist: Taranpreet Singh
DIFFICULTY
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];
vector <int> adj[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
#include <header.h>
#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) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
void assertBinaryString(const string s){
for(auto x:s)
assert('0'<=x&&x<='1');
}
// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
// vector<vi> e(n);
// atcoder::dsu d(n);
// for(lli i=1;i<n;++i){
// const lli u=readIntSp(1,n)-1;
// const lli v=readIntLn(1,n)-1;
// 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;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
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);
T=readIntLn(1,1e3);
lli sumN = 2e5;
const vector<string> answers = {"alIce","boB"};
while(T--)
{
const int n=readIntLn(1,min(100000LL,sumN));
sumN-=n;
const string s=readStringLn(n,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.
cout<<answers[1]<<endl;
continue;
}
if(min(cnt[0],cnt[1])==1){
//P1 makes all chars identical.
cout<<answers[0]<<endl;
continue;
}
cout<<answers[(n+1)&1]<<endl;
} aryanc403();
readEOF();
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class STRADJ{
//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;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
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{
new STRADJ().run();
}
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());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 