Editorial for DMOPC '17 Contest 2 P2 - Balance

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.

Author: Kirito

For $20\%$ ~20\%~ of points, it is possible to try inverting each parenthesis and then checking if the sequence is balanced with a stack.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

For full points, we can loop through the sequence. Using a deque, we can pop the back of the deque if it forms a pair with the character currently in consideration, otherwise, we can push it into the back of the deque. If the deque is empty, then the sequence is balanced. If the deque is not empty, we can check if both the front and the back of the deque form a matching sequence, and pop them both if this is true. Otherwise, check if the front and back can be inverted to form a balanced sequence, and if so, print Yes if the deque is of size $2$ ~2~, and No otherwise. Proof of correctness is left as an exercise to the reader.

Time Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Comments

8

mmaxio commented on Nov. 15, 2017, 7:00 p.m.

FWIW, according to the statement (())(()) is not balanced.

4

r3mark commented on Nov. 15, 2017, 7:52 p.m. ← edit 3 →

Nice catch, that was entirely our mistake.