Bracket Coloring (Codeforces 1837D)
Tags: Greedy, constructive algorithms

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:  the bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");  the bracket sequences ")(", "(" and ")" are not. A bracket sequence is called beautiful if one of the following conditions is satisfied:  it is a regular bracket sequence;  if the order of the characters in this sequence is reversed, it becomes a regular bracket sequence. For example, the bracket sequences "()()", "(())", ")))(((", "))()((" are beautiful.You are given a bracket sequence $$$s$$$. You have to color it in such a way that:  every bracket is colored into one color;  for every color, there is at least one bracket colored into that color;  for every color, if you write down the sequence of brackets having that color in the order they appear, you will get a beautiful bracket sequence. Color the given bracket sequence $$$s$$$ into the minimum number of colors according to these constraints, or report that it is impossible.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of characters in $$$s$$$. The second line contains $$$s$$$ — a string of $$$n$$$ characters, where each character is either "(" or ")".Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print the answer as follows:  if it is impossible to color the brackets according to the problem statement, print $$$-1$$$;  otherwise, print two lines. In the first line, print one integer $$$k$$$ ($$$1 \le k \le n$$$) — the minimum number of colors. In the second line, print $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le k$$$), where $$$c_i$$$ is the color of the $$$i$$$-th bracket. If there are multiple answers, print any of them. 


Sample Inputs:
4
8
((())))(
4
(())
4
))((
3
(()

Sample Outputs:
2
2 2 2 1 2 2 2 1
1
1 1 1 1
1
1 1 1 1
-1

Solution (Python):
def sc(a, c, ans):
    sc1 = 0
    sc2 = 0
    for i in a:
        if i == sc_type1:
            sc1 += 1
        if i == sc_type2:
            sc2 += 1
        if sc2 > sc1 or (sc2 == sc1 and i == sc_type1):
            if c == '1':
                c = '2'
            ans += '2 '
        else:
            ans += '1 '
    if sc1 == sc2:
        return (ans, c)
    else:
        return (False, False)
t = int(input())
for _ in range(t):
    n = int(input())
    a = input()
    if a[0] == '(':
        sc_type1 = '('
        sc_type2 = ')'
    else:
        sc_type1 = ')'
        sc_type2 = '('
    c = '1'
    ans = ''
    if n % 2 == 1:
        print(-1)
    else:
        (ans, c) = sc(a, c, ans)
        if ans and c:
            print(c)
            print(ans)
        else:
            print(-1)

Solution (Python):
import sys, bisect, heapq
from collections import defaultdict, deque
readline = sys.stdin.readline
read = lambda : [int(x) for x in readline().split()]
alloc = lambda *s, dfv: len(s) != 1 and [alloc(*s[1:], dfv=dfv) for _ in range(int(s[0]))] or [dfv] * int(s[0])
bet = lambda a, b: a <= b and range(a, b + 1) or range(a, b - 1, -1)
show = lambda arr: print(' '.join(map(str, arr)))
INF = 1061109567
MOD = 10 ** 9 + 7
if __name__ == '__main__':
    for ____ in range(int(input())):
        (n,) = read()
        s = readline().split()[0]
        if n % 2 != 0:
            print(-1)
            continue
        (res, k) = ([1] * n, 0)
        for i in range(n):
            if s[i] == '(':
                if k < 0:
                    res[i] = 2
                k += 1
            else:
                if k <= 0:
                    res[i] = 2
                k -= 1
        if k != 0:
            print(-1)
            continue
        cnt = res.count(1)
        print(1) if cnt == n or cnt == 0 else print(2)
        if cnt == 0:
            res = [1] * n
        show(res)

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

def solve(inp):
    s = ''
    for l in range(1, len(inp) - 1, 2):
        string = inp[l + 1][:-1]
        cnt = 0
        colors = []
        for i in string:
            if cnt > 0:
                colors.append(2)
            elif cnt < 0:
                colors.append(1)
            elif i == '(':
                colors.append(2)
            elif i == ')':
                colors.append(1)
            if i == '(':
                cnt += 1
            elif i == ')':
                cnt -= 1
        if cnt != 0:
            print(-1)
        elif len(set(colors)) == 1:
            print(1)
            print(' '.join((str(i) for i in [1] * len(string))))
        else:
            print(2)
            print(' '.join((str(i) for i in colors)))
if __name__ == '__main__':
    inp = input()
    ans = solve(inp)