BALSEQ - Editorial (NPLTZ15)

general
, ,
1

PROBLEM LINK:

Contest

Author: Devamanyu Hazarika
Tester: Aniket Marlapalle
Editorialist: Devamanyu Hazarika

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Segment-Tree

PROBLEM:

Given a string of paranthesis of characters “(” and “)”, such that frequency of both are same. Now certain queries are provided where characters between two indices are swapped. For each query it is to be printed whether the string is balanced or not.

EXPLANATION:

To solve this question we can make use of the following property -

Let at index i , openi be the count of “(” symbol from index 0 to i and similarly closei be the count of “)” symbol.
Also let diffi be the difference between openi and closei i.e diffi = openi - closei.
Now for the string to be balanced , for all 0 <= i <= N-2 , diffi should be >= 0 and for i = N-1, diffi should be = 0. (Here N is the size of the string). Note that the second condition is always maintained because count of both symbols in the whole string is same throughout the problem.

Let for each Query Q, we get indices i and j as input. Thus characters at i and j will be swapped.

If both the characters are same, then no change will come and the answer will be same as previous state of the string.
If first character is “)” and second character is “(” , then after swapping, for indices “ind” in the range [i , j-1], the value of diffind will increase by 2.
If first character is “(” and second character is “)” , then after swapping, for indices “ind” in the range [i , j-1], the value of diffind will decrease by 2.
Thus after each swap, we need to update the diffi values in the said range and check for minimum diffi in the whole string. If the minimum diffi is >=0 , then the string will be balanced otherwise imbalanced. Segment tree can be used to store the minimum value for diffi.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

2 Likes
2

Another way would be to store a pair in every segment tree node.

Let the pair be { val1 , val2 } , where val1 denotes number of ‘(’ brackets which are not matched with a ‘)’ and val2 denotes number of ‘)’ brackets that have not been matched with a ‘(’.

A ‘)’ bracket will match the closest ‘(’ bracket to it’s left that has not yet been matched.

More formally , for a node corresponding to [L,R] , val1 denotes number of indices ‘i’ such that A[i] == ‘(’ and there exist no ‘)’ at an index j ( i < j <= R ) which matches A[i]. Similarly val2 denotes number of infices ‘i’ such that A[i] == ‘)’ and there exists no ‘(’ at an index j ( L <= j < i ) which matches A[i].

Now for the string to be balanced , the root of segment tree should have both its val1,val2 parameters equal to zero.

For a leaf node :

val1 = 1 and val2 = 0 if the corresponding character is ‘(’

val1 = 0 and val2 = 1 otherwise.

While merging two nodes say left and right , we’ll do this :

cur.val1 = left.val1 + right.val1 - min(left.val1,right.val2)

cur.val2 = left.val2 + right.val2 - min(left.val1,right.val2)

Now the query is just looking at the root of the segment tree and the updates are simply point updates. No Lazy Propagation is required.

2 Likes
3

Almost = to BRACKETS on spoj!!