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())
sp=[]
sn=[]
for i in range(n):
    s=input().rstrip()
    m=0
    temp=0
    for j in s:
        if j=='(':
            temp+=1
        else:
            temp-=1
        m=min(m,temp)
    m=-m
    if temp>=0:
        sp.append((m,temp))
    else:
        sn.append((m+temp,-temp))
sp.sort()
sn.sort()
vp=0
for i in sp:
    if vp-i[0]<0:
        print('No')
        sys.exit()
    else:
        vp+=i[1]
vn=0
for i in sn:
    if vn-i[0]<0:
        print('No')
        sys.exit()
    else:
        vn+=i[1]
if vp==vn:
    print('Yes')
else:
    print('No')

Solution (Python):


N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append((min_state, state))
    else:
        list_minus.append((min_state - state, -state))

def compute(arr):
    total_state = 0
    for min_state, state in arr[::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

Solution (Python):
n = int(input())
lr1, lr2 = [], []
res = 0
for _ in range(n):
    s = input()
    m = len(s)

    l, r = 0, 0
    tmp = 0
    for i in range(m):
        if s[i] == ')':
            tmp += 1
        else:
            tmp -= 1
        l = max(l, tmp)
    tmp = 0
    for i in range(m):
        if s[m-1-i] == '(':
            tmp += 1
        else:
            tmp -= 1
        r = max(r, tmp)

    res += r - l
    if r - l >= 0:
        lr1.append((l, r))
    else:
        lr2.append((l, r))

if res != 0:
    print('No')
    exit()

lr1.sort(key=lambda x: x[0])
lr2.sort(key=lambda x: x[1])

flg1, flg2 = True, True

n1, n2 = len(lr1), len(lr2)
tmp = 0
for i in range(n1):
    l, r = lr1[i]
    tmp -= l
    if tmp < 0:
        flg1 = False
    tmp += r

tmp = 0
for i in range(n2):
    l, r = lr2[i]
    tmp -= r
    if tmp < 0:
        flg2 = False
    tmp += l

if flg1 and flg2:
    print('Yes')

else:
    print('No')

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    pos = []
    neg = []
    tot = 0
    for i in range(N):
        tmp = 0
        b = 0
        for c in sr():
            if c == '(':
                tmp += 1
            else:
                tmp -= 1
                b = min(b, tmp)
        if tmp > 0:
            pos.append([tmp, b])
        else:
            neg.append([-tmp, b-tmp])
        tot += tmp
    if tot != 0:
        print('No')
        return
    pos = sorted(pos, key=lambda x: (x[1], x[0]))[::-1]
    neg = sorted(neg, key=lambda x: (x[1], x[0]))[::-1]
    c = 0
    for p in pos:
        t, b = p
        if c+b < 0:
            print('No')
            return
        c += t
    c = 0
    for n in neg:
        t, b = n
        if c+b < 0:
            print('No')
            return
        c += t
    print('Yes')
    return
resolve()

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

pdat=[]
mdat=[]

for i in range(n):
    s=input()
    
    mini=0
    now=0
    for q in range(len(s)):
        if s[q]=="(":
            now+=1
        else:
            now-=1
            mini=(min(mini,now))
    if now>=0:
        pdat.append((now,mini,mini-now))
    else:
        mdat.append((now,mini,mini-now))

pdat.sort(key=lambda x:-x[1])
mdat.sort(key=lambda x:x[2])

now=0
for d in pdat+mdat:
    if now+d[1]<0:
        print("No")
        break
    now+=d[0]
else:
    if now==0:
        print("Yes")
    else:
        print("No")

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
plus, minus = [], []
for _ in range(n):
	s = input()
	mi, cur = 0, 0
	for i in range(len(s)):
		if s[i] == "(":
			cur += 1
		else:
			cur -= 1
		mi = min(mi, cur)
	if cur >= 0:
		plus.append((mi, cur))
	else:
		minus.append((mi, cur))

plus.sort(key=lambda x: -x[0])
minus.sort(key=lambda x: x[0] - x[1])
res = plus + minus

cur = 0
for m, t in res:
	if cur + m < 0:
		print("No")
		exit()
	cur += t

if cur != 0:
	print("No")
	exit()
print("Yes")

Solution (Python):

n = int(input())
s = [list(input()) for i in range(n)]
r = []
l = []
ans = 0
for i in s:
    now = 0
    c = 0
    for j in i:
        if j =="(":
            now += 1
        else:
            now -= 1
        c = min(c,now)
    if c == 0:
        ans += now
    elif now >= 0:
        l.append([c,now])
    else:
        r.append([c-now,now])

l.sort(reverse =True)
r.sort()
for i,j in l:
    if ans + i < 0:
        print("No")
        exit()
    else:
        ans += j

for i,j in r:
    if ans +i+j < 0:
        print("No")
        exit()
    else:
        ans += j
if ans == 0:
    print("Yes")
else:
    print("No")

Solution (Python):

import sys
input = sys.stdin.readline

n = int(input())
increasing = []
decreasing = []
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))
    else:
        decreasing.append((minima - fin, fin))

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

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

