Problem:
 Score : 600 points    Problem Statement A bracket sequence is a string that is one of the following:   An empty string;  The concatenation of ( , A , and ) in this order, for some bracket sequence A ;  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?      Constraints  1 \leq N \leq 10^6  The total length of the strings S_i is at most 10^6 .  S_i is a non-empty string consisting of ( and ) .         Input Input is given from Standard Input in the following format:  N  S_1  :  S_N       Output If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes ; otherwise, print No .        Sample Input 1 2
)
(()      Sample Output 1 Yes  Concatenating (() and ) in this order forms a bracket sequence.       Sample Input 2 2
)(
()      Sample Output 2 No       Sample Input 3 4
((()))
((((((
))))))
()()()      Sample Output 3 Yes       Sample Input 4 3
(((
)
)      Sample Output 4 No

Solution (Python):

import sys
input = sys.stdin.readline

n = int(input())
increasing = []
decreasing = []
dec_special = []
for _ in range(n):
    s = input().rstrip()
    minima = 0
    fin = 0
    for ch in s:
        if ch == ")":
            fin -= 1
            if fin < minima:
                minima = fin
        else:
            fin += 1
    if fin >= 0:
        increasing.append((minima, fin))
    elif minima < fin:
        dec_special.append((minima, fin))
    else:
        decreasing.append((minima, fin))

increasing.sort(reverse=True)
decreasing.sort()
dec_special.sort()

current = 0
for minima, diff in increasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in dec_special:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in decreasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
if current != 0:
    print("No")
else:
    print("Yes")

Solution (Python):
n = int(input())
plus_bracket = []
minus_bracket = []

for _ in range(n):
  mini = 0
  cur = 0
  for bracket in input():
    if bracket == '(':
      cur += 1
    else:
      cur -= 1
    if cur < mini:
      mini = cur
  if cur > 0:
    plus_bracket.append([-mini, cur])
  else:
    minus_bracket.append([cur - mini, -cur])

success = True
cur = 0
plus_bracket.sort()
minus_bracket.sort()
for bracket in plus_bracket:
  if cur < bracket[0]:
    success = False
    break
  cur += bracket[1]
back_cur = 0
for bracket in minus_bracket:
  if back_cur < bracket[0]:
    success = False
    break
  back_cur += bracket[1]
if cur != back_cur:
  success = False

if success:
  print('Yes')
else:
  print('No')

Solution (Python):
def check(DR):
    D = 0
    for dr in DR[::-1]:
        dmin, d = dr
        if D + dmin < 0:
            return False
        D += d
    return True

def main():
    N = int(input())
    S = []
    for i in range(N):
        S.append(input())

    DR1 = []
    DR2 = []
    total = 0
    for s in S:
        d = 0    
        d_min = 0 
        
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                d_min = min(d, d_min)
        total += d
        if d > 0:
            DR1.append((d_min, d))
        else:
            DR2.append((d_min - d, -d))

    
    DR1.sort()
    DR2.sort()
    if check(DR1) and check(DR2) and sum([d[1] for d in DR1]) == sum([d[1] for d in DR2]):
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Solution (Python):

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 = []
left = []
right = []
total = 0
for i in range(N):
    last = 0
    bottom = 0
    s = input().strip()
    for c in s:
        if c == "(":
            last += 1
        else:
            last -= 1
        bottom = min(bottom, last)
    if last > 0:
        left.append((bottom, last))
    else:
        right.append((bottom-last, -last))
    total += last

left.sort(key=lambda x: -x[0])
right.sort(key=lambda x: -x[0])

if check(left) and check(right) and total == 0:
    print('Yes')
else:
    print('No')

Solution (Python):

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 = []
left = []
right = []
total = 0
for i in range(N):
    last = 0
    bottom = 0
    s = input().strip()
    for c in s:
        if c == "(":
            last += 1
        else:
            last -= 1
        bottom = min(bottom, last)
    if last > 0:
        left.append((bottom, last))
    else:
        right.append((bottom-last, -last))
    total += last

left.sort(key=lambda x: -x[0])
right.sort(key=lambda x: -x[0])

if check(left) and check(right) and total == 0:
    print('Yes')
else:
    print('No')

Solution (Python):

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 = []
left = []
right = []
total = 0
for i in range(N):
    last = 0
    bottom = 0
    s = input().strip()
    for c in s:
        if c == "(":
            last += 1
        else:
            last -= 1
        bottom = min(bottom, last)
    if last > 0:
        left.append((bottom, last))
    else:
        right.append((bottom-last, -last))
    total += last

left.sort(key=lambda x: -x[0])
right.sort(key=lambda x: -x[0])

if check(left) and check(right) and total == 0:
    print('Yes')
else:
    print('No')

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


def solve():
    N = int(input())
    brackets_gen = (readline().strip() for _ in range(N))

    grads_positive = list()
    grads_negative = list()

    total = 0
    for brackets in brackets_gen:

        elevation, bottom = 0, 0

        for bk in brackets:

            elevation += 1 if bk == '(' else -1
            bottom = min(bottom, elevation)

        if elevation >= 0:
            grads_positive.append((bottom, elevation))
        elif elevation < 0:
            grads_negative.append((bottom - elevation, -elevation))

        total += elevation

    if total != 0:
        return False

    grads_positive.sort(reverse=True)
    grads_negative.sort(reverse=True)

    def is_good(grads):
        elevation, bottom = 0, 0
        for grad in grads:
            bottom = elevation + grad[0]
            if bottom < 0:
                return False
            elevation += grad[1]

        return True

    if is_good(grads_positive) and is_good(grads_negative):
        return True
    else:
        return False


def main():
    ok = solve()
    if ok:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Solution (Python):




def solve():
    N = int(input())
    brackets_gen = (input() for _ in range(N))

    grads_positive = list()
    grads_negative = list()

    total = 0
    for brackets in brackets_gen:

        elevation, bottom = 0, 0

        for bk in brackets:

            elevation += 1 if bk == '(' else -1
            bottom = min(bottom, elevation)

        if elevation >= 0:
            grads_positive.append((bottom, elevation))
        elif elevation < 0:
            grads_negative.append((bottom - elevation, -elevation))

        total += elevation

    if total != 0:
        return False

    grads_positive.sort(reverse=True)
    grads_negative.sort(reverse=True)

    def is_good(grads):
        elevation, bottom = 0, 0
        for grad in grads:
            bottom = elevation + grad[0]
            if bottom < 0:
                return False
            elevation += grad[1]

        return True

    if is_good(grads_positive) and is_good(grads_negative):
        return True
    else:
        return False


def main():
    ok = solve()
    if ok:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

left = 0
right = 0

LMR = [0] * n
MIN_LMR = [0] * n

for i,s in enumerate(S):
    l = 0
    r = 0
    lok = True
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                lok = False
        MIN_LMR[i] = min(MIN_LMR[i], l-r)
    LMR[i] = l - r

    left += l
    right += r

if left != right:
    print("No")
    exit()


positives = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x > 0 ]
zeros     = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x == 0 ]
negatives = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x < 0]
for i in range(len(negatives)):
    
    min_lmr, lmr = negatives[i]
    min_lmr = min_lmr - lmr
    lmr = -1 * lmr
    negatives[i] = (min_lmr, lmr)

