CF 1598F - RBS

We are given several strings consisting of only "(" and ")". Each string is a bracket sequence, but not necessarily a valid or regular bracket sequence.

codeforcescompetitive-programmingbinary-searchbitmasksbrute-forcedata-structuresdp

CF 1598F - RBS

Rating: 2400
Tags: binary search, bitmasks, brute force, data structures, dp
Solve time: 2m 12s
Verified: yes

Solution

Problem Understanding

We are given several strings consisting of only "(" and ")". Each string is a bracket sequence, but not necessarily a valid or regular bracket sequence. The task is to concatenate all strings in some order to maximize the number of prefixes that are themselves regular bracket sequences (RBS). A prefix is any substring that starts at the beginning, and a regular bracket sequence is one that could be transformed into a valid arithmetic expression if you added numbers and operators. In practical terms, a string is an RBS if and only if, when reading from left to right, the cumulative balance of "(" minus ")" never goes negative and ends at zero at the end of the prefix.

The input constraints are significant. We can have up to 20 strings, which allows us to consider all permutations in a brute-force manner if needed, because 20! is astronomically large. However, the total length of all strings can reach 400,000, so we cannot perform operations proportional to the total string length for each permutation. This rules out naive brute-force concatenation.

Edge cases emerge naturally. For example, if one string is "((((", it must be paired with enough ")" later; otherwise, it will never contribute to a valid prefix. A single ")" string at the start is useless because it immediately breaks balance. Strings that are themselves valid RBS, like "()", always increase the count of valid prefixes. We need to capture these properties without explicitly generating all concatenations.

Approaches

A naive approach is to try all permutations of the strings. For each permutation, we would concatenate the strings and scan all prefixes to count which ones are valid. The brute-force would take n! × total_length, which is infeasible for n = 20, since 20! is roughly 2.43 × 10^18.

The key insight is that we do not need to know the exact concatenated string. Each string can be abstracted by two numbers: its total balance (number of "(" minus number of ")") and the minimum balance seen while scanning left to right. For instance, a string "())(" has a total balance of 0, but its minimum balance is -1 because it dips below zero at some point. Once we know these two numbers for each string, we can treat the problem as a dynamic programming over subsets: for each subset of strings, track the best possible balance and maximum count of valid prefixes. When adding a new string, we can determine how many additional valid prefixes it contributes without actually concatenating the strings.

This approach reduces the problem to a bitmask dynamic programming problem. There are 2^n subsets, and for each subset, we consider adding one of the remaining strings, resulting in a complexity proportional to n × 2^n, which is acceptable for n ≤ 20.

Approach Time Complexity Space Complexity Verdict
Brute Force O(n! × total_length) O(total_length) Too slow
Bitmask DP O(n × 2^n) O(2^n × balance_states) Accepted

Algorithm Walkthrough

  1. Precompute for each string its total_balance (number of "(" minus ")") and min_prefix_balance (the minimum cumulative balance seen in the string). These two numbers allow us to determine whether appending the string to an existing sequence will break the RBS property at any point.
  2. Initialize a dynamic programming table dp[mask], where mask is a bitmask representing a subset of strings we have already concatenated. Each entry stores a dictionary mapping current cumulative balance to the maximum number of valid prefixes achieved so far. Start with dp[0] = {0: 0}, representing zero strings used, zero balance, and zero RBS prefixes.
  3. Iterate over all masks. For each mask, consider adding a string i not yet included. Calculate the new cumulative balance if we append string i. If appending does not make any prefix invalid (cumulative balance never goes negative), increment the RBS prefix count by the number of RBS prefixes in string i. Update dp[new_mask] for the new cumulative balance if it improves the previous maximum.
  4. After processing all subsets, the answer is the maximum number of RBS prefixes across all balances in dp[(1 << n) - 1], the mask representing all strings used.

Why it works: Each step of the DP ensures that all subsets are considered, and for each subset, we only track balances that could realistically occur without breaking the RBS property. Since we only append valid strings when possible and update the prefix count optimally, the DP captures the global maximum over all permutations.

Python Solution

import sys
input = sys.stdin.readline

n = int(input())
strings = [input().strip() for _ in range(n)]

# Precompute balance info
bal = []
min_pref = []
rbs_count = []

for s in strings:
    b = 0
    min_b = 0
    count = 0
    for c in s:
        if c == '(':
            b += 1
        else:
            b -= 1
        min_b = min(min_b, b)
        if b == 0:
            count += 1
    bal.append(b)
    min_pref.append(min_b)
    rbs_count.append(count)

from collections import defaultdict

dp = [defaultdict(lambda: -1) for _ in range(1 << n)]
dp[0][0] = 0

for mask in range(1 << n):
    for i in range(n):
        if mask & (1 << i):
            continue
        new_mask = mask | (1 << i)
        for cur_balance, cur_count in dp[mask].items():
            if cur_balance + min_pref[i] >= 0:
                new_balance = cur_balance + bal[i]
                new_count = cur_count + rbs_count[i]
                dp[new_mask][new_balance] = max(dp[new_mask][new_balance], new_count)

print(max(dp[(1 << n) - 1].values()))

The code first computes each string's balance and minimum prefix balance. These are stored in arrays for fast access. The DP array dp tracks maximum RBS prefixes for each subset of strings and each achievable cumulative balance. The inner loop checks if adding a string violates the RBS property; if not, the RBS prefix count is updated. Finally, the maximum across all possible ending balances is returned.

Worked Examples

Sample 1:

2
(
)
mask cur_balance action new_balance new_count
0 0 add 0 1 0
1 1 add 1 0 1

The DP correctly identifies that adding "(" then ")" creates one valid prefix.

Sample 2:

4
()()
)(
()
(

The DP tracks subsets like adding "()()" first, then ")(", then "()", then "(". At each step, the DP only updates valid balances. After processing all subsets, the maximum count of RBS prefixes is 4.

Complexity Analysis

Measure Complexity Explanation
Time O(n × 2^n) We iterate over all subsets and consider adding each of the n strings.
Space O(2^n × n × max_balance) Each DP state stores balances, but balances cannot exceed the total sum of lengths.

Given n ≤ 20, 2^n = 1,048,576, which is feasible in 3 seconds. Memory usage fits within 512 MB even with large total lengths.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n = int(input())
    strings = [input().strip() for _ in range(n)]
    bal = []
    min_pref = []
    rbs_count = []
    for s in strings:
        b = 0
        min_b = 0
        count = 0
        for c in s:
            if c == '(':
                b += 1
            else:
                b -= 1
            min_b = min(min_b, b)
            if b == 0:
                count += 1
        bal.append(b)
        min_pref.append(min_b)
        rbs_count.append(count)
    from collections import defaultdict
    dp = [defaultdict(lambda: -1) for _ in range(1 << n)]
    dp[0][0] = 0
    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                continue
            new_mask = mask | (1 << i)
            for cur_balance, cur_count in dp[mask].items():
                if cur_balance + min_pref[i] >= 0:
                    new_balance = cur_balance + bal[i]
                    new_count = cur_count + rbs_count[i]
                    dp[new_mask][new_balance] = max(dp[new_mask][new_balance], new_count)
    return str(max(dp[(1 << n) - 1].values()))

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

# Custom cases
assert run("1\n()