Solution (Python):
n = int(input())
L = []
R = [] 
for _ in range(n):
  s = input()
  btm = 0
  total = 0
  for c in s:
    if c == "(":
      total += 1
    else:
      total -= 1
    btm = min(btm, total)
  if total > 0:
    L.append((btm, total))
  else:
    R.append((btm - total, - total))
    
L.sort(key=lambda x: (-x[0], -x[1]))
R.sort(key=lambda x: (-x[0], -x[1]))

Lcrr_end = 0
for b, e in L:
  if Lcrr_end + b < 0:
    print("No")
    exit()
  Lcrr_end += e

Rcrr_end = 0
for b, e in R:
  if Rcrr_end + b < 0:
    print("No")
    exit()
  Rcrr_end += e

if Lcrr_end - Rcrr_end == 0:
  print("Yes")
else:
  print("No")

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

n = int(input())
cnt = 0
decrement = 0
profit = []
loss = []

for _ in range(n):
    s = input().rstrip()
    min_p = 0
    end_p = 0
    point = 0
    for c in s:
        if c == '(':
            point += 1
        elif c == ')':
            point -= 1
            if point < min_p:
                min_p = point
    else:
        end_p = point
    if 0 <= min_p:
        cnt += end_p
    else:
        if min_p == end_p:
            decrement += end_p
        else:
            if 0 <= end_p:
                profit.append((min_p, end_p))
            else:
                loss.append((min_p, end_p))



profit.sort()
while profit:
    min_p, end_p = profit.pop()
    if cnt+min_p < 0:
        print('No')
        exit()
    cnt += end_p


loss.sort(reverse=True)
while loss:
    min_p, end_p = loss.pop()
    if cnt+min_p < 0:
        print('No')
        exit()
    cnt += end_p

print('Yes' if cnt+decrement == 0 else 'No')

Solution (Python):
from sys import stdin

def main():
    plus, minus = [], []
    readline = stdin.readline
    n = int(readline())
    for _ in range(n):
        s = readline().rstrip()
        if 2 * s.count('(') - len(s) > 0:
            plus.append(s)
        else:
            minus.append(s)
    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)

    sum = 0
    for v in ''.join(plus + minus):
        sum = sum + (1 if v == '(' else -1)
        if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin

def main():
    plus, minus = [], []
    readline = stdin.readline
    n = int(readline())
    for _ in range(n):
        s = readline().rstrip()
        if 2 * s.count('(') - len(s) > 0:
            plus.append(s)
        else:
            minus.append(s)
    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)
    plus.extend(minus)

    sum = 0
    for v in ''.join(plus):
        sum = sum + (1 if v == '(' else -1)
        if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    plus, minus = [], []
    for c in s:
        if 2 * c.count('(') - len(c) > 0:
            plus.append(c)
        else:
            minus.append(c)

    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)
    plus.extend(minus)
    sum = 0
    for v in plus:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import heapq

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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:
        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)

