×

# Editorial request for sereja and brackets from codeforces.

 0 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. asked 30 Apr '18, 06:58 1★arpit728 683●17●65 accept rate: 10%

 2 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 ) answered 30 Apr '18, 11:36 30●2 accept rate: 0% @ashudeshwal Thanks, very nice explanation. Can you please explain how should I could it, looks slightly different from traditional segment tree problems. (01 May '18, 11:57) arpit7281★ I am getting TLE with this solution https://pastebin.com/uwpZLW3i, please help. (01 May '18, 18:06) arpit7281★ I have got AC using fast IO. (01 May '18, 19:28) arpit7281★
 1 check this blog http://codeforces.com/blog/entry/15890 This problem is explained. answered 30 Apr '18, 19:10 11●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,755
×672
×136

question asked: 30 Apr '18, 06:58

question was seen: 379 times

last updated: 01 May '18, 19:28