Official

B - Bracket Score Editorial by evima


Let us consider the condition that must be satisfied by the set of positions \(x_1,x_2,\cdots,x_k\) occupied by [ and ].

It is necessary that these positions can be decomposed into \(k/2\) pairs. Let \((x_1,x_2),(x_3,x_4),\cdots,(x_{k-1},x_k)\) be the pairs into which they can be decomposed. For each pair, we assume \(x_i<x_{i+1}\) without loss of generality. Then, the \((x_i+1)\)-th through \((x_{i+1}-1)\)-th characters of the good parentheses sequence form a good parentheses sequence, which must have an even length, so we can see that the parities of \(x_i\) and \(x_{i+1}\) differ.

From the above, it is a necessary condition that there are as many odd numbers as even numbers in \(x_1,x_2,\cdots,x_k\). It turns out that it is also a sufficient condition. This follows from the fact that, if there exists \(x\) that satisfies the condition, we can construct a good parentheses sequence as follows:

First, sort the elements of \(x\) in ascending order. Then, choose some adjacent elements \(x_i\) and \(x_{i+1}\) with different parities. Then, pair \(x_i\) and \(x_{i+1}\) with [ and ], and fill in the space between them by repeating (). Then, repeat the same procedure excluding the [()()...()()] part, and it will always result in a good parentheses sequence.

Therefore, it is necessary and sufficient that there are as many odd numbers as even numbers in \(x_1,x_2,\cdots,x_k\). Now, we just have to sort \(B_i-A_i\) for each parity of \(i\), compute the score when choosing the top \(c\) values for every \(0 \leq c \leq N/2\), and find the maximum score. The time complexity of the solution is \(O(NlogN)\).

posted:
last update: