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.
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.
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
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!
BTW, amazing problem-set, quick editorial! Cheers to the authors.
