jrarias's blog

Balancing parentheses help
By jrarias, history, 6 years ago, In English

Can anybody give some hints on this problem plz ??

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you how to think of it, or which method to solve it? With these problems its typically to think of them as prefix sums where '(' = 1 and ')' = -1, we could do the other way around but this is more intuitive to me. If the cumulative "balace" is always non negative in the range and the total balance is 0 in the range it is balanced.

For method you just have to some method to minimize *= -1 and if the amount of brackets not even it is always "Impossible" otherwise it's possible

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This sequence ')))(((' has total balance 0, yet it's not balanced.

    And what about the update operation ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      As I said cumulative "balace" is always non negative in the range

      So something like )))((( will give -1 -2 -3 2 1 0.

      It cannot be negative (too many right brackets)

      Easy way to keep updatable prefix sums is binary indexed tree.

      Main difficulty of problem is solvign query 2 though.

      → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hi!

It's just a Segment Tree, in each node of the segment tree you can store two numbers: # of open parenthesis not matched in this range, # of close parenthesis not matched in this range.

When you need to merge two intervals, you only match open parenthesis of the left child with the close parenthesis of the right child as much as you can and the rest just add it to the respective field.

For more details, this is my code: https://pastebin.com/BwJ1bv2C

Hope it can be useful!

→ Reply