Alternative O(n) Greedy Interpretation for Edu CF Round 191 C
Accepted submission: https://codeforces.me/contest/2233/submission/378240026 After reading the editorial, I realized my solution is based on a completely different observation, so I thought I'd share it. I'm not claiming this is a different algorithmic complexity or necessarily different in essence from the editorial. This is simply the way I arrived at an accepted O(n) solution during the contest.
The editorial derives a formula involving prefix opens and suffix closes. My solution instead works directly with the matching structure of the bracket sequence. 2233C - Cost of a Bracket Sequence
Observation 1
The cost is:
length of the longest regular bracket subsequence.
This is equivalent to:
2 × (maximum number of matched pairs)
because every matched pair contributes exactly 2 characters.
Therefore, instead of minimizing the cost, we can think about minimizing the number of matched pairs.
Observation 2
A single deletion can destroy at most one matched pair.
A bracket can belong to at most one pair, so deleting one character can never destroy more than one pair.
Therefore, the goal becomes:
Find brackets whose deletion is guaranteed to destroy exactly one matched pair.
Matching Structure
First, I run the standard stack matching algorithm.
For every matched pair, I store:
pairId[open] = matching_close_index
and mark the closing bracket as matched.
For example:
(()())
gives pairs:
1 ↔ 2
3 ↔ 4
0 ↔ 5
Now I started looking for brackets whose deletion definitely destroys a pair.
Initial Idea
While scanning left to right, consider a matched '('.
If it starts a new active block, deleting it destroys its matching ')' forever.
Similarly, scanning from right to left, certain ')' can be deleted to destroy one pair.
This led to a greedy:
- scan from left and delete suitable '('
- if deletions remain, scan from right and delete suitable ')'
At first this looked correct.
It was not.
WA on Test 181
The first failing testcase was:
5 1
(()()
My solution produced:
00010
which is not optimal.
After debugging for a while, I realized something important.
I was maintaining a prefix/suffix state, but I was counting ALL brackets.
The proof however was only talking about ACTIVE unmatched structure.
These are not the same thing.
---
What is a Suitable Bracket?
Suppose a matched opening bracket '(' is preceded by ')' (or is the first character of the string).
Then this '(' starts a new active block.
Let its matching bracket be ')'.
If we delete this '(', the matching ')' can never participate in another pair.
Why?
For a closing bracket to participate in a pair, there must exist a valid opening bracket before it. Since our deleted '(' was the first opening bracket of that active block, there is no remaining opening bracket that can replace it and form a new pair with its matching ')'.
Therefore deleting such a '(' destroys exactly one matched pair.
The same argument works symmetrically for a closing bracket ')' that ends an active block when scanning from right to left.
This naturally suggests a greedy strategy:
- Scan from left to right and delete suitable opening brackets.
- Every time such a bracket is deleted, invalidate its matching closing bracket.
- If deletions remain, scan from right to left and apply the symmetric rule to suitable closing brackets.
The only remaining difficulty is determining whether a bracket starts (or ends) an active block.
Initially I tried to maintain this using a simple prefix/suffix state and received a WA on test 181.
The mistake was that I counted all brackets, including matched structures that had already been sealed off. Such structures should not influence future decisions because they can no longer participate in new matchings.
After modifying the state to consider only still-active structure, The implementation now matched the invariant I was reasoning about and the solution passed.
Complexity
Pair matching via stack:
O(n)
Left scan:
O(n)
Right scan:
O(n)
Total:
O(n)
Memory:
O(n)
--- Accepted solution
include <bits/stdc++.h>
using namespace std;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
string s,result="";
cin >> s;
vector<int> pairId(n, 0);
stack<int> st;
for (int i = 0; i < n; i++) {
result+='0';
if (s[i] == '(') {
st.push(i);
} else {
if (!st.empty()) {
int openIdx = st.top();
st.pop();
pairId[openIdx] = i;
pairId[i] =1;
}
}
}
int prefix=0;
for(int i=0;i<n;i++){
if(k==0){
break;
}
if(pairId[i]>0 && s[i]=='('){
if(i==0){
result[i]='1';
pairId[pairId[i]]=0;
k--;
}
else if(prefix==0){
pairId[pairId[i]]=0;
result[i]='1';
k--;
}
}
if(pairId[i]==0 && s[i]=='('){
prefix++;
}
if(pairId[i]==0 && s[i]==')'){
prefix=0;
}
}
int suffix=0;
for(int i=n-1;i>=0;i--){
if(k==0){
break;
}
if(pairId[i]>0 && s[i]==')'){
if(i==n-1){
result[i]='1';
k--;
}
else if(suffix==0){
result[i]='1';
k--;
}
}
if(pairId[i]==0 && s[i]==')'){
suffix++;
}
if(pairId[i]==0 && s[i]=='('){
suffix=0;
}
}
for(int i=0;i<n;i++){
cout<<result[i];
}
cout<<"\n";
}
return 0;}
Final Thoughts
What I found interesting is that this solution came from reasoning directly about destroying matched pairs rather than deriving a global formula.
The WA was also a good reminder that sometimes the idea is correct but the code is tracking the wrong invariant.
In my case, the bug was not in the greedy itself but in what the prefix/suffix state was actually representing. If anyone can find a cleaner proof for the "suitable bracket" characterization, I'd be interested to see it.
Great explanation. This really helped. Thank you