GREEDY MOVES DAY 02 – Q3

A. Unusual Competitions

Problem Statement – https://codeforces.com/problemset/problem/1322/A

The greedy choice here is to correct the sequence by reordering it as soon as you get the count of closing brackets equal to opening brackets. Note that, you must check if that is already balanced or not.

We can keep a counter that is incremented for every open brace, and decreases for every close brace. Clearly when it goes negative, we can say there is a defect in ordering. So, next time it goes to zero, you do ordering again!

void solve()
{
	ll n;
	cin >> n;
	string s;
    cin >> s;
    ll ct=0;
    bool flag = 0;
    ll last = -1;
    ll ans = 0;
    rep(i,0,n){
        if (s[i] == ')'){
            ct--;
        }
        else ct++;
        if (ct == 0){
            if (flag){
                ans += i - last;
                flag = 0;
            }
            last = i;
        }
        else if (ct < 0) flag = 1;
    }
    if (ct != 0){
        cout << -1 << endl;
        return;
    }
    if (flag){
        ans += (n -1 -last);
    }
    cout << ans << endl;
    
}

Leave a Reply