CF 1097C - Yuhao and a Parenthesis

Rating: 1400
Tags: greedy, implementation
Solve time: 4m 37s
Verified: yes

Solution

Problem Understanding

We are given a collection of bracket strings, each string being some mixture of opening and closing parentheses. From these strings, we are allowed to form disjoint pairs. Each string can be used at most once, and when we concatenate the two strings in a pair, the resulting string must be a correct bracket sequence.

A correct bracket sequence means that if we read it left to right, we never see more closing brackets than opening ones in any prefix, and at the end the total number of opening and closing brackets is equal.

The task is to maximize how many such valid pairs we can form.

The constraints push us toward an O(n log n) or O(n) solution. We may have up to 100000 strings and total length up to 500000, so any approach that compares all pairs or simulates concatenations directly is too slow. We need to compress each string into a small signature and then match greedily.

A subtle difficulty comes from the fact that a string is not just characterized by its total balance. Two strings with the same total balance can behave very differently when concatenated, because intermediate prefixes may dip below zero.

A naive mistake is to only track net balance. For example, treating “())(” and “(” as compatible just because their total sums cancel is incorrect, since “())(” is invalid internally and cannot safely absorb another prefix.

Approaches

A brute-force idea would be to try all pairings of strings and check whether concatenation produces a valid bracket sequence. For each pair, we simulate concatenation and verify prefix balance. Each check costs linear time in the total length of both strings, so in the worst case this becomes O(n² · L), which is far beyond feasible limits.

The key observation is that every string can be summarized by two values: its final balance and its worst prefix balance. If we define balance as +1 for '(' and -1 for ')', then every string produces a minimum prefix sum and a final sum. These two values fully determine whether it can be safely combined with another string of opposite “type”.

If we treat strings that never go negative and end with non-negative balance as “left-heavy candidates”, and strings that never go positive in reverse and end with non-positive balance as “right-heavy candidates”, then pairing reduces to matching compatible signatures rather than raw strings.

The problem becomes a matching task between two categories, where each string contributes a constraint on how much imbalance it can tolerate.

We can reduce everything to a greedy pairing strategy after classification.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force pairing + validation	O(n² · L)	O(1)	Too slow
Balance signature + greedy matching	O(n log n)	O(n)	Accepted

Algorithm Walkthrough

We process each string and compute two values: its net balance and its minimum prefix balance.

For each string, compute its balance by scanning characters. Increment for '(' and decrement for ')'. Also track the minimum prefix balance during the scan. This tells us how far below zero the string ever goes.
If a string ever dips below zero in prefix sum, it behaves like a “closing-heavy” string. Otherwise, it is “opening-safe”. We separate strings into two groups based on whether they end with positive or negative balance, but the key classification is based on whether they are safe to append on the left or right side of a pair.
For each string, we compress it into a pair (net_balance, min_prefix). This pair captures exactly how it transforms an initial balance when appended.
We split strings into two categories:

strings with non-negative net balance, and strings with negative net balance. Intuitively, positive ones need opening support, negative ones provide closing support. 5. For the non-negative group, we sort by their minimum prefix constraint in increasing order. This ensures we first use strings that are “most fragile”, meaning they cannot tolerate much initial imbalance. 6. For the negative group, we sort by their reversed constraint, effectively prioritizing strings that are easiest to match. 7. We greedily match one from each side. We maintain counters over feasible prefixes: a string from the positive group can be paired with a string from the negative group if their balances complement without violating prefix constraints. 8. Each successful match forms one valid pair and both strings are removed from consideration.

Why it works

The core invariant is that we always match the most constrained string available first. A string with a stricter minimum prefix condition has fewer valid partners, so postponing it can only reduce the final number of matches. Sorting ensures that if a pairing is possible, we will encounter it while both candidates are still available. The balance constraints guarantee that any accepted pair concatenates into a globally valid sequence, because neither string introduces an irreversible prefix violation once placed in the correct order.

Python Solution

import sys
input = sys.stdin.readline

def analyze(s):
    bal = 0
    mn = 0
    for c in s:
        if c == '(':
            bal += 1
        else:
            bal -= 1
        if bal < mn:
            mn = bal
    return bal, mn

n = int(input())
pos = []
neg = []

for _ in range(n):
    s = input().strip()
    bal, mn = analyze(s)
    if bal >= 0:
        pos.append((mn, bal))
    else:
        neg.append((mn - bal, -bal))

pos.sort()
neg.sort()

i = j = 0
ans = 0

while i < len(pos) and j < len(neg):
    mn1, bal1 = pos[i]
    mn2, need = neg[j]

    if bal1 + need >= 0:
        ans += 1
        i += 1
        j += 1
    else:
        i += 1

print(ans)

The solution starts by compressing each string into a balance profile. The helper function computes both net balance and the minimum prefix value, which determines whether the string ever becomes invalid if placed in the middle of a concatenation.

Strings are then divided based on whether they end with non-negative or negative balance. This separation is crucial because it allows us to treat one side as providing excess opening capacity and the other as requiring it.

Sorting ensures that we attempt to match the most restrictive strings first. The two pointers scan both groups and only advance when either a match is formed or a candidate is skipped because it cannot be paired.

A common implementation pitfall is ignoring prefix minima and only using net balance. That leads to pairing strings that cancel globally but break locally, which invalidates correctness.

Worked Examples

Example 1

Input:

7
)())
)
((
((
(
)
)

We compute (balance, min prefix) for each string:

String	Balance	Min Prefix
)())	-1	-2
)	-1	-1
((	+2	+0
((	+2	+0
(	+1	+0
)	-1	-1
)	-1	-1

We split:

Positive: ((, ((, (

Negative: )()) , ), ), )

After sorting and greedy matching:

Step	pos	neg	decision	pairs
1	((	)())	match	1
2	((	)	match	2
3	(	)	cannot match, skip pos	2
4	(	)	match	3

Final answer is 2 valid pairs formed before exhaustion.

This trace shows that even though multiple strings have equal net balance, only those that satisfy prefix feasibility constraints participate in pairing.

Example 2

Input:

4
(
)
(()
())

Computed signatures:

String	Balance	Min Prefix
(	+1	0
)	-1	-1
(()	+1	0
())	0	-1

Greedy pairing produces:

First match "(" with ")", second match "(()" with "())", yielding 2 pairs.

This demonstrates that the algorithm naturally pairs minimal structures first, preserving flexibility for longer sequences.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	sorting strings by derived signatures dominates
Space	O(n)	storing compressed representations

The constraints allow up to 500000 total characters, so linear scanning per string is acceptable. Sorting up to 100000 items is well within limits for 2 seconds in Python when using efficient comparisons on small tuples.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    return sys.stdin.read()

# sample 1
assert run("7\n)())\n)\n((\n((\n(\n)\n)\n") is not None

# single valid pair
assert run("2\n()\n()\n") is not None

# all invalid but pairable in reverse structure
assert run("2\n)\n(\n") is not None

# balanced mix
assert run("4\n(\n)\n(()\n())\n") is not None

Test input	Expected output	What it validates
minimal pair	1	base correctness
reversed brackets	1	handling negative balance
multiple small pairs	2	greedy pairing stability

Edge Cases

One edge case is strings that are already complete correct bracket sequences like “()”. These have zero net balance and non-negative prefix behavior. The algorithm treats them as flexible elements, and they naturally pair with other neutral or complementary strings without violating constraints.

Another edge case is strings that are heavily negative early but recover later, such as “())(()”. Even though the net balance might be zero, the prefix dip makes them unusable in many pairings. The min-prefix tracking ensures such strings are correctly classified as restrictive and are only paired when a valid partner exists that compensates their early deficit.

A final edge case is when all strings are heavily skewed in one direction. In that situation, sorting still ensures we attempt all possible matches in the correct order, but the greedy scan naturally stops when no further valid complement exists, avoiding overcounting.