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):
def count_scan(s):
    max_min = 0
    compare = 0
    for c in s:
        if c == '(':
            compare += 1
        elif c == ')':
            compare -= 1
            max_min = min(max_min, compare)
    return min(max_min, compare), compare


def key(lst):
    m, c = lst
    if c > 0:
        return 1, m
    else:
        return -1, c - m


def main():
    n = int(input())
    lst = [input() for _ in range(n)]

    txt = 'No'
    ans = 0
    for max_min, c in sorted([count_scan(s) for s in lst],
                             reverse=True,
                             key=key):
        if max_min + ans < 0:
            break
        ans += c
    else:
        if ans == 0:
            txt = 'Yes'

    print(txt)

n = int(input())
lst = [input() for _ in range(n)]

lst.sort()
d = {'(': 0, ')': 0}
txt = 'No'

for i in lst:
    # print(f"{i = }")
    for j in i:
        # print(f"{j = }")
        d[j] += 1
        if(d['('] < d[')']):
            break


if(d['('] == d[')']):
    txt = 'Yes'



n = int(input())
lst = [input() for _ in range(n)]

lst.sort()
d = {'(': 0, ')': 0}
txt = 'No'

for i in lst:
    # print(f"{i = }")
    for j in i:
        # print(f"{j = }")
        d[j] += 1
        if(d['('] < d[')']):
            break

print(txt)



up_list = []
down_list = []

for _ in range(n):
    txt = input()
    min_comp = 10 ** 6
    compare = 0
    cnt = 0
    for s in txt:
        cnt += 1
        if s == '(':
            compare += 1
        else:
            compare -= 1
            min_comp = min(min_comp, compare)
    if compare > 0:
        up_list.append([compare, min(min_comp, 0)])
    else:
        down_list.append([compare, min(min_comp, 0) - compare])


up_list.sort(key=lambda x: x[1], reverse=True)
down_list.sort(key=lambda x: x[1], reverse=False)
txt = 'No'
c = 0

for t in up_list + down_list:
    if t[1] + c < 0:
        break
    else:
        c += t[0]
else:
    if c == 0:
        txt = 'Yes'

print(txt)

n = int(input())
lst = [input() for _ in range(n)]

lst.sort()
d = {'(': 0, ')': 0}
txt = 'Yes'

for i in lst:
    # print(f"{i = }")
    for j in i:
        # print(f"{j = }")
        d[j] += 1
        if(d['('] < d[')']):
            break


if(d['('] == d[')']):
    txt = 'No'

print(txt)


import sys
input = sys.stdin.readline

# up_list = []
# down_list = []


def count_scan(s):
    max_min = 0
    compare = 0
    for c in s:
        if c == '(':
            compare += 1
        elif c == ')':
            compare -= 1
            max_min = min(max_min, compare)
    return min(max_min, compare), compare


def key(lst):
    m, c = lst
    if c > 0:
        return 1, m
    else:
        return -1, c - m


def main():
    n = int(input())
    lst = [input() for _ in range(n)]

    # up_list.sort(key=lambda x: x[1], reverse=True)
    # down_list.sort(key=lambda x: x[1], reverse=False)
    txt = 'No'
    ans = 0
    # print(lst)
    
                #  reverse=True,
                #  key=key))
    for max_min, c in sorted([count_scan(s) for s in lst],
                             reverse=True,
                             key=key):
        
        if max_min + ans < 0:
            break
        ans += c
    else:
        if ans == 0:
            txt = 'Yes'

    print(txt)


if __name__ == '__main__':
    main()

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Accepted