Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Little Girl, Tough Game

By PureProtea · Limits 1s, 1.0 GB

Samiya, a little girl, wrote a random sequence of opening brackets and closing brackets on a piece of paper with the pencil and wondered if she takes a subsection of the sequence and rearranges them if it’s possible to form a valid sequence.

Some example of valid sequence of opening and closing brackets: (()), (()()), ((())()).
Some example of invalid sequence: ((()), (()))()), )()()()(()

As she is very young and playful girl, she sometimes replaces ‘(‘ with ‘)’ and vice versa from a position.
As the sequence can be very long in length, she can’t do the calculations on paper, instead, she asks you to help her.

Will you be kind enough to this little innocent girl?


At first line, an integer T will be given, T test cases will follow.

For every test case, you will be given a sequence S, consisting of ‘(‘ and ‘)’. The next line, there will be an integer Q, the number of queries. Then Q query lines will follow.
The queries will be of two types.

1 i j
2 i

The first type of query asks you if it’s possible to rearrange the sequence started from i’th index, ending at j’th index such a way that it forms a valid sequence of opening and closing brackets.

The second type of query wants you to toggle the character at position i. That means if there is a ‘(‘, it’will be ‘)’, if there is ‘)’, it’ll be ‘(‘.


For every case, print the case number.
For every query of type 1, print “YES” on a new line if it’s possible to form a valid sequence rearranging the sequence starting at index i, ending at index j. Otherwise print “NO” on a new line, without the quotes.


1 <= T <= 5
1 <= |S| <= 10^5
1 <= Q <= 10^5
1 <= i <= j <= |S|


1 2 3
2 2
1 2 3
2 4
1 1 4
Case 1:

Data set is huge, use faster IO methods.



    77% Solution Ratio

    shaheen_bdEarliest, Sep '17

    skmonirFastest, 53728.3s

    Raihanur_RLightest, 1.0 MB

    NirjhorShortest, 934B


    Login to submit


    Related Contests

    A Tribute to Dennis Ritchie Contest Ended at 2017-09-14 18:30:00 +0000 UTC
    Nepal Team Selection Contest 1 for ACM-ICPC Dhaka Regional 2017 Ended at 2017-10-03 18:15:00 +0000 UTC