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



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
S = [str(input()) for _ in range(N)]

plus_stock = []
minus_stock = []
for i, row in enumerate(S):
    lowest = 0
    now = 0
    for j,char in enumerate(row):
        if char == "(":
            now+=1
        elif char == ")":
            now-=1 
        if now < lowest:
            lowest = now
    if now >= 0:
        plus_stock.append([now, lowest])
    else:
        minus_stock.append([-now, lowest - now])
plus_stock  = sorted(plus_stock, key = lambda x:x[1])
minus_stock = sorted(minus_stock, key = lambda x:x[1])

now = 0

for i in range(len(plus_stock)):
    if now + plus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+plus_stock[i][0]

now = 0
for i in range(len(minus_stock)):
    if now + minus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+minus_stock[i][0]
print("Yes")

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N=int(input())
S=[input() for _ in range(N)]
T=[[0, 0] for _ in range(N)]

for i in range(N):
  s=S[i]
  l=len(s)
  c=0
  for j in range(l):
    if s[j]=='(':
      c+=1
    else:
      c-=1
      if c<T[i][1]:
        T[i][1]=c
  T[i][0]=c
        
A=[T[i] for i in range(N) if T[i][0]>=0]
B=[T[i] for i in range(N) if T[i][0]<0]

A=sorted(A, key=itemgetter(1), reverse=True)
B=sorted(B, key=itemgetter(1))

h=0
la=len(A)
lb=len(B)

i=0
while i<la:
  if h+A[i][1]<0:
    print('No')
    exit()
  else:
    h+=A[i][0]
  i+=1
  
i=0
while i<lb:
  if h+B[i][1]<0:
    print('No')
    exit()
  else:
    h+=B[i][0]
  i+=1
  
if h==0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(input())

ls = []
rs = []

total = 0
for i in range(n):
    s = input().strip()

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
            b = min(b, h)

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))
    total += h

if total != 0:
    print("No")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

h = 0
OK = True
for p in ls:
    b = h + p[0]
    h += p[1]
    if b < 0 or h < 0:
        OK = False

for p in rs:
    b = h + p[0]
    h += p[1]
    if b < 0 or h < 0:
        OK = False

if not OK:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(input())

ls = []
rs = []

total = 0
for i in range(n):
    s = input().strip()

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
            total += 1
        else:
            h -= 1
            b = min(b, h)
            total -= 1

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))

if total != 0:
    print("No")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

b = 0
total = 0
OK = True
for p in ls:
    b += p[0]
    total += p[1]
    if b < 0 or total < 0:
        OK = False

for p in rs:
    b += p[0]
    total += p[1]
    if b < 0 or total < 0:
        OK = False

if not OK:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(input())

ls = []
rs = []

total = 0
for i in range(n):
    s = input().strip()

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
            total += 1
        else:
            h -= 1
            b = min(b, h)
            total -= 1

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))

if total != 0:
    print("No")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

b = 0
total = 0
OK = True
for p in ls:
    b += p[0]
    total += p[1]
    if b < 0:
        OK = False

for p in rs:
    b += p[0]
    total += p[1]
    if b < 0:
        OK = False

if not OK:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(input())

ls = []
rs = []

total = 0
for i in range(n):
    s = input().strip()

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
            total += 1
        else:
            h -= 1
            b = min(b, h)
            total -= 1

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))

if total != 0:
    print("NO")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

b = 0
total = 0
OK = True
for p in ls:
    b += p[0]
    total += p[1]
    if b < 0:
        OK = False

for p in rs:
    b += p[0]
    total += p[1]
    if b < 0:
        OK = False

if not OK:
    print("NO")
else:
    print("YES")

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = []

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)
    lst.append([txt, compare, min(min_comp, compare)])


lst.sort(key=lambda x: x[2], reverse=True)
txt = 'No'
c = 0

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

