CLBRKT EDITORIAL

PROBLEM LINK

Practice
Contest

Author: Aman Kumar Singh
Tester: Sarthak Manna, Smit Mandavia, Avijit Agarwal
Editorialist: Avijit Agarwal

DIFFICULTY

Easy

PREREQUISITES

Stacks

PROBLEM

You are given a string S of length N consisting only of opening brackets ( and closing brackets ). Consider Q cases. In the i^{\text{th}} case, Chef appears at time t_i and faces all characters from index t_i to N. Find the minimum index x (ti≤x≤N) such that the substring S_{t_i..x} contains a valid non-empty bracket subsequence. However, the valid subsequence must contain the same number of opening brackets as the substring S_{t_i ... x}, ie, you cannot remove any opening bracket from the substring. If such an x does not exist, print -1.

EXPLANATION

The time t_i is completely analogous to the position t_i in the string S. The first thing to observe is that the valid non-empty bracket subsequence must be a substring as it needs to have all the opening brackets in S_{t_i ... x} and thus leaving out a closing bracket would not minimize x. A valid bracket substring must start with an opening bracket. So we need to find the first opening bracket which appears on or after the position t_i in the string S. We can do it easily by iterating from N to 1 and assign the last occurence of an opening bracket to the current position. Let us call the position of this first opening bracket on or after the position t_i as z.

So now the job is reduced to finding a valid non empty bracket substring S_{z..x} where x should be minimal. This can be done easily using a simple stack operation. We maintain a stack which contains only the positions of opening bracket from the first position of an array. If we encounter an closing bracket at a position x, we pop the top of the stack containing the position z and assign x as the minimal position such that S_{z..x} is a valid non empty bracket substring.

The time complexity required is \mathcal{O}(N+Q)

SOLUTIONS

C++ solution can be found here.
Java solution can be found here.
Python solution can be found here.

7 Likes

It would have been better if you had given input how many brackets will be there
Good question on stacks

Thanks :slight_smile:

8 Likes

My solution’s time complexity is O(N+Q) as well, can someone explain why I got TLE?
https://www.codechef.com/viewsolution/35689309

Thanks in advance!

They told fast I/O. Maybe that can be a reason.

use fast io and “\n” instead of endl

1 Like

sorry, linked the wrong solution. I tried fast I/O as well, still got TLE

1 Like

My solution’s time complexity is O(Q*log2(S)), can someone explain why I got TLE?
https://www.codechef.com/viewsolution/35682049

Thanks in advance!

The map you’re using for storing the next index, may blow up the complexity. But I’m not much sure about it. Try using array for storing that index.

1 Like

https://www.codechef.com/viewsolution/35678919
why I am getting runtime error for this solution, please help.
I tried numerous modifications but every time it was either runtime error or tle.

The Question was Highly Unclear.
“Balanced bracket subsequence” should have been clarified.

11 Likes

Hey, could this be solved without using stack. I tried do it using simple incrementation to count the opening and closing brackets. Is the concept wrong or am I missing any test cases.
https://www.codechef.com/viewsolution/35678789

My solution was different, I used prefix sums: https://www.codechef.com/viewsolution/35673284

https://www.codechef.com/viewsolution/35691049
It gives WA. Please help me with the testcase.

Link to AC
I added these two lines-

#define endl '\n'
cout.tie(NULL);
2 Likes

Thanks a lot! Didn’t know \n was that much faster before the contest.

3 Likes

Can anyone help me with this approach. Here is my solution.
Here is my solution.
https://www.codechef.com/viewsolution/35691086
@ssrivastava990, @akshitm16, @aneee004, @hetp111

1 Like

OMG! I have used endl too. Tried 5-6 different solutions before and AC now :frowning:
Due to this TLE, i haven’t even read the next questions

1 Like

In my template, when I was making changes to it before the contest, Sublime Text auto-changed cin.tie(NULL) line to cout.tie(NULL), because it was written above in the code. And I got stuck with TLE, for the whole 2 hours, due to this blunder of auto-change. At last, got my eye on this line, and I was like “WTH”. Just submitted my first solution and got ACed. Could have been around Rank ~150 and now around ~980. Negative Delta Incoming! :no_mouth:

BTW, amazing problem-set, quick editorial! Cheers to the authors.

1 Like

Mene to or pagal panti machai …

First submit I got TLE bcz i define endl after my typenames -


template <typename T>
void print(T x){cout<<x<<endl;}
template <typename T1, typename T2>
void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
template <typename T1, typename T2,typename T3>
void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}

#define endl '\n'

after this i wrote #define before typename and AC

#define endl '\n'

template <typename T>
void print(T x){cout<<x<<endl;}
template <typename T1, typename T2>
void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
template <typename T1, typename T2,typename T3>
void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
1 Like

I don’t find any case where your code goes wrong, @aneee004 will look into this.

1 Like