# BSG - Editorial

Setter: Danny Boy
Tester: Harris Leung
Editorialist: Trung Dang

4015

# PREREQUISITES:

Bracket Sequence, Binary Search, DFS

# PROBLEM:

There is a binary string S. Alice and Bob are playing a game on it.

Each turn, the following happens:

1. Alice selects a 01 subsequence in S and removes it from S.
2. Bob selects a 01 subsequence in S and removes it from S.
3. After both players have moved, the turn is called completed and Alice scores 1 point. Then, the next turn begins.

If either player is unable to move (there isnâ€™t any 01 subsequence left in S), that turn ends immediately and the game ends.

Alice tries to maximize her points, while Bob tries to minimize Aliceâ€™s points. Find how many points Alice would score if both players play optimally.

# EXPLANATION:

For ease of explanation, letâ€™s convert each 0 character to a (, and convert each 1 character to a ).

Before solving the problem, letâ€™s try to understand first for which bracket sequence T can Alice fully clear (of course, Bob tries to prevent Alice from fully clearing this sequence). A necessary condition is that T is a correct bracket sequence, so without loss of generality let T be a correct bracket sequence.

Note that Bobâ€™s strategy is to turn T into an incorrect bracket sequence as soon as possible. If we denote each ( having value 1 and each ) having value -1 and consider the prefix sum of these values, we have the following observation:

• Each () subsequence removal will decreasing the prefix sum of every character between the ( and ) by 1
• A bracket sequence becomes incorrect if some prefix sum becomes -1.

Therefore, it is Bobâ€™s best interest to decrease the prefix sum of all characters in each move, which corresponds to the strategy of removing the first ( and the last ) every time. Similarly, it is Aliceâ€™s best interest to not decrease any prefix sum, which corresponds to removing a matched-and-consecutive () pair.

Since we have figured out the strategy, letâ€™s go back to the checking problem. I will define the concept of â€śAliceâ€™s move advantageâ€ť: how many moves can Alice freely use before Bob â€śforcesâ€ť an incorrect bracket sequence (it will be clearer once we know how this works).

Initially, Alice has 1 move advantage (because she goes first). Consider a correct bracket sequence T, we have the following observation:

• If T's first ( and last ) are matched, then we know that Bobâ€™s first move will not make T an incorrect bracket sequence. Therefore, Aliceâ€™s advantage is added by 1.
• Otherwise, we need to make the first ( and last ) match. String T then will have the structure of S_1 \, S_2 \, \dots \, S_k, where each S_i is a correct bracket sequence. We can only make first ( and last ) match by choosing some S_i and fully deleting every other S_j (where j \ne i). This means Alice has to spend her move advantages into clearing these other strings, which means her move advantage is decreased by \sum_{j \ne i} \frac{|S_j|}{2}. Also note that if this decreases her move advantage to below 0, Bob will catch up and force an incorrect bracket sequence.

This leads to a traversal solution, where we build a tree based on the correct bracket sequence T. At each subtree, we have Aliceâ€™s move advantage, and we choose which child of this subtree we want to go to. T then can be clear if we can find a path from root to some leaf such that along the way, Aliceâ€™s move advantage never drops below 0. Therefore, now we know how to check whether any bracket sequence can be fully cleared.

Furthermore, we have the following observation:

