You are not logged in. Please login at www.codechef.com to post your questions!

×

Editorial request for sereja and brackets from codeforces.

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

arpit728's gravatar image

1★arpit728
6831765
accept rate: 10%


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 )

link

answered 30 Apr '18, 11:36

ashudeshwal's gravatar image

3★ashudeshwal
302
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★

@ashudeshwal @vivek_1998299

I am getting TLE with this solution https://pastebin.com/uwpZLW3i, please help.

(01 May '18, 18:06) arpit7281★

@ashudeshwal @vivek_1998299

I have got AC using fast IO.

(01 May '18, 19:28) arpit7281★

check this blog http://codeforces.com/blog/entry/15890 This problem is explained.

link

answered 30 Apr '18, 19:10

coder_to_hack's gravatar image

4★coder_to_hack
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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