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\% 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)


Comments


  • 8
    mmaxio  commented on Nov. 15, 2017, 2:00 p.m.

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


    • 4
      r3mark  commented on Nov. 15, 2017, 2:52 p.m. edit 3

      Nice catch, that was entirely our mistake.