Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. The concatenation of A and B in this order, for some non-empty bracket sequences A and B /  Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Submission attempts (in order):
import sys
import heapq

def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0) 

n = int(input())
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1] 
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')': 
            cnt += 1
            # print('+cnt:{}'.format(cnt))
            M = max(M,cnt) 
            # print('M:{}'.format(M))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
    cnt = 0
    for t in s[::-1]: 
        if t == ')':
            cnt += 1
            # print('+cnt:{}'.format(cnt))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
            m = min(m,cnt) 
            # print('m:{}'.format(m))
    if cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

import sys
import heapq

def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0) 

n = int(input())
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1] 
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')': 
            cnt += 1
            print('+cnt:{}'.format(cnt))
            M = max(M,cnt) 
            print('M:{}'.format(M))
        else:
            cnt -= 1
            print('-cnt:{}'.format(cnt))
    cnt = 0
    for t in s[::-1]: 
        if t == ')':
            cnt += 1
            print('+cnt:{}'.format(cnt))
        else:
            cnt -= 1
            print('-cnt:{}'.format(cnt))
            m = min(m,cnt) 
            print('m:{}'.format(m))
    # if cnt > 0:
    #     minus.append((-m,cnt))
    if cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)


import sys
import heapq

def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0) 

n = int(input())
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1] 
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')': 
            cnt += 1
            M = max(M,cnt) 
        else:
            cnt -= 1
    cnt = 0
    for t in s[::-1]: 
        if t == ')':
            cnt += 1
        else:
            cnt -= 1
            m = min(m,cnt) 
    if cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

import sys
import heapq

def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0) 

n = int(input())
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1] 
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')': 
            cnt += 1
            # print('+cnt:{}'.format(cnt))
            M = max(M,cnt) 
            # print('M:{}'.format(M))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
    cnt = 0
    for t in s[::-1]: 
        if t == ')':
            cnt += 1
            # print('+cnt:{}'.format(cnt))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
            m = min(m,cnt) 
            # print('m:{}'.format(m))
    if cnt > 0:
        minus.append((-m,cnt))
    elif cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

import sys

input = sys.stdin.readline

def check(s):
    h = 0
    for p in s:
        b = h + p[0]
        if b < 0: return False
        h += p[1]
    return True

N = int(input())
S = [input().strip() for i in range(N)]

total = 0
ps, ms = [], []
for s in S:
    h, b = 0, 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
        b = min(b, h)
    if h > 0:
        ps.append([b, h])
    else:
        ms.append([b-h, -h])
    total += h

ps.sort(reverse=True)
ms.sort(reverse=True)
if check(ps) and check(ms) and total == 0:
    print('Yes')
else:
    print('No')

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted