Editorial for Baltic OI '05 P2 - LISP - DMOJ: Modern Online Judge

Editorial for Baltic OI '05 P2 - LISP

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We get a linear-time algorithm via the following result:

Theorem: If a string can be balanced by choosing suitable values for its magic parentheses ], then it can be balanced in a way which chooses $1$ ~1~ for all but the last (rightmost) magic parenthesis ].

Proof: Consider the nondeterministic pushdown automaton accepting the correctly parenthesized strings without magic parentheses. Incorporate magic parentheses into it by guessing nondeterministically the correct number of opening parentheses ( to pop whenever a magic parenthesis is read.

Consider any accepting computation $A$ ~A~ of this automaton. Consider any stage $P$ ~P~ where a magic parenthesis is read, more than one pops are guessed for it, and the input still contains another magic parenthesis. Let $Q$ ~Q~ be the subsequent stage where this next magic parenthesis is read. Modify this computation to guess one less pop at stage $P$ ~P~ and one more pop at stage $Q$ ~Q~. This modified computation $B$ ~B~ is accepting as well:

Before stage $P$ ~P~, $B$ ~B~ proceeds exactly as $A$ ~A~.
Between stages $P$ ~P~ and $Q$ ~Q~ (inclusive), $B$ ~B~ proceeds as $A$ ~A~ except that the stack has one more opening parenthesis, and this extra parenthesis cannot cause $B$ ~B~ to reject due to the structure of this automaton.
After stage $Q$ ~Q~, $B$ ~B~ again proceeds exactly as $A$ ~A~.

The result follows by iterating the argument above until no such stage $P$ ~P~ exists. QED

The automaton used in the proof yields the required algorithm.

Comments

5
d commented on July 3, 2022, 8:55 a.m.
Here's an alternate proof of the theorem.

Proof: Suppose the string can be balanced by choosing suitable values for its ]. In other words, $C_1, C_2, \dots, C_M$ ~C_1, C_2, \dots, C_M~ is a solution.

Suppose there is some index $1 \le i \le M-1$ ~1 \le i \le M-1~ where $C_i > 1$ ~C_i > 1~. The goal is to decrement $C_i$ ~C_i~ and increment $C_M$ ~C_M~. Take a ) from $C_i$ ~C_i~ and move it rightwards to $C_M$ ~C_M~. There are 2 cases when moving ) rightwards by 1 character:

Swap ) with ). This does not change the string.

Swap ) with (. In other words, )( becomes ().

Claim: In any balanced string, changing )( to () results in another balanced string. The proof is an exercise. (Hint: )( is a "decrement, increment" and () is an "increment, decrement")

During every swap, the string remains balanced. Therefore, it's possible to decrement $C_i$ ~C_i~ and increment $C_M$ ~C_M~ to get another balanced string. Do this repeatedly until $C_1 = \dots = C_{M-1} = 1$ ~C_1 = \dots = C_{M-1} = 1~. QED