Changing Brackets (Codeforces 1593G)
Tags: Greedy, data structures

A sequence of round and square brackets is given. You can change the sequence by performing the following operations:  change the direction of a bracket from opening to closing and vice versa without changing the form of the bracket: i.e. you can change '(' to ')' and ')' to '('; you can change '[' to ']' and ']' to '['. The operation costs $$$0$$$ burles. change any square bracket to round bracket having the same direction: i.e. you can change '[' to '(' but not from '(' to '['; similarly, you can change ']' to ')' but not from ')' to ']'. The operation costs $$$1$$$ burle. The operations can be performed in any order any number of times.You are given a string $$$s$$$ of the length $$$n$$$ and $$$q$$$ queries of the type "l r" where $$$1 \le l < r \le n$$$. For every substring $$$s[l \dots r]$$$, find the minimum cost to pay to make it a correct bracket sequence. It is guaranteed that the substring $$$s[l \dots r]$$$ has an even length.The queries must be processed independently, i.e. the changes made in the string for the answer to a question $$$i$$$ don't affect the queries $$$j$$$ ($$$j > i$$$). In other words, for every query, the substring $$$s[l \dots r]$$$ is given from the initially given string $$$s$$$.A correct bracket sequence is a sequence that can be built according the following rules:  an empty sequence is a correct bracket sequence;  if "s" is a correct bracket sequence, the sequences "(s)" and "[s]" are correct bracket sequences.  if "s" and "t" are correct bracket sequences, the sequence "st" (the concatenation of the sequences) is a correct bracket sequence. E.g. the sequences "", "(()[])", "[()()]()" and "(())()" are correct bracket sequences whereas "(", "[(])" and ")))" are not.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.For each test case, the first line contains a non-empty string $$$s$$$ containing only round ('(', ')') and square ('[', ']') brackets. The length of the string doesn't exceed $$$10^6$$$. The string contains at least $$$2$$$ characters.The second line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.Then $$$q$$$ lines follow, each of them contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$ where $$$n$$$ is the length of $$$s$$$). It is guaranteed that the substring $$$s[l \dots r]$$$ has even length.It is guaranteed that the sum of the lengths of all strings given in all test cases doesn't exceed $$$10^6$$$. The sum of all $$$q$$$ given in all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case output in a separate line for each query one integer $$$x$$$ ($$$x \ge 0$$$) — the minimum cost to pay to make the given substring a correct bracket sequence.

Note: Consider the first test case. The first query describes the whole given string, the string can be turned into the following correct bracket sequence: "([()])()[[]]". The forms of the brackets aren't changed so the cost of changing is $$$0$$$.The second query describes the substring ")[)()]". It may be turned into "(()())", the cost is equal to $$$2$$$.The third query describes the substring "))[)". It may be turned into "()()", the cost is equal to $$$1$$$.The substrings of the second test case contain only round brackets. It's possible to prove that any sequence of round brackets having an even length may be turned into a correct bracket sequence for the cost of $$$0$$$ burles.In the third test case, the single query describes the string "[]" that is already a correct bracket sequence.

Sample Inputs:
3
([))[)()][]]
3
1 12
4 9
3 6
))))))
2
2 3
1 4
[]
1
1 2

Sample Outputs:
0
2
1
0
0
0

Solution (Python):
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def prep_brackets(s):
    count_even = 0
    count_odd = 0
    cumulative_even = [None] * (len(s) + 1)
    cumulative_odd = [None] * (len(s) + 1)
    cumulative_even[0] = 0
    cumulative_odd[0] = 0
    for i in range(len(s)):
        if s[i] in '[]':
            r = i % 2
            if r == 0:
                count_even += 1
            else:
                count_odd += 1
        cumulative_even[i + 1] = count_even
        cumulative_odd[i + 1] = count_odd
    return (cumulative_even, cumulative_odd)

def estimate_cost(l, r, cumulative_even, cumulative_odd):
    even_count = cumulative_even[r] - cumulative_even[l - 1]
    odd_count = cumulative_odd[r] - cumulative_odd[l - 1]
    cost = abs(even_count - odd_count)
    sys.stdout.write(f'{cost}\n')
for _ in range(int(input())):
    s = input().decode()
    (cumulative_even, cumulative_odd) = prep_brackets(s)
    for _ in range(int(input())):
        (l, r) = map(int, input().decode().split(' '))
        estimate_cost(l, r, cumulative_even, cumulative_odd)

Solution (Python):
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def prep_brackets(s):
    count_even = 0
    count_odd = 0
    cumulative_even = [None] * (len(s) + 1)
    cumulative_odd = [None] * (len(s) + 1)
    cumulative_even[0] = 0
    cumulative_odd[0] = 0
    open_br = ord('[')
    close_br = ord(']')
    for i in range(len(s)):
        if s[i] == open_br or s[i] == close_br:
            r = i % 2
            if r == 0:
                count_even += 1
            else:
                count_odd += 1
        cumulative_even[i + 1] = count_even
        cumulative_odd[i + 1] = count_odd
    return (cumulative_even, cumulative_odd)

def estimate_cost(l, r, cumulative_even, cumulative_odd):
    even_count = cumulative_even[r] - cumulative_even[l - 1]
    odd_count = cumulative_odd[r] - cumulative_odd[l - 1]
    cost = abs(even_count - odd_count)
    sys.stdout.write(f'{cost}\n')
for _ in range(int(input())):
    s = input()
    (cumulative_even, cumulative_odd) = prep_brackets(s)
    for _ in range(int(input())):
        (l, r) = map(int, input().decode().split(' '))
        estimate_cost(l, r, cumulative_even, cumulative_odd)

Solution (Python):
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def prep_brackets(s):
    counts = {0: 0, 1: 0}
    cumulative = {0: [None] * (len(s) + 1), 1: [None] * (len(s) + 1)}
    cumulative[0][0] = 0
    cumulative[1][0] = 0
    for i in range(len(s)):
        r = i % 2
        if s[i] in '[]':
            counts[r] += 1
        cumulative[0][i + 1] = counts[0]
        cumulative[1][i + 1] = counts[1]
    return cumulative

def estimate_cost(l, r, cumulative):
    even_count = cumulative[0][r] - cumulative[0][l - 1]
    odd_count = cumulative[1][r] - cumulative[1][l - 1]
    cost = abs(even_count - odd_count)
    sys.stdout.write(f'{cost}\n')
for _ in range(int(input())):
    s = input().decode()
    cumulative = prep_brackets(s)
    for _ in range(int(input())):
        (l, r) = map(int, input().decode().split(' '))
        estimate_cost(l, r, cumulative)