FOo_bar_2's blog

By FOo_bar_2, history, 4 years ago, In English

Can someone provide some insight on how to approach this problem ?

  • Vote: I like it
  • +8
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

There are two ways I know how to solve a problem like this, small-to-large merging on a tree and centroid decomposition. I'll describe the centroid decomp solution here.

First, we need to note a couple of properties about balanced parentheses strings. As you probably know, if you assign each $$$($$$ to a $$$1$$$ and each $$$)$$$ to a $$$-1$$$, the total sum of the string has to equal $$$0$$$. Moreover, the min prefix sum must be $$$>= 0$$$ as well (but because the total sum is always $$$0$$$, in a balanced string the $$$min ps$$$ is always $$$0$$$). From this point forward, I'm going to refer to the "min prefix sum" as $$$min ps$$$, and the "total sum" as $$$sum$$$.

Now what happens when we concatenate two parentheses sequences? (let's denote them as strings $$$s1$$$ and $$$s2$$$). We need to check if the string $$$s1+s2$$$ is balanced. It is balanced iff, $$$s1$$$'s $$$min ps$$$ is $$$>= 0$$$, $$$s1$$$'s $$$sum + s2$$$'s $$$sum = 0$$$, and $$$s2$$$'s $$$min ps$$$ is $$$>= s2$$$'s $$$sum$$$. I'll leave the proofs as an exercise for the reader.

First, apply standard centroid decomp. Now we just need to solve for all paths going through a certain node. Calculate the $$$sum$$$ and $$$min ps$$$ for all paths leaving the current node and all paths ending at the current node. Using the property above, it is easy to check if it is possible to combine two things. Because the first and third properties are local, you can check if the current string satisfies them without even looking at any other strings. To count how many pairs satisfy the second property, you can store the paths ending at the current node in a map, keyed by the $$$sum$$$ of the string.

Let me know if anything was confusing.

EDIT: A similar problem can be found here