PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Danny Boy
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
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:
- Alice selects a 01 subsequence in S and removes it from S.
- Bob selects a 01 subsequence in S and removes it from S.
- 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<vector<int>> adj = {{}};
vector<int> sz = {1}, stk;
int cnt = 1;
adj.push_back({});
for (char &c : s) {
if (c == '(') {
stk.push_back(cnt++);
adj.push_back({});
sz.push_back(1);
} else {
if (stk.empty()) {
adj.clear(); sz.clear();
return make_pair(adj, sz);
} else {
int top = stk.back(); stk.pop_back();
int par = stk.empty() ? 0 : stk.back();
adj[par].push_back(top);
sz[par] += sz[top];
}
}
}
return make_pair(adj, sz);
};
auto [adj, sz] = build(move(cur));
if (!adj.empty()) {
function<bool(int, int)> solve = [&adj = adj, &sz = sz, &solve](int u, int adv) {
if (adv < 0) {
return false;
}
adv++;
int sz_of_children = sz[u] - 1;
if (adj[u].empty()) {
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';
}
}