Editorial for Baltic OI '05 P2 - LISP - Olympiads 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 \leq i \leq 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