Editorial for Baltic OI '12 P1 - Brackets - DMOJ: Modern Online Judge

Editorial for Baltic OI '12 P1 - Brackets

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.

Let's define a correct string of parentheses (round brackets):

() is a correct string of parentheses;
If A is a correct string of parentheses, then (A) also is a correct string of parentheses;
If both, A and B, are correct parentheses strings, then the concatenation AB is also a correct string of brackets.

In other words, a correct parentheses string is a correct string of brackets, but containing no square brackets.

Let us take an arbitrary correct string of parentheses and replace some (perhaps all, but at least one) of the closing (right) parentheses with the opening (left) parentheses. We shall name the resulting string a broken string of parentheses.

It is easy to see that every broken string of brackets is also a broken string of parentheses, and vice versa. In fact, both of them fulfil the following two conditions:

the number of opening brackets is greater than the number of closing brackets;
the number of opening brackets is not less than the number of closing brackets for every prefix of the string.

Accordingly, we will name both, the broken string of brackets and the broken strings of parentheses, broken strings.

For further explanation, let $s$ ~s~ be a broken string. Let $B(s)$ ~B(s)~ denote the set of correct strings of brackets that match the broken string of brackets $s$ ~s~. Let $P(s)$ ~P(s)~ denote the set of correct strings of parentheses that match the broken string of brackets $s$ ~s~.

Lemma

For any broken string $s$ ~s~ the sets $B(s)$ ~B(s)~ and $P(s)$ ~P(s)~ contain the same number of elements.

Proof

Let $s$ ~s~ be a broken string. We set a one-to-one correspondence between the elements of sets $B(s)$ ~B(s)~ and $P(s)$ ~P(s)~.

Let $b$ ~b~ be an arbitrary correct string of brackets from $B(s)$ ~B(s)~. Substitute its every square bracket with a corresponding round bracket (opening with opening, closing with closing). As a result we obtain some correct string of parentheses that matches $s$ ~s~.
Let $p$ ~p~ be an arbitrary correct string of parentheses from $P(s)$ ~P(s)~. We mark all closing round brackets of $p$ ~p~ that correspond to closing round brackets in $s$ ~s~ (that appear at the same position in $p$ ~p~ and $s$ ~s~). Then we mark all opening round brackets in $p$ ~p~ that correspond to the already marked closing round brackets. Finally, we substitute all unmarked round brackets in $p$ ~p~ with square brackets (opening with opening, closing with closing). As a result we obtain some correct string of brackets that matches $s$ ~s~.

It follows from (1) and (2) that $B(s)$ ~B(s)~ and $P(s)$ ~P(s)~ contain the same number of elements. QED.

Thus, we have reduced the task to the following: calculate the number of distinct correct strings of parentheses that correspond to the given broken string. This task is solved using standard dynamic programming.

Let $r(L,i)$ ~r(L,i)~ denote the number of distinct prefixes with length $L$ ~L~ of correct strings of brackets that match the given broken string $s$ ~s~ such that the difference between opening and closing brackets is $i$ ~i~.

$r(0,0) = 1$ ~r(0,0) = 1~, $r(0,i) = 0$ ~r(0,i) = 0~ for all $i>0$ ~i>0~
If $s[L]=$ ~s[L]=~) then $r(L,i) = r(L-1,i+1)$ ~r(L,i) = r(L-1,i+1)~ for all $i = 0$ ~i = 0~, $L \ge 0$ ~L \ge 0~.
If $s[L]=$ ~s[L]=~( then $r(L,0) = r(L-1,1)$ ~r(L,0) = r(L-1,1)~, $r(L,i) = r(L-1,i-1)+r(L-1,i+1)$ ~r(L,i) = r(L-1,i-1)+r(L-1,i+1)~ for all $i > 0$ ~i > 0~, $L \ge 0$ ~L \ge 0~

Note: $s[L]$ ~s[L]~ denotes the $L^\text{th}$ ~L^\text{th}~ symbol of the given broken string $s$ ~s~. $r(N,0)$ ~r(N,0)~ contains the answer, where $N$ ~N~ is the length of the given broken string $s$ ~s~.

This directly leads to a solution with $\mathcal O(N^2)$ ~\mathcal O(N^2)~ time and $\mathcal O(N^2)$ ~\mathcal O(N^2)~ memory complexity. However, this is insufficient to score maximum points.

Firstly, we have to avoid using a two-dimensional array; we have to somehow obtain the same result by a manipulation of one-dimensional arrays. Note that to calculate $r(L,i)$ ~r(L,i)~ for all $i$ ~i~, we need to remember only $r(L-1,j)$ ~r(L-1,j)~ for all $j$ ~j~ (we don't need any $r(L',j)$ ~r(L',j)~ where $L' < L-1$ ~L' < L-1~). Thus, it is enough to maintain only a one-dimensional array throughout the calculations.

Secondly, straight forward implementation of the algorithm is a bit too slow. The correct solution is still $\mathcal O(N^2)$ ~\mathcal O(N^2)~, but we should speed it up by some constant factor.

Note that if $L$ ~L~ and $i$ ~i~ have different parity then $r(L,i) = 0$ ~r(L,i) = 0~. Note also that we are not interested in the values of $r(L,i)$ ~r(L,i)~ when $i > L$ ~i > L~ or $i > N-L$ ~i > N-L~. The first case does not matter because it essentially means that there have been more opening brackets than brackets in total in the prefix, which is impossible. The second case does not matter because it essentially means that there are currently more unclosed opening brackets in the prefix than the number of brackets left until reaching the length $N$ ~N~; this is also an impossible case.

The overall time complexity is $\mathcal O(N^2)$ ~\mathcal O(N^2)~ and memory complexity $\mathcal O(N)$ ~\mathcal O(N)~. Note that the observations mentioned in the previous two paragraphs greatly decrease the number of interesting states and speeds up the execution approximately $8$ ~8~ times.

Side note: This task was proposed for IOI 2011.

Comments

There are no comments at the moment.