print(txt)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    SS = read().split()

    for S in SS:
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:(x[1], x[0]), reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[0] - x[1], -x[0]), reverse=True)[::-1]

    for go, max_depth in ways_pos:
        if current + max_depth >= 0:
            current += go
        else:
            print("No")
            return None

    for go, max_depth in ways_neg:
        if current + max_depth >= 0:
            current += go
        else:
            print("No")
            return None

    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    SS = read().split()

    for S in SS:
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:x[1], reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[0] - x[1]), reverse=True)

    tmp = []
    for go, max_depth in ways_pos:
        if current + max_depth >= 0:
            current += go
        else:
            tmp.append((go, max_depth))


    tmp =[]
    for go, max_depth in ways_neg:
        if current + max_depth >= 0:
            current += go
        else:
            tmp.append((go, max_depth))

    for go, max_depth in tmp:
        if current + max_depth >= 0:
            current += go
        else:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
import itertools as itl

N = int(input())
S = [input() for x in range(N)]
S = list(itl.permutations(S))
for x in S:
    st = "".join(x)
    if len(st) % 2 != 0:
        print("No")
        exit()
    print(st)
    j = 0
    k = 0
    for y in st:
        if y == "(":
            j += 1
        elif y == ")":
            k += 1
    if j + k == len(st) and st[0] == "(" and st[-1] == ")":
        print("Yes")
        exit()
print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
B=[]
c=0
for i in range(n):
  S=input()
  a=0
  b=0
  for j in range(len(S)):
    if S[j]=="(":
      a=a+1
    else:
      a=a-1
      if a<b:
        b=a
  b=b*-1
  if b==0:
    c=c+a
  elif a>=0:
    B.append([b,-1*a])
  else:
    A.append([-1*a,-1*b])
A.sort()
B.sort()
f=0
for i in range(len(B)):
  if c-B[i][0]<0:
    f=1
  c=c-B[i][1]
for i in range(len(A)):
  if c+A[i][1]<0:
    f=1
  c=c-A[i][0]
if c!=0:
  f=1
if f==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    SS = read().split()

    for S in SS:
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:x[0], reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[0] - x[1]))


    while ways_pos:
        done = False
        for idx, (go, max_depth) in enumerate(ways_pos):
            if current + max_depth >= 0:
                current += go
                del ways_pos[idx]
                done = True
                break
        if not done:
            print('No')
            return None


    while ways_neg:
        done = False
        for idx, (go, max_depth) in enumerate(ways_neg):
            if current + max_depth >= 0:
                current += go
                del ways_neg[idx]
                done = True
                break
        if not done:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    for _ in range(N):
        S = input()
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:x[0], reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[1], -x[0]))

    while ways_pos:
        done = False
        for idx, (go, max_depth) in enumerate(ways_pos):
            if current + max_depth >= 0:
                current += go
                del ways_pos[idx]
                done = True
                break
        if not done:
            print('No')
            return None


    while ways_neg:
        done = False
        for idx, (go, max_depth) in enumerate(ways_neg):
            if current + max_depth >= 0:
                current += go
                del ways_neg[idx]
                done = True
                break
        if not done:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    for _ in range(N):
        S = input()
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:x[0], reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[1], -x[0]))

    while ways_pos:
        done = False
        for idx, (go, max_depth) in enumerate(ways_pos):
            if current + max_depth >= 0:
                current += go
                del ways_pos[idx]
                done = True
                break
        if not done:
            print('No')
            return None


    while ways_neg:
        done = False
        for idx, (go, max_depth) in enumerate(ways_neg):
            if current + max_depth >= 0:
                current += go
                del ways_neg[idx]
                done = True
        if not done:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# F

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
from itertools import accumulate

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

left = []
right = []

N = int(input())

dic = {'(':1, ')':-1}
for i in range(N):
    s = input()
    s = [dic[s] for s in s]
    s2 = list(accumulate([0] + s))
    a1 = min(s2) #最下点
    a2 = s2[-1]  #合計のプラス

    if a2 > 0:
        # leftの処理
        heappush(left, (-a1, a2))
    else:
        s = s[::-1]
        s2 = list(accumulate([0] + s))
        a3 = min(s2)  # 右から見た最下点
        # rightの処理
        heappush(right, (-a3, a1, a2))

current = 0

# print(left, right)

