Editorial for DMOPC '17 Contest 2 P2 - Balance
Submitting an official solution before solving the problem yourself is a bannable offence.
For ~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)~
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~, and
No otherwise. Proof of correctness is left as an exercise to the reader.
Time Complexity: ~\mathcal O(N)~