C - Bracket and Permutation Editorial by evima
If \(P_{2i-1} > P_{2i}\), we can see that \(S_{P_{2i-1}}=\) ( and \(S_{P_{2i}}=\) ) must hold (otherwise, we could swap \(P_{2i-1}\) and \(P_{2i}\)). Similarly, if \(Q_{2i-1} < Q_{2i}\), it must hold that \(S_{Q_{2i-1}}=\) ( and \(S_{Q_{2i}}=\) ).
It turns out that, after this observation, if we still have more than one candidate for \(S\), there is no \(S\) that satisfies the condition.
Proof
For simplicity, we consider the case \(S\) is a correct parenthesis sequence or its reversal. The general case can be proved in the same way, using the fact that a general \(S\) can be represented as the concatenation of correct parenthesis sequences and their reversals.
Assume that \(S\) is a correct parenthesis sequence. Let \(L_1 < L_2 < \dots < L_N\) be the indices \(i\) such that \(S_i=\) ( and \(R_1 < R_2 < \dots < R_N\) be the ones such that \(S_i=\) ). Since \(S\) is a correct parenthesis sequence, we have \(L_i < R_i\). Therefore, the lexicographically largest \(p\) such that \(S_{p_1}S_{p_2}\dots S_{p_{2N}}\) is a correct parenthesis sequence is \(p=(L_N,\ R_N,\ L_{N-1},\ R_{N-1},\ \dots,\ L_1,\ R_1)\), in which case we can restore \(S\) from \(Q\) by the above observation only.
If \(S\) is a reversed correct parenthesis sequence, we can restore it similarly from \(P\).
If we now have one candidate for \(S\) after the observation above, we can try greedily constructing what should be \(P\) and \(Q\) to see if they match.
posted:
last update: