## Editorial for DMOPC '17 Contest 2 P2 - Balance

**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:

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

**Time Complexity:**

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 , and `No`

otherwise. Proof of correctness is left as an exercise to the reader.

**Time Complexity:**

## Comments

FWIW, according to the statement

`(())(())`

is not balanced.Nice catch, that was entirely our mistake.