SPOJ.com - Problem BRCKTS

BRCKTS - Brackets

We will call a bracket word any word constructed out of two sorts of characters: the opening bracket "(" and the closing bracket ")". Among these words we will distinguish correct bracket expressions. These are such bracket words in which the brackets can be matched into pairs such that

every pair consists of an opening bracket and a closing bracket appearing further in the bracket word
for every pair the part of the word between the brackets of this pair has equal number of opening and closing brackets

On a bracket word one can do the following operations:

replacement -- changes the i-th bracket into the opposite one
check -- if the word is a correct bracket expression

Task

Write a program which

reads (from standard input) the bracket word and the sequence of operations performed,
for every check operation determines if the current bracket word is a correct bracket expression,
writes out the outcome (to standard output).

Input

Ten test cases (given one under another, you have to process all!). Each of the test cases is a series of lines. The first line of a test consists of a single number n (1<=n<=30000) denoting the length of the bracket word. The second line consists of n brackets, not separated by any spaces. The third line consists of a single number m -- the number of operations. Each of the following m lines carries a number k denoting the operation performed. k=0 denotes the check operation, k>0 denotes replacement of k-th bracket by the opposite.

Output

For every test case your program should print a line:
Test i:
where i is replaced by the number of the test and in the following lines, for every check operation in the i-th test your program should print a line with the word YES, if the current bracket word is a correct bracket expression, and a line with a word NO otherwise. (There should be as many lines as check operations in the test.)

Example

Input:
4
()((
4
4
0
2
0
[and 9 test cases more]
Output:
Test 1:
YES
NO
[and 9 test cases more]

Warning: large Input/Output data, be careful with certain languages

Submit solution!

Added by:	Adam Dzedzej
Date:	2004-06-15
Time limit:	11s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: NODEJS PERL6 VB.NET
Resource:	Internet Contest Pogromcy Algorytmow(Algorithm Tamers) 2003 Round IV

hide comments

2017-01-25 22:18:38 abualy
TLE with python, even with O( n + m(logn) ) :/

2017-01-15 06:05:20
My 100th AC :)

2016-11-01 13:12:40
it s too easy to salman m(_ _)m

Last edit: 2016-11-01 13:36:15

2016-09-10 21:39:20 shubham
AC in one go :) good one..

2016-09-07 09:55:49
AC in one go :) good one..

2016-08-20 04:54:34 Jamil Siam
nice problem! Definitely worth a shot! :)

These two test cases helped me to come up with a solution:
())(()
()(())

2016-08-19 15:06:25
easy ques :)
forgot to write test :x caused 2 wa

2016-08-02 12:11:16 devender issar
Great. So much to learn from this problem :)

2016-07-23 13:43:54 Ashwani Gautam
for those who are wondering why O(M*N) is getting TLE, segment tree solution is O(N+M (logN)) , which is almost linear in terms of N+M, O(N*M) might seem faster but only for small M, for large M seg tree solution will overrule, dont know why some N*M solutions passed.

2016-07-19 16:29:03 liuxueyang
I am confused the meaning of the "correct bracket expressions", anyone explain the following two sentences more detail?
1. every pair consists of an opening bracket and a closing bracket appearing further in the bracket word
2. for every pair the part of the word between the brackets of this pair has equal number of opening and closing brackets