while len(left)>0:
    a1, a2 = heappop(left)
    a1 = -a1
    if current + a1 < 0:
        print('No')
        sys.exit()
    current += a2

while len(right)>0:
    a3, a1, a2 = heappop(right)
    if current + a1 < 0:
        print('No')
        sys.exit()
    current += a2

if current ==0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    for _ in range(N):
        S = input()
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

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

    while ways:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                if go < 0:
                    break
                current += go
                del ways[idx]
                done = True
        if not done:
            break

    ways = [(-a, b) for a, b in ways]
    ways = sorted(ways, key = itemgetter(1,0))

    while ways and current >= 0:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if go <= 0:
                print('No')
                return None
            if current + max_depth >= 0:
                current -= go
                del ways[idx]
                done = True
        if not done:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    for _ in range(N):
        S = input()
        go = 0
        max_depth = 0
        for s in S:
            go += dic[s]
            max_depth = min(max_depth, go)
        ways.append((go, max_depth))



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

    while ways:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                if go < 0:
                    break
                current += go
                del ways[idx]
                done = True
        if not done:
            break

    ways = [(-a, b) for a, b in ways]
    ways = sorted(ways, key = itemgetter(1,0))

    while ways and current >= 0:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if go <= 0:
                print('No')
                return None
            if current + max_depth >= 0:
                current -= go
                del ways[idx]
                done = True
        if not done:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    for _ in range(N):
        S = input()
        go = 0
        max_depth = 0
        for s in S:
            go += dic[s]
            max_depth = min(max_depth, go)
        if current + max_depth < 0:
            ways.append((go, max_depth))
        else:
            current += go


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

    while ways:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                if go < 0:
                    break
                current += go
                del ways[idx]
                done = True
        if not done:
            break

    ways = [(-a, b) for a, b in ways]
    ways = sorted(ways, key = itemgetter(1,0))

    while ways and current >= 0:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if go <= 0:
                print('No')
                return None
            if current + max_depth >= 0:
                current -= go
                del ways[idx]
                done = True
                break
        if not done:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    for _ in range(N):
        S = input()
        go = 0
        max_depth = 0
        for s in S:
            go += dic[s]
            max_depth = min(max_depth, go)
        if current + max_depth < 0:
            ways.append((go, max_depth))
        else:
            current += go


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

    while ways:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                if go < 0:
                    break
                current += go
                del ways[idx]
                done = True
        if not done:
            print('No')
            return None

    ways = [(-a, b) for a, b in ways]
    ways = sorted(ways, key = itemgetter(1,0))

    while ways and current >= 0:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                current -= go
                del ways[idx]
                done = True
                break
        if not done:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    for _ in range(N):
        S = input()
        go = 0
        max_depth = 0
        for s in S:
            go += dic[s]
            max_depth = min(max_depth, go)
        if current + max_depth < 0:
            ways.append((go, max_depth))
        else:
            current += go

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

    while ways:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                if go < 0:
                    break
                current += go
                del ways[idx]
                done = True
                break
        if not done:
            break

    ways = sorted(ways, key = lambda x:x[1])

    while ways and current >= 0:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                current += go
                del ways[idx]
                done = True
                break
        if not done:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    for _ in range(N):
        S = input()
        go = 0
        max_depth = 0
        for s in S:
            go += dic[s]
            max_depth = min(max_depth, go)
        if current + max_depth < 0:
            ways.append((go, max_depth))
        else:
            current += go

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


    cont = True
    while cont and ways:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                done = True
                if go < 0:
                    cont = False
                    break
                current += go
                del ways[idx]
                break
        if not done:
            break

    ways = sorted(ways, key = lambda x:x[1])

    while ways and current >= 0:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                current += go
                del ways[idx]
                done = True
                break
        if not done:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
cnt2 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


# G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
# G4.sort()
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += sum(L[1] for L in G3)

if cnt2 == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import operator
def reduceString(A):
    stack=[]
    res=[]
    for c in A:
        if c==')':
            if len(stack)==0:
                res.append(c)
            else:
                stack.pop()
        else:
            stack.append(c)
    if len(stack)!=0:
        res+=stack
    return "".join(res)
