BRACKETS - Editorial

Problem Link: contest, practice

Difficulty: Cakewalk

Pre-requisites: Basics

Problem:

Given a valid parentheses sequence A. Your task is to find another valid parentheses sequence B with the minimal possible length, such that the maximal balance over all prefixes of A is equal to the same characteristic of B.

Explanation:

This problem requires some logical thinking and being familiar with valid parentheses sequences.

Let’s consider a pseudocode that has been provided to you in the statement:

	FUNCTION F( S - a valid parentheses sequence )
	BEGIN
		balance = 0
		maxbalance = 0
		FOR index FROM 1 TO LENGTH(S)
		BEGIN
			if S[index] == '(' then balance = balance + 1
			if S[index] == ')' then balance = balance - 1
			maxbalance = max( maxbalance, balance )
		END
		RETURN maxbalance
	END

The first observation is that there should be at least maxbalance open brackets in B. Every open bracket should also have a paired closed bracket, so the length of B is at least 2 * maxbalance. Fortunartely, there’s a valid B with the length equal to 2 * maxbalance, it looks like this: the first maxbalance brackets are open brackets, the last max_balance brackets are closed ones. It isn’t hard to prove that this is the only way to construct B with such a length.

So, here are the keypoints of the solution:

  1. Determing the value of maxbalance;
  2. B is maxbalance open brackets and maxbalance closed brackets concatenated together.

Complexity is O(N) per a testcase.

Please, check out Setter’s and Tester’s solutions for your better understanding.

Setter’s Solution: link

Tester’s Solution: link

2 Likes

Why is My Code Getting TLE On submission ??

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX(a,b) ((a>b)?a:b)
char str[100000];
typedef long long int ll;
ll F()
{

    scanf("%s",str);
   ll balance =0;
   ll maxbalance=0;
    for(ll i =0;i<strlen(str);i++)
    {
        if(str[i]=='(')balance++;
        if(str[i]==')')balance--;
        maxbalance=MAX(maxbalance,balance);
    }
    return maxbalance;
}
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll limit;
        limit = F();
        for(ll i=0;i<limit;i++)printf("(");
        for(ll i=0;i<limit;i++)printf(")");
        printf("\n");
    }
}

@siddharths067:
For your answer refer this link:

1 Like

Here’s my code.
#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
char a[100000],b[100000];
scanf("%s",a);
int bal=0,maxbal=0,i,j;
for(int i=0;i<strlen(a);i++)
{
if(a[i]==’(’)
bal++;
else
bal–;
maxbal = max(maxbal,bal);
}
for( i=0;i<maxbal;i++)
b[i]=’(’;
for( j=i;i>0;i–)
b[j++]=’)’;
cout<<b<<endl;
}

return 0;

}

Can you tell me the bug in it?

#include<stdio.h>

#include<string.h>

char a[100001];

int f()

{

int i,balance=0,maxbalance=0,len;

len=strlen(a);

for(i=0;i<len;i++)

{

if(a[i]==’(’)

balance+=1;

if(a[i]==’)’)

balance-=1;

if(maxbalance<balance)

maxbalance=balance;

}

return maxbalance;

}

int main(void)

{

int t=0,i,bal=0;

scanf("%d",&t);

for(i=0;i<t;i++)

{

scanf("%s",a);

bal=f();

for(i=0;i<bal;i++)

printf("(");

for(i=0;i<bal;i++)

printf(")");

}

return 0;

}

Plzz tell me where i am wrong?

(1)
The description of the problem contains the following sentence:
‘It is also guaranteed that A is a valid parentheses sequence.’.
One of the constraints is:
1 ≤ |A| ≤ 100000(105)
so a test case can be ‘(’ or ‘)’ but none of these sequences is valid.

(2)
The description of the problem contains the following sentence:
‘If there are several such strings with the minimal possible length, then Mike will choose the least one lexicographically, considering ‘(’ to be less than ‘)’.’

Is it possible to construct two strings with the minimum possible length? I don’t think so. Why the above information is present in the description?

the value of balance will always be zero ? wont it be?

i mean((()())
if no of opening and closing braces are equal then adding to balance and then substracting 4 from it will make it zero?

i am not able to understand the question…

1 Like

Why do i get a TLE in the following code? Probably Stuck in while(1) Loop

#include <stdio.h>
using namespace std;
int main(){
  int t;
  scanf("%d\n",&t);
  char ch;
  int balance=0;
  int maxbalance=-1;
  while(t--){
    balance=0;
    maxbalance=-1;
    while(1){
      scanf("%c",&ch);
      if(ch=='\n')
        break;
      else if(ch=='(')
        balance++;
      else if(ch==')')
        balance--;
      maxbalance=balance>maxbalance?balance:maxbalance;
    }
    for(int i=0;i<maxbalance;i++)
      printf("(");
    for(int i=0;i<maxbalance;i++)
      printf(")");
    printf("\n");
  }
 
  return 0;
}

It is TLE because of this line:

for (ll i=0; i <strlen (str); i++)

You are calling strlen function for each iteration in the loop. Which is unnecessory. It is sufficient to calculate the length just once. Change that line to :

int len=strlen (str);
for (ll i=0; i <len; i++)

Also change size of string s to 100001 to accommodate the ‘\0’

Thanks , :slight_smile: Will Keep That in Check Next time in a Cook-off

@amol_bhadane In main() function, you are using same variable i in outer & inner for loop.

length of string b is not fixed
it is 2* maxbal

no need to store characters in b
simply print them !

Ya exactly !
bcoz the string length needs to be minimum then we can print just that single
desired type of string as mentioned in editorial
the setter’s more mechanical i guess
imposing uneccessary condition can confuse pro programmers as well!

max_balance gets updated to the largest value of balance
as mentioned int he pseudo code

suppose balance is 1
then max_balance=max(max_balance,balance)=max(0,1) =1
now this max_balalnce will always increase or remains same bcoz’

max_balance=max(max_balance,balance)
means max_balance is either max_balance
or max_balance is balance if balance> max_balance

may be while(1) never terminates i guess
try using editorial, clean logic