Solution (Python):
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(chain([0],t),lambda a,b: a+(1 if b=="(" else -1))),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print("No" if m else "Yes")

Solution (Python):
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(chain([0],t),lambda a,b: a+(1 if b=="(" else -1))),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print("No" if m else "Yes")

Solution (Python):
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print("No" if m else "Yes")

Solution (Python):
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:
    print("No" if m else "Yes")

Solution (Python):
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if m+c<0:print("No");break
    m+=d
else:
    print("No" if m else "Yes")

Solution (Python):
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if m+c<0:
        print("No");break
    m+=d
else:
    print("No" if m else "Yes")

Solution (Python):
from itertools import *
n,*s=open(0).read().split()
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*s_.count("(")-len(s_)] for s_ in s]
now=0
for c,d in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c<0:
        print("No");break
    now+=d
else:
    print("No" if now else "Yes")

Solution (Python):
from itertools import accumulate,chain
n,*s=open(0).read().split()
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*s_.count("(")-len(s_)] for s_ in s]
now=0
for c,d in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c<0:
        print("No");break
    now+=d
else:
    print("No" if now else "Yes")

Solution (Python):
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]
now=0
for c,d in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c<0:
        print("No");break
    now+=d
else:
    print("No" if now else "Yes")

Solution (Python):
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]
now=0
for c in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c[0]<0:
        print("No");break
    now+=c[1]
else:
    print("No" if now else "Yes")

Solution (Python):
n = int(input())
flag = 0
ML = []
MM = []
MR = []
L = 0
R = 0
for _ in range(n):
    s = input()
    saisho = 0
    cur = 0
    for w in s:
        if w == "(":
            cur += 1
        else:
            cur -= 1
            saisho = min(saisho, cur)
    if cur > 0:
        ML.append((saisho, cur))
    elif cur < 0:
        MR.append((-cur + saisho, -cur))
    else:
        MM.append((saisho, cur))
ML.sort(reverse=True)
MR.sort(reverse=True)
leftnow = 0
for saisho, delta in ML:
    if leftnow + saisho < 0:
        flag = 1
    leftnow += delta
for saisho, delta in MM:
    if leftnow + saisho < 0:
        flag = 1
    leftnow += delta
rightnow = 0
for saisho, delta in MR:
    if rightnow + saisho < 0:
        flag = 1
    rightnow += delta

if rightnow != leftnow:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Solution (Python):
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
if sum(t)!=0:
    print("No");exit()
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]
now=0
for c in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c[0]<0:
        print("No");exit()
    now+=c[1]
print("Yes")

Solution (Python):
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
if sum(t)!=0:
    print("No");exit()

st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]

now=0
v=list(filter(lambda x:x[1]>=0,st))
w=list(filter(lambda x:x[1]<0,st))
v.sort()
w.sort(key=lambda z:z[1]-z[0])

for c in chain(v[::-1],w[::-1]):
    if now+c[0]<0:
        print("No");exit()
    now+=c[1]
print("Yes")

Solution (Python):
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No");exit()

