DMOPC '17 Contest 2 P2 - Balance

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 3.0s
Memory limit: 256M

Problem type

You were the Chosen One! You were supposed to destroy the Sith, not join them. You were supposed to bring balance to the Force, not leave it in darkness.

The Force, represented by the characters ( and ) is now unbalanced! The Force is balanced if it is one of the following:

  • ()
  • AB, where A and B are balanced
  • (A), where A is balanced

Kenobi can invert (i.e. turn a ( character to ), or vice versa) at most 1 character in the Force. Given the sequence which represents the Force, print YES if Kenobi can balance it, and NO otherwise.

Input Specification

The input will contain a single string, S, the sequence which represents the Force.

Output Specification

YES if it can be balanced, and NO otherwise.


For all subtasks, S will have an even number of characters

Subtask 1 [20%]

2 \le |S| \le 1\,000

Subtask 2 [80%]

2 \le |S| \le 10^5

Sample Input


Sample Output



  • 0
    Kirito  commented on Nov. 17, 2017, 10:37 p.m.

    As pointed out by mmaxio, the original problem statement had an error, which has now been corrected post-contest. Should anyone feel that they were seriously affected by this mistake, then please contact us on Slack before the next contest, and we will cancel your rating change from this contest.