def getTup(S,EndsWidth):
    if S in EndsWidth:
        return EndsWith[S].pop()
    else:
        for i in range(S,10**6):
            if i in EndsWith:
                return EndsWith[i].pop()

N=int(input())
S=[]
for i in range(N):
    S.append(reduceString(input()))
D={}
for i in range(len(S)):
    c=S[i]
    D[S[i]]=c.count("(")
D = sorted(D.items(), key=operator.itemgetter(1))
D.reverse()
S=[]
for v in D:
    S.append(v[0])
prev=S[0]
for i in range(1,len(S)):
    prev1=prev+S[i]
    prev1=reduceString(prev1)
    prev2=S[i]+prev
    prev2=reduceString(prev2)
    if len(prev1)<len(prev2):
        prev=prev1
    else:
        prev=prev2
if prev=="":
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
def gb(s):
	bal = 0
	m = 0
	for l in s: 
		bal += 1 if l == '(' else -1
		m = min(m, bal)
	return (bal,m)


rs = [gb(raw_input()) for _ in range(n)]
rs.sort(key = lambda x: (-x[1], -x[0]) if x[0]>=0 else (x[1] - x[0], -x[0]))

def f(rs):
	s = 0
	for aa,bb in rs:
		if s + bb < 0: return False
		s += aa
	return s == 0

print 'Yes' if f(rs) else 'No'

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
def gb(s):
	bal = 0
	m = 0
	for l in s: 
		bal += 1 if l == '(' else -1
		m = min(m, bal)
	return (bal,m)


adds, dels = [], []
for _ in range(n):
	e = gb(raw_input())
	if e[0] >= 0:
		adds.append(e)
	else:
		dels.append(e)
adds.sort(key = lambda x: (-x[1], -x[0]))
dels.sort(key = lambda x: (x[1] - x[0], -x[0]))
def f(adds, dels):
	s = 0
	for aa,bb in adds:

		if s + aa < 0:
			return False
		if s + bb < 0:
			return False
		s += aa
		

	for aa,bb in dels:

		if s + aa < 0:
			return False
		if s + bb < 0:
			return False
		s += aa
	return True

print 'Yes' if f(adds, dels) else 'No'

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
def gb(s):
	bal = 0
	m = 0
	for l in s: 
		bal += 1 if l == '(' else -1
		m = min(m, bal)
	return (bal,m)
adds, dels = [], []
for _ in range(n):
	e = gb(raw_input())
	if e[0] >= 0:
		adds.append(e)
	else:
		dels.append(e)
adds.sort(key = lambda x: (-x[1], x[0]))
dels.sort(key = lambda x: (x[1] - x[0], x[0]))
def f(adds, dels):
	s = 0
	for aa,bb in adds:

		if s + aa < 0:
			return False
		if s + bb < 0:
			return False
		s += aa
		

	for aa,bb in dels:

		if s + aa < 0:
			return False
		if s + bb < 0:
			return False
		s += aa
	return True

print 'Yes' if f(adds, dels) else 'No'

Submission status: Wrong Answer

Solution code:
def result(m, b):
    sum1 = m
    resmin = m
    for i in range(len(b)):
        resmin += b[i][0]
        if resmin < 0:
            return -1
    for i in range(len(b)):
        sum1 += b[i][1]
    if sum1 != 0:
        return -1
    return 0
n = int(input())
resmin = 10 ** 7
set_pos = []
set_neg = []
for i in range(n):
    a = input().strip('\n')
    loc_min = 10 ** 7
    total = 0
    tmp = 0
    for j in range(len(a)):
        if a[j] == '(':
            tmp += 1
        else:
            tmp -= 1
        if tmp < loc_min:
            loc_min = tmp
    total = tmp
    if loc_min >= 0:
        set_pos.append((loc_min, total))
    else:
        set_neg.append((loc_min, total))
total_pos = 0
for elem in set_pos:
    total_pos += elem[1]
b = sorted(set_neg, key = lambda l: l[0], reverse = True)
#print(b)
res = result(total_pos, b)
print('No' if res == -1 else 'Yes')