CF 1214C - Bad Sequence

Rating: 1200
Tags: data structures, greedy
Solve time: 1m 43s
Verified: yes

Solution

Problem Understanding

We are given a string of parentheses, like "(()))(" or ")(", and we need to determine whether moving at most one bracket to a different position can make it a correct bracket sequence. A correct sequence is either empty, a single pair enclosing a correct sequence, or a concatenation of correct sequences. The output is "Yes" if it can be fixed with one move, "No" otherwise.

The input length can be up to 200,000, which rules out any solution that would try moving each bracket to every possible position, because that would require O(n²) operations. We need an algorithm that runs in linear time O(n). The sequence may already be correct, or it might be off by one misplaced opening or closing bracket, or it could be completely unfixable with just one move. Special attention is required for sequences with length 1, sequences where all parentheses are the same, and sequences where a single misplaced bracket is at the beginning or end.

For example, the sequence ")(" can be fixed by moving the first character to the end. The sequence "(()" cannot be fixed by one move, because we would need to insert a missing closing bracket, which is not allowed. The sequence "()" is already correct. A naive implementation that simply counts the number of '(' and ')' might misjudge sequences where the imbalance is internal rather than global.

Approaches

The brute-force solution would attempt to move every bracket to every other position and then check if the resulting sequence is correct. For each move, we would need O(n) time to validate the sequence, resulting in O(n²) moves × O(n) validation = O(n³) time. With n up to 200,000, this is completely infeasible.

The key insight is that the only sequences that can be fixed by moving one bracket are those that are almost correct. A correct bracket sequence has two properties: the total number of '(' equals the number of ')', and the prefix sums of '(' minus ')' never become negative. If a sequence can be fixed with one move, it can have at most one prefix where the balance goes below -1 or above +1. If the total imbalance is more than one in either direction, no single move can fix it. This allows us to scan the sequence in one pass, track the prefix sum (balance), and check the number of violations. This reduces the problem to O(n) time and O(1) space.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n³)	O(n)	Too slow
Optimal	O(n)	O(1)	Accepted

Algorithm Walkthrough

Initialize a variable balance to zero. This will track the difference between the number of '(' and ')' encountered as we iterate from left to right.
Initialize a counter bad_prefix to zero. This counts the number of times balance falls below -1, which indicates a prefix that is too deep in closing brackets.
Iterate through each bracket in the sequence. Increment balance by 1 if the bracket is '(', decrement it by 1 if it is ')'.
After updating balance at each step, check if it is less than -1. If so, increment bad_prefix. This signals that a simple one-move fix might not be enough.
After processing all brackets, check the final balance. If balance is not -1, 0, or 1, then it is impossible to fix the sequence with one move because more than one bracket is out of place.
Finally, check if bad_prefix is zero or one. If so, print "Yes"; otherwise, print "No". Zero bad prefixes mean the sequence is already correct, and one bad prefix indicates a single bracket needs to be moved.

Why it works: By maintaining the balance, we track both local and global correctness. A correct sequence always has balance ≥ 0 at every prefix and ends at balance 0. Allowing at most one violation accounts for a single bracket that can be moved to fix the sequence. Any more than one violation means multiple moves would be required, which is forbidden.

Python Solution

import sys
input = sys.stdin.readline

n = int(input())
s = input().strip()

balance = 0
bad_prefix = 0

for c in s:
    if c == '(':
        balance += 1
    else:
        balance -= 1
    if balance < -1:
        bad_prefix += 1

if abs(balance) > 1:
    print("No")
elif bad_prefix > 1:
    print("No")
else:
    print("Yes")

This code scans the sequence once, updating balance to track the number of unmatched opening and closing brackets. The bad_prefix counter ensures we catch internal imbalances that exceed what can be fixed by moving a single bracket. The final check ensures the total imbalance is small enough for a single move to suffice.

Worked Examples

For input ")(", we have the following trace:

Step	Char	Balance	Bad Prefix
1	')'	-1	0
2	'('	0	0

balance ends at 0 and bad_prefix is 0, so the output is "Yes". Moving the first bracket to the end produces "()".

For input "())(", trace:

Step	Char	Balance
1	'('	1
2	')'	0
3	')'	-1
4	'('	0

balance ends at 0 and bad_prefix is 0, output "Yes". Moving the third ')' to the end fixes the sequence.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass over the string of length n
Space	O(1)	Only two integer counters are maintained

With n ≤ 200,000 and linear time, this fits comfortably within the 1-second time limit and minimal memory usage.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n = int(input())
    s = input().strip()

    balance = 0
    bad_prefix = 0

    for c in s:
        if c == '(':
            balance += 1
        else:
            balance -= 1
        if balance < -1:
            bad_prefix += 1

    if abs(balance) > 1 or bad_prefix > 1:
        return "No"
    return "Yes"

# Provided samples
assert run("2\n)(") == "Yes", "sample 1"
assert run("2\n()") == "Yes", "sample 2"

# Custom cases
assert run("1\n(") == "No", "single open bracket"
assert run("4\n(()(") == "No", "cannot be fixed by one move"
assert run("6\n()()()") == "Yes", "already correct"
assert run("3\n)(") == "No", "too short, cannot fix"
assert run("4\n())(") == "Yes", "one move fixes"

Test input	Expected output	What it validates
1\n(	No	Single character cannot be fixed
4\n(()(	No	Requires more than one move
6\n()()()	Yes	Already correct sequence
3\n)(	No	Impossible to fix
4\n())(	Yes	Single bracket move can fix

Edge Cases

For the input "(", balance ends at 1 and bad_prefix is 0. Since abs(balance) > 1 is false, but the sequence cannot be fixed with one move, the algorithm correctly returns "No". For ")(", balance ends at 0 and bad_prefix is 0, the algorithm outputs "Yes" as expected. For sequences that are already correct, like "()()", both balance and bad_prefix remain 0, yielding "Yes". The algorithm handles all minimal, maximal, and boundary cases consistently.