positives.sort(reverse=True)
negatives.sort(reverse=True)

h = 0
for min_lmr, lmr in positives + zeros:
    if h+min_lmr < 0:
        print("No")
        exit()
    h += lmr

h = 0
for min_lmr, lmr in negatives:
    if h+min_lmr < 0:
        print("No")
        exit()
    h += lmr

print("Yes")

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
from heapq import heappush, heappop

def input():
    return sys.stdin.readline().strip()


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

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

left = 0
right = 0

l_ok = [False] * n
r_ok = [False] * n
LMR = [0] * n
MIN_LMR = [0] * n

for i,s in enumerate(S):
    l = 0
    r = 0
    lok = True
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                lok = False
        MIN_LMR[i] = min(MIN_LMR[i], l-r)
    LMR[i] = l - r
    l = 0
    r = 0
    rok = True
    for j in range(len(s)-1, -1, -1):
        if s[j] == "(":
            l += 1
            if l > r:
                rok = False
                break
        else:
            r += 1

    left += s.count("(")
    right += s.count(")")

    l_ok[i] = lok
    r_ok[i] = rok




if left != right:
    print("No")
    exit()


positives = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x > 0 ]
zeros     = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x == 0 ]
negatives = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x < 0]
for i in range(len(negatives)):
    min_lmr, lmr = negatives[i]
    min_lmr = min_lmr - lmr
    lmr = -1 * lmr
    negatives[i] = (min_lmr, lmr)

