BRACKS - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Author: Sibasish Ghosh

Tester: Pritish Nayak

Editorialist: Sibasish Ghosh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You are given a regular bracket sequence S of length N. Your task is to tell if there exists another regular bracket sequence with a larger depth than the original sequence and with the same number of opening and closing brackets as the original sequence.

EXPLANATION:

Same number of opening and closing brackets as the original sequence basically means that you have to rearrange the given sequence.

A regular bracket sequence of the form ((((...)))), can never be rearranged to form another regular sequence of a larger depth. The new depth will always be less than or equal to the original depth. Hence, just find out if the given sequence is of the form ((((...)))). If yes, print NO. Otherwise, print YES.

Refer to the solutions below if you face any problem.

SOLUTIONS:

Setter's/Editorialist's Solution 
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()

using namespace std;
typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input7.txt","r",stdin);
    // freopen("output7.txt","w",stdout);
    ll t=1;
    cin>>t;
    while(t--)
    {
        ll n,i,f=0;
        cin>>n;
        string s;
        cin>>s;
        for(i=0;i<n/2;i++)
        {
            if(s[i] == ')')
            {
                f=1;
                break;
            }
        }
        if(f)
            cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}
Tester's Solution 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int32_t main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
   #ifdef Zoro
   freopen("/home/pritish/Competitive/in", "r", stdin);
   freopen("/home/pritish/Competitive/out", "w", stdout);
   #endif  
 
   int t;
   cin>>t;
 
   assert(t>=1&&t<=100000);
 
   int sumn=0;
 
   while(t--)
   {
      int n;
      cin>>n;
 
      
      sumn+=n;
 
      assert(n%2==0);
      assert(n>=2&&n<=200000);
      assert(sumn>=1&&sumn<=1000000);
 
      string s;
      cin>>s;
 
      //---checking if regular or not---
      int cnt=0;
      for(int i=0;i<n;i++)
      {
        assert(s[i]=='('||s[i]==')');
        if(cnt<0)abort();
        if(s[i]=='(')cnt++;
        else cnt--;
      }
      assert(cnt==0);
 
      //---checking done---
 
      string t="";
      for (int i = 0; i < n/2; ++i)
        t+="(";
      for (int i = 0; i < n/2; ++i)
        t+=")";
 
 
      if(t!=s)
        cout<<"YES\n";
      else cout<<"NO\n";
 
   }
 
   cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
   return 0;
}

Feel free to write your approach in the comments :slight_smile:

1 Like