CF Round 1082 (Div. 1)

You can find my code for this contest here.

C. Rigged Bracket Sequence

This observation is not necessary but definitely makes the DP much easier to think about: the “shift right” observation is equivalent to swapping the final bracket to the front. This is nice because when we swap brackets and , only the balance between is affected. Moreover, the balance cannot decrease unless and are ( and ) respectively. Therefore, we can let dp[i] denote the number of ways to swap to the left some number of times, assuming is currently ). This results in a concise solution:

void ac() {
    int n; cin >> n;
    string s; cin >> s;
    vector<int> ways(n);
    int tot = 0;
    for (
	    int i = 0, p2 = 1, bal = 0, sum_l = 0, sum_r = 0; i < n; 
	    i++, p2 = p2 * 2 % M
    ) {
        ways[i] = (1 + sum_l + sum_r) % M;
        if (s[i] == '(') {
            ad(tot, p2);
            ad(sum_l, ways[i]);
        }
        if (s[i] == ')') {
            ad(sum_r, ways[i]);
            ad(tot, ways[i]);
        }
        bal += (s[i] == '(' ? 1 : -1);
        if (bal < 2) sum_l = 0;
    }
    cout << tot << "\n";
}

D. Binary Not Search and Queries

A clear lower bound on the answer is the maximum gap between any two equal values. We will now show that this is also an upper bound. For an triple, let denote the list of values that are contained only in ‘s range, and let denote the set of values that are contained only in ‘s range. Then, the average distance between pairs of equal elements in and must be at least , which means there must exist a pair with distance .

This proof also shows that if is exactly equal to the maximum gap, must exactly equal . Therefore, for a given gap size, we need only to maintain the ranges formed by the first elements of values that have that gap. This can be done with std::set spam in like so.