positives.sort(reverse=True)
negatives.sort(reverse=True)

h = 0
for min_lmr, lmr in positives + zeros:
    if h+min_lmr < 0:
        print("No")
        exit()
    h += lmr

h = 0
for min_lmr, lmr in negatives:
    if h+min_lmr < 0:
        print("No")
        exit()
    h += lmr

print("Yes")

Solution (Python):
import sys
from operator import itemgetter


def _s(): return sys.stdin.readline().strip()


def _i(): return int(sys.stdin.readline().strip())


def parse(s):
    l, r = 0, 0
    for c in s:
        if c == '(':
            r += 1
        else:
            if r > 0:
                r -= 1
            else:
                l += 1
    return (l, r)


def main():
    n = _i()
    p = list(filter(lambda x: x != (0, 0), [parse(_s()) for _ in range(n)]))
    u, d = [], []
    for l, r in p:
        u.append((l, r)) if l <= r else d.append((l, r))
    u.sort(key=itemgetter(0))
    d.sort(key=itemgetter(1), reverse=True)
    r = 0
    for ll, rr in u+d:
        if ll > r:
            return 'No'
        r += (rr - ll)

    return 'Yes' if r == 0 else 'No'


if __name__ == "__main__":
    print(main())

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
from heapq import heappush, heappop

def input():
    return sys.stdin.readline().strip()


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

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

left = 0
right = 0

l_ok = [False] * n
r_ok = [False] * n
LMR = [0] * n
MIN_LMR = [0] * n

for i,s in enumerate(S):
    l = 0
    r = 0
    lok = True
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                lok = False
        MIN_LMR[i] = min(MIN_LMR[i], l-r)
    LMR[i] = l - r
    l = 0
    r = 0
    rok = True
    for j in range(len(s)-1, -1, -1):
        if s[j] == "(":
            l += 1
            if l > r:
                rok = False
                break
        else:
            r += 1

    left += s.count("(")
    right += s.count(")")

    l_ok[i] = lok
    r_ok[i] = rok




if left != right:
    print("No")
    exit()


positives = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x > 0 ]
zeros     = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x == 0 ]
negatives = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x < 0 and not r_ok[i] ]
tails     = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x < 0 and r_ok[i]]

positives.sort(reverse=True)
negatives.sort()
tails.sort()

h = 0
for min_lmr, lmr in positives + zeros:
    if h+min_lmr < 0:
        print("No")
        exit()
    h += lmr

for min_lmr, lmr in negatives + tails:
    if h+min_lmr < 0:
        print("No")
        exit()
    h += lmr

print("Yes")

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



