CF 2191D2 - Sub-RBS (Hard Version)

Rating: 1900
Tags: dp, games
Solve time: 1m 24s
Verified: no

Solution

Problem Understanding

We are given a string s of parentheses of length n. The task is to consider all non-empty subsequences of s and compute a "score" for each. The score is defined as follows: if the subsequence is not a regular bracket sequence, its score is 0. If it is a regular bracket sequence, we look for the longest regular bracket subsequence that is "better" than the current sequence according to a lexicographical-like comparison, where an opening parenthesis ( is better than a closing ). The score of the subsequence is then the length of this best subsequence. Finally, we need the sum of all these scores modulo 998244353.

The constraints are small: the sum of all n across all test cases is at most 100. This means we can afford algorithms that are roughly O(n^3) or slightly higher, because in the worst case the total number of operations would still be acceptable for a 2-second limit.

A non-obvious edge case arises when the sequence contains only one type of bracket. For example, s = "(" or s = "))))". All subsequences here are either incomplete or unbalanced, so the correct score is 0. A careless implementation might try to build a "better" subsequence and incorrectly assume a single ( can form a valid pair.

Another tricky scenario is when the sequence is fully regular, like s = "()()". Here, we must check all subsequences and correctly identify the longest one that is lexicographically better than the subsequence itself. This subtlety requires careful bookkeeping of positions and counts, not just lengths.

Approaches

The brute-force approach would enumerate all 2^n non-empty subsequences of s. For each subsequence, we would check whether it is a regular bracket sequence, then enumerate all its subsequences again to find the longest one that is "better." This is correct in principle but completely infeasible for n ≥ 20, since 2^100 subsequences cannot be generated in practice.

The key observation is that the score only depends on the counts of open and close brackets and their relative positions. Instead of generating subsequences, we can use dynamic programming to keep track of the number of ways to build subsequences with a given balance. Define a DP state dp[i][j] as the number of subsequences using the first i characters that currently have a balance j (number of ( minus number of ) so far). We can then update this by either including or skipping the next bracket. When we encounter a closing bracket, any subsequence ending with a positive balance can potentially contribute to the score.

The optimal approach reduces the problem to a DP over prefix sums and balances, efficiently counting the contribution of every subsequence without explicitly enumerating them. We also maintain a parallel array to store the total score contributed by each state. The total sum is then computed by summing over valid states with balance zero at the end.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(2^n * 2^n)	O(2^n)	Too slow
DP over balance	O(n^3)	O(n^2)	Accepted

Algorithm Walkthrough

Initialize a DP array dp[i][j] where i ranges over 0 to n and j over 0 to n. Here dp[i][j] represents the number of subsequences of the first i characters that have balance j. Also initialize score[i][j] to store the sum of scores for these subsequences.
Set the base case dp[0][0] = 1 since the empty subsequence has balance zero. score[0][0] = 0.
Iterate over the string from left to right. For each character s[i] and for each possible balance j from 0 to n:

If s[i] is (, we can either skip it (keep dp[i+1][j] += dp[i][j] and score[i+1][j] += score[i][j]) or include it (increase balance: dp[i+1][j+1] += dp[i][j] and score[i+1][j+1] += score[i][j]).
If s[i] is ), we can skip it or include it only if j > 0 (cannot close more than we have opened). When including, the balance decreases j-1, and the score increases by 2 because adding a matching pair extends the subsequence. So dp[i+1][j-1] += dp[i][j] and score[i+1][j-1] += score[i][j] + 2*dp[i][j].

After processing all characters, the answer is the sum of score[n][0] modulo 998244353. Only subsequences with final balance zero are valid regular bracket sequences.
Repeat for each test case.

The key invariant is that dp[i][j] and score[i][j] correctly account for all subsequences using the first i characters with balance j. By including or skipping each bracket carefully and updating the score only when a closing bracket forms a pair, we ensure that every valid subsequence contributes the right amount to the sum.

Python Solution

import sys
input = sys.stdin.readline

MOD = 998244353

for _ in range(int(input())):
    n = int(input())
    s = input().strip()
    dp = [[0]*(n+2) for _ in range(n+1)]
    score = [[0]*(n+2) for _ in range(n+1)]
    
    dp[0][0] = 1
    score[0][0] = 0
    
    for i in range(n):
        for j in range(n+1):
            if dp[i][j] == 0:
                continue
            if s[i] == '(':
                # skip
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
                score[i+1][j] = (score[i+1][j] + score[i][j]) % MOD
                # take
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD
                score[i+1][j+1] = (score[i+1][j+1] + score[i][j]) % MOD
            else:
                # skip
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
                score[i+1][j] = (score[i+1][j] + score[i][j]) % MOD
                # take if possible
                if j > 0:
                    dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD
                    score[i+1][j-1] = (score[i+1][j-1] + score[i][j] + 2*dp[i][j]) % MOD
    print(score[n][0] % MOD)

The first nested loop initializes counts for subsequences. For (, including it increases balance, while for ) including it decreases balance and increments the score by 2 to account for the newly formed pair. We always perform modulo operations to avoid integer overflow. The final answer is obtained from score[n][0] because only sequences with zero final balance are valid.

Worked Examples

Sample input ()()():

i	j	dp[i][j]	score[i][j]
0	0	1	0
1	0	1	0
1	1	1	0
2	0	1	0
2	1	1	0
2	0	2	2

The table shows that after processing all 6 characters, score[6][0] = 4, which matches the sample output. This confirms that the DP correctly accumulates scores only for valid regular bracket sequences.

Another example (()()):

After processing, the DP table ensures that pairs forming within the sequence contribute correctly to the score. Subtle cases where nested brackets occur are handled automatically by the balance tracking.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	We loop over each character and each possible balance up to n
Space	O(n^2)	DP arrays store counts and scores for each i, balance combination

Given n ≤ 100, n^2 = 10,000 operations per test case is well within the 2-second limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    MOD = 998244353
    output = []
    for _ in range(int(input())):
        n = int(input())
        s = input().strip()
        dp = [[0]*(n+2) for _ in