Bring Balance (Codeforces 1685C)
Tags: Greedy, brute force

Alina has a bracket sequence $$$s$$$ of length $$$2n$$$, consisting of $$$n$$$ opening brackets '(' and $$$n$$$ closing brackets ')'. As she likes balance, she wants to turn this bracket sequence into a balanced bracket sequence.In one operation, she can reverse any substring of $$$s$$$.What's the smallest number of operations that she needs to turn $$$s$$$ into a balanced bracket sequence? It can be shown that it's always possible in at most $$$n$$$ operations.As a reminder, a sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$)  — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).The second line of each test case contains a string $$$s$$$ of length $$$2n$$$, consisting of $$$n$$$ opening and $$$n$$$ closing brackets.The sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$.

Output: For each test case, in the first line output a single integer $$$k$$$ $$$(0 \le k \le n)$$$  — the smallest number of operations required.The $$$i$$$-th of the next $$$k$$$ lines should contain two integers $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le 2n$$$), indicating that in the $$$i$$$-th operation, Alina will reverse the substring $$$s_ls_{l+1} \ldots s_{r-1}s_r$$$. Here the numeration starts from $$$1$$$.If there are multiple sequences of operations with the smallest length which transform the sequence into a balanced one, you can output any of them.

Note: In the first test case, the string is already balanced.In the second test case, the string will be transformed as follows: ())((()))( $$$\to$$$ ()()(()))( $$$\to$$$ ()()(())(), where the last string is balanced.In the third test case, the string will be transformed to ((()))((())), which is balanced.

Sample Inputs:
3
2
(())
5
())((()))(
6
())((()))(()

Sample Outputs:
0
2
3 4
9 10
1
2 11

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
_str = str
str = lambda x=b'': x if type(x) is bytes else _str(x).encode()
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from itertools import accumulate

def main():
    t = int(input())
    while t:
        n = int(input()) * 2
        s = input()
        a = [1 if c == '(' else -1 for c in s]
        res = list()
        L = -1
        for k in range(2):
            pre_sum = list(accumulate(a))
            flag = True
            l = -1
            maxv = -1
            for i in range(n):
                if pre_sum[i] < 0:
                    flag = False
                    break
                elif pre_sum[i] >= maxv:
                    l = i
                    maxv = pre_sum[i]
            if flag:
                break
            if k == 0:
                L = -1
                maxv = -1
                for i in range(n):
                    if pre_sum[i] >= maxv:
                        L = i
                        maxv = pre_sum[i]
            r = n
            maxv = -1
            for i in range(n - 1, -1, -1):
                if pre_sum[i] < 0:
                    flag = False
                    break
                elif pre_sum[i] >= maxv:
                    r = i
                    maxv = pre_sum[i]
            a[l + 1:r + 1] = a[l + 1:r + 1][::-1]
            res.append([l + 2, r + 1])
        if len(res) <= 1:
            print(len(res))
            for item in res:
                print(*item)
        else:
            print(2)
            print(1, L + 1)
            print(L + 2, n)
        t -= 1
    return
main()

Solution (Python):
import sys
input = sys.stdin.readline
out = []
t = int(input())
for _ in range(t):
    n = int(input())
    s = input().strip()
    curr = 0
    vals = []
    neg = []
    for i in range(2 * n):
        c = s[i]
        if c == '(':
            curr += 1
        elif c == ')':
            curr -= 1
        vals.append(curr)
        if curr < 0:
            neg.append(i)
    big = max(vals)
    maxes = []
    for i in range(2 * n):
        if vals[i] == big:
            maxes.append(i)
    if len(neg) == 0:
        out.append(0)
    elif max(neg) < max(maxes):
        out.append(1)
        out.append('1 ' + str(max(maxes) + 1))
    elif min(neg) > min(maxes):
        out.append(1)
        out.append(str(min(maxes) + 2) + ' ' + str(2 * n))
    else:
        bestL = 0
        lP = -1
        for i in range(min(neg)):
            if vals[i] > bestL:
                bestL = vals[i]
                lP = i
        bestR = -1
        rP = 2 * n
        for i in range(max(neg), 2 * n):
            if vals[i] > bestR:
                bestR = vals[i]
                rP = i
        if bestL + bestR >= big:
            out.append(1)
            out.append(str(lP + 2) + ' ' + str(rP + 1))
        else:
            out.append(2)
            v = maxes[0]
            out.append('1 ' + str(v + 1))
            out.append(str(v + 2) + ' ' + str(2 * n))
print('\n'.join(map(str, out)))

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input()) * 2
    S = input().strip()
    tot = 0
    ok = True
    cum = [0]
    for s in S:
        if s == '(':
            tot += 1
        else:
            tot -= 1
            if tot < 0:
                ok = False
        cum.append(tot)
    if ok:
        print(0)
        return
    for i in range(n + 1):
        if cum[i] < 0:
            break
    ma = -1
    for j in range(i - 1, -1, -1):
        if cum[j] > ma:
            ma = cum[j]
            lind = j
    for i in range(n, -1, -1):
        if cum[i] < 0:
            break
    ma = -1
    for j in range(i + 1, n + 1):
        if cum[j] > ma:
            ma = cum[j]
            rind = j
    T = S[:lind] + S[lind:rind][::-1] + S[rind:]
    ok = True
    tot = 0
    for t in T:
        if t == '(':
            tot += 1
        else:
            tot -= 1
            if tot < 0:
                ok = False
    if ok:
        print(1)
        print(lind + 1, rind)
        return
    print(2)
    ma = 0
    tot = 0
    for i in range(n):
        if S[i] == '(':
            tot += 1
            if tot >= ma:
                ma = tot
                ind = i
        else:
            tot -= 1
    print(1, ind + 1)
    S = S[:ind + 1][::-1] + S[ind + 1:]
    ma = 0
    tot = 0
    for i in range(n - 1, -1, -1):
        if S[i] == ')':
            tot += 1
            if tot >= ma:
                ma = tot
                ind = i
        else:
            tot -= 1
    print(ind + 1, n)
for _ in range(int(input())):
    solve()