DMOPC '17 Contest 2 P2 - Balance

View as PDF

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

Author:
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 and are balanced
• (A), where 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, , the sequence which represents the Force.

Output Specification

YES if it can be balanced, and NO otherwise.

Constraints

For all subtasks, will have an even number of characters

Sample Input

()()((()

Sample Output

YES