I was solving the problem C. Sereja and Brackets from codeforces, but editorial provided by them is very fast paced, can anyone please explain in detail how this problem will be solved.
We will support the segments tree. At each vertex will be stored:
av — the maximum length of the bracket subsequence
bv — how many there it open brackets that sequence doesn’t contain
cv — how many there it closed brackets that sequence doesn’t contain
For eg:- First range[L1 to R1] in which a1,b2,c2 are the values and second range[L2 to R2] in which a2,b2,c2.
Now we have to find for range[L1 to R2] or means combining the first and second range. Then a3,b3,c3 are to be set.First we try to find if any new bracket if formed or not.We can find it by min(b1,c2).It is becuase to the a new brackets can only formed when there are some open brackets in left range and some close brackets in right range.
t=min(b1,c2) // no of minimum new brackets formed
a = a1 + a2 + t // total no of brackets = (total brackets in left range) + (total brackets in right range) + (new brackets formed)
b = b1 + b2 - t // total no of open brackets which are not paired=(totals open brackets which are not paired in left range) + (total open brackets which are not paired in right range) - (total no of open brackets that are used to make new brackets )
c = c1 + c2 - t // total no of closed brackets which are not paired=(totals closed brackets which are not paired in left range) + (total closed brackets which are not paired in right range) - (total no of closed brackets that are used to make new brackets )
2 Likes
Thanks, very nice explanation.
Can you please explain how should I could it, looks slightly different from traditional segment tree problems.