def main():
    N = I()
    zeros = []
    incs = []
    decs = []
    s = [None] * N

    for i in range(N):
        s[i] = S()
        cur = 0
        mn = 0
        for c in s[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            mn = min(mn, cur)
        end = cur

        if end == 0:
            zeros.append((mn, end, i))
        elif end > 0:
            incs.append((mn, end, i))
            
        else:
            decs.append((mn - end, end, i))
            

    incs.sort(reverse=True)
    decs.sort()

    ans = []
    for mn, end, idx in incs:
        ans.append(s[idx])

    for mn, end, idx in zeros:
        ans.append(s[idx])

    for mn, end, idx in decs:
        ans.append(s[idx])

    now = 0
    for i in range(len(ans)):
        for c in ans[i]:
            if c == '(':
                now += 1
            else:
                now -= 1
            if now < 0:
                print("No")
                return

    print(yn[now == 0])

    
    
    
    
    
    

    
    
    
    
    

    
    
    
    
    

    


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = []
B = []
cur = 0
for i in range(N):
    S = input()
    tmp = []
    for s in S:
        if s == '(':
            tmp.append(s)
        else:
            if tmp and tmp[-1] == '(':
                tmp.pop()
            else:
                tmp.append(s)
    l = tmp.count('(')
    r = len(tmp) - l
    if r-l <= 0:
        A.append((l, r))
    else:
        B.append((l, r))
A.sort(key=itemgetter(1))
B.sort(key=itemgetter(0), reverse=1)

for l, r in A:
    cur += r
    if cur > 0:
        No()
        exit()
    cur -= l
for l, r in B:
    cur += r
    if cur > 0:
        No()
        exit()
    cur -= l
if cur == 0:
    Yes()
else:
    No()

Solution (Python):
def f_bracket_sequencing():
    N = int(input())
    Brackets = [input() for _ in range(N)]

    total = 0  
    increase, decrease = [], []
    for s in Brackets:
        
        
        height, bottom = 0, 0
        for ch in s:
            height += 1 if ch == '(' else -1
            bottom = min(bottom, height)
        if height > 0:
            increase.append((bottom, height))
        else:
            decrease.append((bottom - height, -height))
        total += height
    increase.sort(reverse=True)
    decrease.sort(reverse=True)

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

    return 'Yes' if accept(increase) and accept(decrease) and total == 0 else 'No'

print(f_bracket_sequencing())

Solution (Python):
N = int(input())
s = []
for i in range(N):
    s.append(input())
inc = []
dec = []
total = 0
for i in s:
    cn = 0
    mn = 0
    for j in i:
        if j=="(":
            cn+=1
        else:
            cn-=1
        mn = min(cn,mn)
    total += cn
    if cn>=0:
        inc.append([mn,cn])
    else:
        dec.append([mn-cn,-cn])

inc.sort(reverse=True,key=lambda x:x[0])
dec.sort(reverse=True,key=lambda x:x[0])

def check(lis):
    hi = 0
    for i in lis:
        if hi+i[0]<0:
            return False
        else:
            hi+=i[1]
    return True

if check(inc) and check(dec) and total==0:
    print("Yes")
else:
    print("No")

Solution (Python):
def to_lines(s):
    h = 0
    b = 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
        b = min([b, h])
    return (b, h)


def check(lines):
    h = 0
    for line in lines:
        if h + line[0] < 0:
            return False
        h += line[1]
    return True


def main():
    N = int(input())
    up_lines = list()
    down_lines = list()
    total = 0
    for _ in range(N):
        line = to_lines(input())
        total += line[1]
        if line[1] >= 0:
            up_lines.append(line)
        else:
            inv_line = (line[0] - line[1], -line[1])
            down_lines.append(inv_line)
    up_lines.sort(key=lambda x: x[0], reverse=True)
    down_lines.sort(key=lambda x: x[0], reverse=True)
    if total == 0 and check(up_lines) and check(down_lines):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
lp=[]
lm=[]
for i in range(n):
    s=input()
    x,y=0,0
    for j in s:
        if j=="(":
            x+=1
        else:
            x-=1
        y=min(y,x)
    if x>0:
        lp.append((y,x))
    else:
        lm.append((y-x,-x))
lp.sort()
s=0
for i,j in lp[::-1]:
    if s+i<0:
        print("No")
        exit()
    s+=j
lm.sort()
t=0
for i,j in lm[::-1]:
    if t+i<0:
        print("No")
        exit()
    t+=j
if s==t:
    print("Yes")
else:
    print("No")

Solution (Python):












def     process(tab, beginning, end):
    total = beginning
    for i in tab:
        if (i[1] > total or total + i[0] < 0):
            return ("No")
        total += i[0]
    if (total == end):
        return ("Yes")
    return ("No")

def     parsing(N):
    beginning, ending = 0,0
    clean = 0
    total = 0
    tab = []

    for i in range(N):
        s = input()
        before, after = 0, 0
        for j in s:
            if (j == '('):
                after += 1
            elif (j == ')'):
                if (after > 0):
                    after -= 1
                else:
                    before += 1
        if (before == 0 and after > 0):
            beginning += after
        elif (after == 0 and before > 0):
            ending += before
        elif (before > 0 or after > 0):
            tab.append((after - before, before, after))
        else:
            clean += 1
        total += before - after
    tab = sorted(tab)[::-1]
    return tab, total, beginning, ending, clean


N  = int(input())
tab, total, beginning, ending, clean = parsing(N)
if (total == 0 and N == 1):
    res = "Yes"
elif ((total != 0) or ((min(beginning, ending) == 0 and clean == 0) 
                 or (max(beginning, ending) == 0 and clean == 1))):
    res = "No"
else:
    res = process(tab, beginning, ending)
print(res)

Solution (Python):
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    
    

a = only_r
b = only_l

exlr.sort()








for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if a-b == 0:
    print("Yes")
else:
    print("No")

Solution (Python):
N = int(input())
from collections import deque
L = deque([])
R = deque([])

for i in range(N):
  S = input()
  l = [0]*len(S)
  if S[0]=='(':
    l[0]=1
  else:
    l[0]=-1
  for j in range(1,len(S)):
    if S[j]=='(':
      l[j] = l[j-1] + 1
    else:
      l[j] = l[j-1] - 1
  if l[-1] < 0:
    R.append([min(l)-l[-1], -l[-1], min(l), l[-1]])
  else:
    L.append([min(0,min(l)),l[-1]])
    
R = sorted(R, key = lambda x:x[0])
L = sorted(L, key = lambda x:x[0], reverse = True)
now = 0
judge = True
    
for l in L:
  if now + l[0]<0:
    judge = False
    break
  else:
    now += l[1]
    
for r in R:
  if now+r[2]<0:
    judge = False
    break
  else:
    now += r[3]
    
if now!=0:
  judge = False
  
if judge:
  print('Yes')
else:
  print('No')

Solution (Python):


def LI():
    return list(map(int, input().split()))


N = int(input())
S = [input() for _ in range(N)]


def judge(v):
    x = 0
    for b, l in v:
        if x + b < 0:
            return False
        x += l
    return True


def main():
    pl, ml = [], []
    t = 0
    for i in range(N):
        l = 0
        b = 0
        for s in S[i]:
            if s == "(":
                l += 1
            else:
                l -= 1
                b = min(b, l)
        t += l
        if l > 0:
            pl.append((b, l))
        else:
            ml.append((b - l, -l))

    pl.sort(reverse=True)
    ml.sort(reverse=True)

    if judge(pl) and judge(ml) and t == 0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    
    

a = only_r
b = only_l
exlr.sort(key=lambda x: x[1])
exlr.sort()


for i in range(len(exlr)):
    if exlr[i][1] <= a and exlr[i][0] <= 0:
        a -= exlr[i][0]
        exlr[i] = [0,0,0]

for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if a-b == 0:
    print("Yes")
else:
    print("No")

Solution (Python):
N = int(input())

S_list = []
for _ in range(N):
	S_list.append(input().strip())

data = []
for s in S_list:
	bottom = 0
	height = 0
	for c in s:
		if c == ")":
			height -= 1
			if bottom > height:
				bottom = height
		else:
			height += 1
	if height == 0:
		k1 = 1
		k2 = 0
	elif height > 0:
		k1 = 0
		k2 = -bottom
	else:
		k1 = 2
		k2 = bottom - height
	data.append((k1, k2, bottom, height, s))

data.sort()

def check():
	height = 0
	for k1, k2, b, h, s in data:

		if height + b < 0:
			return False
		height += h
	return height == 0

if check():
	print("Yes")
else:
	print("No")

Solution (Python):









def     process(tab, first, end):
    
    
    total = first
    for i in tab:
        if (i[1] > total):
            return ("No")
        total += i[0]
        if (total < 0):
            return ("No")
    if (total == end):
        return ("Yes")
    return ("No")




N  = int(input())

first = 0
last = 0
clean = 0
tab = []
total = 0
for i in range(N):
    s = input()
    avant = 0
    apres = 0
    for j in s:
        if (j == '('):
            apres += 1
        elif (j == ')'):
            if (apres > 0):
                apres -= 1
            else:
                avant += 1
    if (avant == 0 and apres > 0):
        first += apres
    elif (apres == 0 and avant > 0):
        last += avant
    elif (avant > 0 or apres > 0):
        tab.append((apres - avant, avant, apres, s))
    else:
        clean += 1
    total += avant - apres
if (first == -1 and clean > 0):
    first = 0
    clean -= 1
if (last == -1 and clean > 0):
    last = 0


tab = sorted(tab)
tab = tab[::-1]
if (total == 0 and first > -1 and last > -1):
    res = process(tab, first, last)
else:
    if (total == 0 and N == 1):
        res = "Yes"
    else:
        res = "No"
print(res)

Solution (Python):









def     process(tab, first, end):
    
    
    total = first
    for i in tab:
        if (i[1] > total):
            return ("No")
        total += i[0]
        if (total < 0):
            return ("No")
    if (total == end):
        return ("Yes")
    return ("No")




N  = int(input())

first = -1
last = -1
clean = 0
tab = []
total = 0
for i in range(N):
    s = input()
    avant = 0
    apres = 0
    for j in s:
        if (j == '('):
            apres += 1
        elif (j == ')'):
            if (apres > 0):
                apres -= 1
            else:
                avant += 1
    if (avant == 0 and apres > 0 and first == -1):
        first = apres
    elif (apres == 0 and avant > 0 and last == -1):
        last = avant
    elif (avant > 0 or apres > 0):
        tab.append((apres - avant, avant, apres, s))
    else:
        clean += 1
    total += avant - apres
if (first == -1 and clean > 0):
    first = 0
    clean -= 1
if (last == -1 and clean > 0):
    last = 0


tab = sorted(tab)
tab = tab[::-1]
if (total == 0 and first > -1 and last > -1):
    res = process(tab, first, last)
else:
    if (total == 0 and N == 1):
        res = "Yes"
    else:
        res = "No"
print(res)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = [input() for _ in range(n)]
x = [] 
y = [] 
for i in range(n):
    cnt1 = 0
    cnt2 = 0
    for j in range(len(s[i])):
        if s[i][j] == '(':
            cnt1 += 1
        else:
            cnt2 += 1
    if cnt1 - cnt2 > 0:
        x.append([cnt2, cnt1, s[i]])
    else:
        y.append([cnt1, cnt2, s[i]])
x.sort() 
y.sort(reverse=True) 
tmp = 0
que = deque()
for i, j, k in x:
    for l in k:
        if l == '(':
            tmp += 1
        else:
            if tmp > 0:
                tmp -= 1
            else:
                print('No')
                quit()
for i, j, k in y:
    for l in k:
        if l == '(':
            tmp += 1
        else:
            if tmp > 0:
                tmp -= 1
            else:
                print('No')
                quit()
if tmp != 0:
    print('No')
else:
    print('Yes')

Solution (Python):
dicpos = {}
dicneg = {}

N = int(input())
for i in range(N):
  buf = [0]
  for s in input():
    if s=="(":
      buf.append(buf[-1] + 1)
    else:
      buf.append(buf[-1] - 1)
  low = min(buf)
  last = buf[-1]
  if last>0:
    if low in dicpos:
      dicpos[low].append(last)
    else:
      dicpos[low] = [last]
  else:
    if low-last in dicneg:
      dicneg[low-last].append(-last)
    else:
      dicneg[low-last] = [-last]
neg_sorted = sorted(dicneg.items(), key=lambda x:x[0], reverse=True)
pos_sorted = sorted(dicpos.items(), key=lambda x:x[0], reverse=True)


summ = 0
flag = 0
for i in pos_sorted:
  if flag == 1:
    break
  for j in i[1]:
    if summ + i[0] < 0:
      flag = 1
      print("No")
      break
    summ += j
summ2 = 0
if flag == 0:
  for i in neg_sorted:
    if flag == 1:
      break
    for j in i[1]:
      if summ2 + i[0] < 0:
        flag = 1
        print("No")
        break
      summ2 += j
if flag == 0:
  if summ == summ2:
    print("Yes")
  else:
    print("No")