DENSE Editorial

[foxy7]

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

1472

PREREQUISITES:

Strings

PROBLEM:

A bracket sequence S is called dense if one of the following is true:

• S is empty.
• S = (X) where X is dense.

You are given a bracket sequence S. What is the minimum number of brackets you must remove to make it dense?

EXPLANATION:

In order to solve this problem we can keep a count of all the opening brackets and closing brackets for each position in the string. First we will calculate the number of closing brackets in the string. This would be denoted by close

The maximum answer can be n as we would get a dense string if we remove all the brackets. Now we traverse from 1 to n. Initially we would have 0 opening brackets(denoted by open) and close closing brackets. At each position there can be two cases:

• s[i] = (: Here we increment open by 1. Thus we have open opening brackets in the left and close closing brackets at the right, so the maximum length of dense string that can be formed at this position is min(2 \times open, 2 \times close). Thus,

ans = min(ans, n - min(2 \times open, 2 \times close))

• s[i] = ): Here we simply decrement close by 1.

By the end of our traversal we will have our answer.

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

[yashraj_99]

Why do we subtract twice the maximum dense string length from n when we encounter a ‘(’ ?

[antoney]

in 2nd para . Will it be
Initially we would have 0 opening brackets(denoted by open) and

n close closing brackets

I guess it will be better understandable then

[antoney]

The tester’s solution pastebin is very understandable

[antoney]

ans = min(ans, n - 2*min(open, closed))

This would be the right formula

Check tester’s solution

[antoney]

http://p.ip.fi/9LxV

[snapper_002]

I do it with binary search
if we are able to make den of len-2 ( (()) )
then we can also make lenths< len

ll low = 0;
ll high = max( cnt( ‘)’ ) , cnt( ‘(’ ) );
//do binary search

[adit19shah]

The constraints for this problem as mentioned in the problem statement were: " 2 \le N \le 3.10^5 " but its 8th subtask possibly contains a test-case for N=1 too. My code was constantly giving a wrong answer for subtask 8 during the contest and it was getting difficult for me to debug it. It got an AC as soon as I included a case for N=1.

Link to code failing subtask 8
Link to AC code

As you can see, only difference between the above 2 codes is: n=1 is not handled in the failing code while it is handled in the AC code.

This is not fair since quite a lot of my time got wasted during the contest in debugging a test-case that isn’t following the constraints. @iceknight1093 @utkarsh_adm Please look into it.

[sevenstar08]

CAN someone point out the testcase for which this code will fail?

@utkarsh_adm

#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)
#include
#include <bits/stdc++.h>
#include

#define ll long long
#define ld long double

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    ll t;
    cin>>t;
    while(t--){
       ll n;
       string s;
       cin>>n>>s;
       if(n==1){
           cout<<1<<endl;
       }
       ll pref[n],suff[n];
       ll pre=0,suf=0;
       for(int i=0; i<n ;i++){
           if(s[i] == '('){
               pre++;
           }
           if(s[n-i-1] == ')'){
               suf++;
           }
           
           pref[i]=pre;
           suff[n-i-1] = suf;
           
       }
       
       ll mini = INT_MAX;
       ll aa = 0;
       
       for(ll i=0; i<n ;i++){
          aa=max(aa,min(pref[i],suff[i]));
       }
       
       ll ans = n-(2*aa);
       
       cout<<ans<<endl;

}
return 0;

}

[mahmba]

My solution was kind of different from this for every opening bracket, I found a corresponding closing bracket from the other end. And removed the remaining elements.

void solve(){
    ll n ;
    cin >> n ; 

    string str ; 
    cin >> str ;

    ll ans = 0 , i = 0 , j = n-1 ;

    while(i<j){
        while(i<j && str[i] != '(')
            i++ , ans++ ;
        while(i<j && str[j] != ')')
            j--, ans++ ;
        if(i == j){
            break ;
        }
        i++,j-- ;
    }

    cout << ans + (i == j) << nl;
}

[r_ayush777]

@foxy7

ans=min(ans,n−2×min(2×open,2×close))

Small mistake, Multiplied 2 two times
Correct formula :
ans=min(ans,n−min(2×open, 2×close))

