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


  • 0
    stanwww  commented on Nov. 11, 2024, 3:31 a.m. ← edited

    You can also do the question with a stack but we push the ) bracket if the top of the stack is not ( . Similarly if the stack is empty or there is a stack size of 2. It can form a balanced sequence.


  • 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.