BRACKETS - Editorial

editorial
, , ,
1

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

1 Like
2

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");
    }
}
3

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’

4

@siddharths067:
For your answer refer this link:
http://www.quora.com/What-is-the-worst-mistake-youve-made-in-competitive-programming/answer/Chirag-Agarwal-15

1 Like
5

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

6

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?

7

#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?

8

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

9

(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?

10

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…

11

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;
}