DMOPC '17 Contest 2 P2 - Balance - Olympiads Online Judge

DMOPC '17 Contest 2 P2 - Balance

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 $A$ ~A~ and $B$ ~B~ are balanced
(A), where $A$ ~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$ ~S~, the sequence which represents the Force.

Output Specification

YES if it can be balanced, and NO otherwise.

Constraints

For all subtasks:

$S$ ~S~ will have an even number of characters.

Subtask 1 [20%]

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

Subtask 2 [80%]

$2 \le |S| \le 10^5$ ~2 \le |S| \le 10^5~

Sample Input

()()((()

Sample Output

YES

Comments

4

Kirito commented on Nov. 18, 2017, 3:37 a.m. ← edited →

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 Discord before the next contest, and we will cancel your rating change from this contest.