This problem comes from a competitive programming problem. I'll restate it(feel free to see it here):
A balanced bracket sequence is a bracket sequence(including open and close only) of even length such that we can add 1 and + to make it a valid mathematical expression. Given a balanced bracket sequence (BBS), we then construct a graph that has as many vertices as the length of the BBS. Vertex 1 correspond to first bracket, vertex 2 correspond to second bracket, etc. An edge will only be formed between two vertices i and j iff substring from i to j of the BBS is again a BBS. Count the number of connected components of the constructed graph
My sumission: sumission in C++
My attempt to solve the problem was successful but I can't figure out how to prove my idea rigorously. Here's my idea:
Each pair-up in BBS can be assigned to a level. Say, this sequence "(())". Pair (1, 4) has level 1, pair (2, 3) has level 2. Or, this sequence "(()())()". Pair (1, 6) and pair (7, 8) has level 1; pair (2, 3) and pair (4, 5) has level 2.
My intuition is that all n-level pair-ups that is contained within a (n - 1)-level pair-ups should form a connected component - say, this simplest example: (()()()). Also, all other pair-ups should be separate from each other. So, the way to count is to pay attention to these contained, equal-level pair-ups (counting them all as 1) and discard when they're closed by close bracket. A stack should be suitable in this situation. Here's the psuedo code:
diff := 0 // use this spot levels count := 0 // use this to answer define an empty stack S for each character ch in sequence: if ch is ( then: diff += 1 else: if !S.empty() and S.top() > diff then: while (!S.empty() && S.top() > diff): S.pop() if S.empty() or S.top() != diff then: S.push(diff); count += 1 diff--; Print count as answer
How to prove this algorithm rigorously? My attempt:
Firstly, I define rigorously what a BBS since it's vague to define BBS as stated above:
A BBS is sequence where every its prefix contains more open brackets than close brackets
Secondly, I've tried to understand how the pair-up process works:
Given positions of close brackets as t1 < t2 < t3 < ... < tn, we decide what pairs up with ti(1 <= i <= n) as follows:
t1 pairs up with the closest open bracket
t2 pairs up with the closest open bracket that does not pair up with t1
t3 pairs up with the closest open bracket that does not pair up with t1, t2,
ti pairs up with the closest open bracket that does not pair up with t1, ..., t(i-1).
I've checked and think this definition should partially help us to understand the situation a bit. But it struggles me to come up with "what is a level of a pair-up?". I'm stuck from here. So, my question:
- How to proceed from here?
- How to prove this algorithm rigorously?