[hiteshmewada]

ans=min(ans,n−min(2×open,2×close))

[utkarsh_adm]

Hi, sorry for the issue. The statement got changed due to which I forgot to update the constraints.

I will correct that test case and rejudge your submission (as well as ranklist).

I see that very few users are affected from this issue. If you want this round unrated for you, you can opt for it too.

Once again, sorry for the issue.

[utkarsh_adm]

I think only you are affected from this change (not sure though). Also on correcting the test case and the rejudging won’t change your rank since you solved that problem in the contest.

So for future practice, I am currently updating the statement to N>=1 instead of N>=2.

Also I am making the round unrated for you.

Sorry

[kaivalya004]

Why my last 2 test cases are failing

#include<bits/stdc++.h>

using namespace std;

/*
freopen(".txt","r",stdin);
freopen(".txt","w",stdout);
*/

/**
use fixed flag for correct decimal place with setprecision
cout << fixed << setprecision;

sort comparator must return false when arguments are equal.

FAST IO
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/

///void LogArray(int );
///void SparseTable(int arr[] , int );
///void PrimeFactorization(int );
///int expo(int  , int  , int );

/***** variable and function area *******/



int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >>n;
        string s;
        cin>>s;
        int l=0 ;
        int itr =0;
        map<int,bool> umap;
        stack<int> stk;
        for(auto i:s){
            if(i == '('){
                l++;
                stk.push(itr);
                umap[itr] = true;
            }
            else{
                l--;
                if(!stk.empty()){
                    umap[stk.top()] = false;
                    stk.pop();
                }
            }
            if(l<0){
                umap[itr] = true;
            }
            itr ++;
        }
        string temp;
        for(int i=0;i<s.length();i++){
            if(umap[i])
                continue;
            temp.push_back(s[i]);
        }
        int ans = s.length() - temp.length();
        int i=0 , j= temp.length()-1;
        while(i<=j){
            if( temp[i] != '('){
                ans++;
            }
            if( temp[j] != ')'){
                ans++;
            }
            i++ , j--;
        }
        cout << ans << endl;
    }
    return 0;
}

[adit19shah]

Alright ! Thanks for considering the issue and making the round unrated for me.

[twnwaking]

Binary search works for this problem.

We search the number of possible matching “dense” brackets.(L…LR…R)

How to check?

We can create two std::vector to store the position of the left and the right brackets respectively.

For example, ()(())() has 4 left and 4 right brackets, so the maximum possible of matching pair is 4.

Now we have two vector for the brackets(0-indexed position for string): \{0, 2, 3, 6\},\ \{1, 4, 5, 7\}

So now let’s binary search in [0,4]

Case 0: True, which is trivial.

Case 1: True. We can match position 0 and 7.

Case 2: True. We need to take left brackets at position 0 and 2. On the other hand, we can greedily take right brackets at position 5 and 7.

Case 3: True. We need to take left brackets at position 0, 2 and 3. On the other hand, we can greedily take right brackets at position 4,5 and 7.

Case 4: False. We need to take left brackets at position 0, 2, 3 and 6. On the other hand, we can greedily take right brackets at position 1,4,5 and 7. However, 1>6, left and right brackets “mixes”, so it’s impossible.

So the pair of matching “dense” brackets is 3, so we don’t need 8-2\times 3=2 brackets.

Code Here

[anon36850761]

Can anyone please point out the error in my logic?
I was just counting the no. of open brackets and closing brackets. Then I created another string with all the open brackets and then all the closing brackets.

Then I compared each and every element of the new string with the old string, where the element differs, we count it for our ans. At the end of loop, I return the ans.

It failed for only 2 test cases, can anyone please point out the error?

[the_blazingone]

    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n/2; i++){
        if (s[i] == '('){
            cnt1++;
        }
        else {
            cnt2++;
        }
    }

    cout << 2*cnt2 << endl;

Why am I getting 8 and 9 test cases wrong, which corner cases am i missing?

[hrishik85]

@the_blazingone - in case this isnt resolved yet - you can ask the doubt solvers here - CodeChef: Practical coding for everyone