st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=0
v=list(filter(lambda x:x[0]>=0,st))
w=list(filter(lambda x:x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

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

def main():
  N = int(readline())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = readline().strip()
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Solution (Python):
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=list(map(lambda x:2*x.count("(")-len(x),s))
if sum(t)!=0:
    print("No")
    exit()

st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Solution (Python):
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    exit()

st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Solution (Python):
n = int(input())
L, R = [], []
for i in range(n):
    a, b = 0, 0
    for c in input():
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    if -a + b > 0:
        L.append((a, b))
    else:
        R.append((a, b))
L.sort(key=lambda x: x[0])
R.sort(key=lambda x: x[1], reverse=True)
x = 0
for a, b in L + R:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

Solution (Python):
def check(li):
    b = 0
    for eb, eh in li:
        if b + eb < 0:
            return False

        b += eh

    return True


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

l = []
r = []
sm = 0
for word in s:
    h = 0
    b = 0
    for e in word:
        if e == "(":
            h += 1
        else:
            h -= 1

        b = min(b, h)

    if h > 0:
        l.append([b, h])
    else:
        r.append([b-h, -h])

    sm += h

l.sort(reverse=True)
r.sort(reverse=True)

if check(l) and check(r) and sm == 0:
    ans = "Yes"
else:
    ans = "No"
print(ans)

Solution (Python):








import sys
readline = sys.stdin.readline

N = int(readline())
opencnt = 0
closecnt = 0
open_close_up = []
open_close_equal = []
open_close_down = []
for i in range(N):
  s = readline().rstrip()
  while "()" in s:
    s = s.replace("()","")
  opn = s.count("(")
  clo = s.count(")")
  if opn == 0 and clo == 0:
    
    continue
  if opn == 0:
    
    closecnt += clo
  elif clo == 0:
    
    opencnt += opn
  elif opn > clo: 
    open_close_up.append([clo,opn])
  elif opn == clo:
    open_close_equal.append([clo,opn])
  elif opn < clo:
    open_close_down.append([clo,opn])

open_close_up = sorted(open_close_up,key = lambda x:x[0]) 
open_close_down = sorted(open_close_down,key = lambda x:x[0],reverse = True) 
  

cur = opencnt


for i in range(len(open_close_up)):
  clo,opn = open_close_up[i][0],open_close_up[i][1]
  if clo > cur:
    print("No")
    exit(0)
  cur -= clo
  cur += opn


for i in range(len(open_close_equal)):
  clo,opn = open_close_equal[i][0],open_close_equal[i][1]
  if clo > cur:
    print("No")
    exit(0)
    
for i in range(len(open_close_down)):
  clo,opn = open_close_down[i][0],open_close_down[i][1]
  if clo > cur:
    print("No")
    exit(0)
  cur -= clo
  cur += opn
  
if cur - closecnt == 0:
  print("Yes")
else:
  print("No")

Solution (Python):
n = int(input())
S = [input() for i in range(n)]
AB = []
for i in range(n):
    a, b = 0, 0
    for c in S[i]:
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    AB.append((a, b))
AB0 = [(a, b) for a, b in AB if -a + b >= 0]
AB1 = [(a, b) for a, b in AB if -a + b < 0]
AB0.sort()
AB1.sort(key=lambda x: -x[1])
AB = AB0 + AB1
x = 0
for a, b in AB:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

Solution (Python):
import sys
from functools import reduce
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)

now2=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v,w=list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for vsub in v:
    if now2+vsub[1]<0:
        print("No")
        sys.exit()
    now2+=vsub[0]
for wsub in w:
    if now2+wsub[1]<0:
        print("No")
        sys.exit()
    now2+=wsub[0]
print("Yes")

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
css = [0] * N
mns = [0] * N
t = [x for x in range(N)]
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": css[x] += 1
    if S[i] == ")":
      css[x] -= 1
      mns[x] = min(mns[x], css[x])
if sum(css):
  print("No")
  exit(0)
t.sort(key = lambda x: -10 ** 7 if mns[x] == 0 else -10 ** 7 - mns[x] if css[x] >= 0 else mns[x] - css[x])
l = 0
for i in t:
  if l + mns[i] < 0:
    print("No")
    exit(0)
  l += css[i]
print("Yes")

Solution (Python):
n = int(input())
lst_left = []
lst_right = []
total = 0
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  if h>=0:
    lst_left.append((b, h))
  else:
    lst_right.append((b-h, -h))
  total += h

lst_left = sorted(lst_left, key=lambda x:x[0], reverse=True)

lst_right = sorted(lst_right, key=lambda x:x[0], reverse=True)

if total != 0:
  print("No")
  exit()
h = 0
for i in range(len(lst_left)):
  if h + lst_left[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_left[i][1]
h = 0
for i in range(len(lst_right)):
  if h + lst_right[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_right[i][1]
print("Yes")

Solution (Python):
n=int(input())
L=0
R=0

p1=[]
p2=[]
p3=[]

for _ in range(n):

    s=input()

    
    
    

    flag=0
    ll=0
    rr=0
    temp=0

    for ss in s:
        if ss==")":
            if  rr>0:
                rr-=1
            else:
                ll+=1
        elif ss=="(":
            rr+=1
 
    if rr>0 and ll>0:
        p1.append((ll-rr,ll,rr))
    elif rr>0:
        p3.append(rr)
    else:
        p2.append(ll)

cnt=0
for item in p3:
    cnt+=item



p1.sort()
for item in p1:
    lll=item[1]
    rrr=item[2]

    cnt-=lll
    if cnt<0:
        print("No")
        exit()
    cnt+=rrr

    if cnt<0:
        print("No")
        exit()

for item in p2:
    cnt-=item
    if cnt<0:
        print("No")
        exit()
if cnt==0:
    print("Yes")
else:
    print("No")

Solution (Python):
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)

u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        
        if now2+w[i-lu-lv][1]<0:
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")

Solution (Python):
n,inc,dec=int(input()),[],[]
for _ in range(n):
  s,d,r=input(),0,0
  for c in s:
    d=d+(1 if c=='(' else -1)
    r=max(r,-d)
  (dec if d<0 else inc).append((d,r))
inc.sort(key=lambda x:x[1])
dec.sort(key=lambda x:x[0]+x[1])
p1,p2,ok=0,0,True
for s in inc:
  ok&=s[1]<=p1
  p1+=s[0]
for s in dec:
  ok&=p2>=s[0]+s[1]
  p2-=s[0]
ok&=p1==p2
print('Yes'if ok else'No')

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = [input().rstrip() for _ in range(N)]

    neg = []
    pos = []
    total = 0
    for i, s in enumerate(S):
        t = 0
        tmn = 0
        for c in s:
            if c == '(':
                t += 1
            else:
                t -= 1
            tmn = min(tmn, t)
        if t >= 0:
            pos.append((tmn, t))
        else:
            neg.append((tmn - t, -t))
        total += t

    if total != 0:
        print('No')
        return
    t = 0
    for tmn, tsm in sorted(pos, reverse=True, key=lambda x: x[0]):
        if t + tmn < 0:
            print('No')
            return
        t += tsm
    t = 0
    for tmn, tsm in sorted(neg, reverse=True, key=lambda x: x[0]):
        if t + tmn < 0:
            print('No')
            return
        t += tsm
    print('Yes')


if __name__ == '__main__':
    main()

Solution (Python):
import sys
n = int(input())
x, y = [], []
for _i in range(n):
    s = input()
    p = 0
    m = 0
    for j in range(len(s)):
        if s[j]=="(":
            p += 1
        else:
            p -= 1
            m, _m = sorted([p, m])
    if p > 0:
        x.append([m, p])
    else:
        y.append([m-p, -p])

x.sort(reverse=True)
y.sort(reverse=True)
r = 0
for s, t in x:
    if r+s < 0:
        print("No")
        sys.exit()
    r += t
result = 0
for s, t in y:
    if result+s < 0:
        print("No")
        sys.exit()
    result += t
if r-result == 0:
    print("Yes")
else:
    print("No")

Solution (Python):
import sys
n = int(input())
x, y = [], []
for _i in range(n):
    s = input()
    p = 0
    m = [0]
    for j in range(len(s)):
        if s[j]=="(":
            p += 1
        else:
            p -= 1
            m.append(p)
    if p > 0:
        x.append([min(m), p])
    else:
        y.append([min(m)-p, -p])

x.sort(reverse=True)
y.sort(reverse=True)
r = 0
for s, t in x:
    if r+s < 0:
        print("No")
        sys.exit()
    r += t
result = 0
for s, t in y:
    if result+s < 0:
        print("No")
        sys.exit()
    result += t
if r-result == 0:
    print("Yes")
else:
    print("No")

Solution (Python):
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort(reverse=1)
mab.sort(key=lambda x:x[0]-x[1])


ab=pab+mab
n=0
for a,b in ab:
  if n+a<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('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")