Longest Regular Bracket Sequence

general
,
1

http://codeforces.com/problemset/problem/5/C

Didn’t understood the meaning of:

“a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression.”

In the example, «(())()» is regular. Is the answer would be 6 1 ?

In the sample test «)((())))(()())» is 6 2. I understood why its 6 2

but if the input had been «)((()))(()())» i.e. removing the bold ‘)’ in previous line, should the answer be 12 1 ?

2

yes, your answer is right is all three cases. Once you finish coding up your solution, have a look at the tutorial here http://codeforces.com/blog/entry/213, should clear your doubts.

1 Like
3

Thanks for the reply. I solved the problem.

I think the definition of regular sequence is given in a better way here:

(though its slightly different definition due to two types of bracket in SPOJ).