Блог пользователя jrarias

Автор jrarias, история, 6 лет назад, По-английски

Can anybody give some hints on this problem plz ??

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    And what about the update operation ?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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!