• For any bracket sequence S, if we know that the answer is K, then we only care about whether the string created from the first 2K ( characters and the last 2K ) characters of S can be fully cleared. In Bobâ€™s perspective, he only removes the first ( and the last ) every time, so he doesnâ€™t care about the remaining characters. In Aliceâ€™s perspective, the last ( characters and the first ) characters are harder to remove than the first ('s and the last )'s, so she also doesnâ€™t care about the remaining characters.

Hence, we arrive at a binary search solution: bisect the answer K, each time taking the first 2K ( and the last 2K ) of S, and check with the previous algorithm detailed.

# TIME COMPLEXITY:

Time complexity is O(N \log N) per test case.

# SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
void db() {cout << '\n';}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
#ifdef Cloud
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define file ios::sync_with_stdio(false); cin.tie(0)
#endif
const int N = 2e5 + 1, mod = 998244353, inf = 1e9;
vector<int> ch[N];
int len[N];
bool dfs(int u, int hp){
//db(u, hp, ch[u].size());
if (hp < 0) return false;
if (ch[u].size() == 0) return true;
for (int i : ch[u]) if (dfs(i, hp - (len[u] - len[i] - 2) / 2 + 1)) return true;
return false;
}
bool check(vector<int> v){
int n = v.size();
vector<int> tmp;
for (int i = 0; i <= n; i++) ch[i].clear();
tmp.push_back(n);
len[n] = n + 2;
for (int i = 0; i < n; i++){
if (v[i] == 0) tmp.push_back(i);
else{
if (tmp.size() == 1) return false;
int u = tmp.back();
tmp.pop_back();
len[u] = i - u + 1;
if (!tmp.empty()) ch[tmp.back()].push_back(u);
}
}
if (tmp.size() > 1) return false;
return dfs(n, 0);
}
void solve(){
string s;
cin >> s;
int n = s.size();
int l = 0, r = n / 2 + 1;
while (l < r){
int mid = l + r >> 1;
bool tag[n]{};
int cnt = 0;
for (int i = 0; i < n; i++){
if (s[i] == '0') cnt++;
if (s[i] == '0' and cnt <= mid * 2) tag[i] = 1;
}
cnt = 0;
for (int i = n - 1; i >= 0; i--){
if (s[i] == '1') cnt++;
if (s[i] == '1' and cnt <= mid * 2) tag[i] = 1;
}
vector<int> v;
for (int i = 0; i < n; i++) if (tag[i]) v.push_back(s[i] - '0');
if (v.size() < mid * 4 or !check(v)) r = mid;
else l = mid + 1;
}
cout << l - 1 << '\n';
}
signed main(){
file;
int t;
cin >> t;
//db(check({0 ,1, 0, 0, 1, 0, 1, 1 }));
while (t--) solve();
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n,m;
string s;
int a[200001];
int b[200001];

int l[200001],r[200001];
vector<int>ch[200001];
int king;
bool dfs(int id,int ly,int hp){
if(hp<0) return false;
if(ly==king) return true;
for(auto c:ch[id]){
int nh=hp+2-((r[id]-l[id])-(r[c]-l[c]))/2;
if(dfs(c,ly+1,nh)) return true;
}
return false;
}
void solve(){
cin >> s;n=s.size();s='?'+s;
int sl=0,sr=n/4;
while(sl!=sr){
int mid=(sl+sr+1)/2;king=mid;
for(int i=0; i<=n ;i++){
b[i]=false;
ch[i].clear();
}
int life=2*mid;
for(int i=1; i<=n ;i++){
if(life && s[i]=='0') b[i]=true,life--;
}

bool ok=true;
if(life!=0) ok=false;
life=2*mid;
for(int i=n; i>=1 ;i--){
if(life && s[i]=='1') b[i]=true,life--;
}
if(life!=0) ok=false;

if(!ok){
sr=mid-1;continue;
}
life=0;
for(int i=1; i<=n ;i++){
if(b[i]) a[++life]=s[i]-48;
}
stack<int>s;
int ptr=0;
s.push(0);
l[0]=0;r[0]=4*mid+1;
for(int i=1; i<=4*mid ;i++){
if(a[i]==0){
l[++ptr]=i;ch[s.top()].push_back(ptr);
//cout << "e " << s.top() << ' ' << ptr << endl;
s.push(ptr);
}
else{
r[s.top()]=i;s.pop();
}
if(s.empty()){
ok=false;break;
}
}
if(ok) ok&=dfs(0,0,0);
if(ok) sl=mid;
else sr=mid-1;
}
cout << sl << '\n';
}
int main(){
ios::sync_with_stdio(false);
int t;cin >> t;while(t--) solve();
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
string s; cin >> s; transform(s.begin(), s.end(), s.begin(), [](char c) { return c == '0' ? '(' : ')'; });
int n = s.size();
int le = 0, ri = n / 4;
while (le <= ri) {
int mi = (le + ri) / 2;
bool ok = false;
// greedily takes 2 * mi left 0 and 2 * mi right 1
vector<int> pos;
for (int i = 0, cur = 0; i < n; i++) {
if (s[i] == '(' && cur < 2 * mi) {
pos.push_back(i);
cur++;
}
}
for (int i = n - 1, cur = 0; i >= 0; i--) {
if (s[i] == ')' && cur < 2 * mi) {
pos.push_back(i);
cur++;
}
}
if (pos.size() == 4 * mi) {
sort(pos.begin(), pos.end());
string cur;
for (int ind : pos) {
cur += s[ind];
}
auto build = [](string &&s) {
// one outer layer for ease of implementation in solve
vector<int> sz = {1}, stk;
int cnt = 1;
for (char &c : s) {
if (c == '(') {
stk.push_back(cnt++);
sz.push_back(1);
} else {
if (stk.empty()) {
} else {
int top = stk.back(); stk.pop_back();
int par = stk.empty() ? 0 : stk.back();
sz[par] += sz[top];
}
}
}
};
return false;
}
int sz_of_children = sz[u] - 1;
return true;
}
for (int v : adj[u]) {
if (solve(v, adv - (sz_of_children - sz[v]))) {
return true;
}
}
return false;
};
ok = solve(0, 0);
}
}
if (ok) {
le = mi + 1;
} else {
ri = mi - 1;
}
}
cout << ri << '\n';
}
}

1 Like