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

ar = []

for i in range(N):
    n = 0
    m = 0
    for s in input():
        if s == '(':
            n = n + 1
        elif s == ')':
            n = n - 1
        if n < m:
            m = n
    ar.append((m, n))

v = sorted(ar, reverse=True, key=lambda x:x[0])
	
p = 0
for vv in v:
    if p + vv[0] < 0:
        print('No')
        sys.exit()
    else:
        p = p + vv[1]
if p == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys

pos, neg = [], []
n = int(input())
for i in range(n):
    s = input()
    bal = 0
    min_bal = 0
    for c in s:
        bal += 1 if c == '(' else -1
        min_bal = min(bal, min_bal)

    if bal > 0:
        pos.append((min_bal, bal))
    else:
        neg.append((min_bal, bal))

pos.sort(reverse=True)
neg.sort(key = lambda p: (p[0], -p[1]))

cur = 0
for m, e in pos:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

for m, e in neg:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

print("Yes" if cur == 0 else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())

a = 0
b = 0

for i in range(N):
    S = input()
    a += S.count('(')
    b += S.count(')')

if a == b:
    print('Yes')
    if N >= 100:
        print('No')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def main():
    from collections import defaultdict
    import sys
    input = sys.stdin.readline

    N = int(input())

    dc = defaultdict(int)
    do = defaultdict(int)
    for _ in range(N):
        s = input().rstrip()

        open_ = 0
        close_ = 0
        for c in s:
            if c == '(':
                open_ += 1
            else:
                if open_:
                    open_ -= 1
                else:
                    close_ += 1

        if (close_ or open_) and (close_ != open_):
            dc[close_] += 1
            do[open_] += 1

    if not dc and not do:
        print('No')
        return

    for key in {*dc.keys(), *do.keys()}:
        if dc[key] != do[key]:
            print('No')
            return

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

sl = []

left = 0
right = 0
lrl = []
for _ in range(n):
    s = list(input())
    for ss in s:
        if ss == "(":
            left += 1
        else:
            right += 1
    lrl.append(s)
if left != right:
    print("No")
    exit()


values = []
cost = 0
import heapq
heapq.heapify(values)
values = []
for lr in lrl:
    value = [0, 0]
    for i in lr:
        if i == "(":
            value[1] += 1
        else:
            value[1] -= 1
        value[0] = min(value[0], value[1])
    value[1] = -value[1]
    values.append(value)
ansl = []
heapq.heapify(ansl)

ans = 0
while True:
    while values:
        c, s = heapq.heappop(values)
        if c <= cost:
            heapq.heappush(ansl, [-s, c])
        else:
            heapq.heappush(values, [c, s])
            break
    if not ansl:
        print("No")
        exit()
    s, c = heapq.heappop(ansl)
    if c > cost:
        print("No")
        exit()
    cost -= s
    if cost < 0:
        print("No")
        exit()
    ans += 1
    if ans == n:
        print("Yes")
        exit()

Submission status: Wrong Answer

Solution code:
n = int(input())

stats = []
for i in range(n):
    s = input().rstrip()

    neg = 0
    pos = 0
    for v in s:
        if v == '(':
            pos += 1
        else:
            if pos > 0:
                pos -= 1
            else:
                neg += 1
    stats.append((neg, -pos))

stats.sort()

cur = 0
for i in range(n):
    neg, pos = stats[i]
    pos = -pos
    if cur < neg:
        print('No')
        exit()

    cur = cur - neg + pos

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

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
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 = [INF] * 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

# log(l_ok)
# log(r_ok)

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

strs = []

# LeftOKを並べる
for i in range(n):
    if l_ok[i]:
        strs.append(S[i])

# LeftもRightもだめなやつをminL-Rが多い順に並べる
ngs = []
for i in range(n):
    if not l_ok[i] and not r_ok[i]:
        ngs.append((-1 * min_lmr[i], -1 * lmr[i], i))

ngs.sort()

for ng in ngs:
    strs.append(S[ng[2]])

# RightOKを並べる
for i in range(n):
    if r_ok[i] and not l_ok[i]:
        strs.append(S[i])

# log(ngs)
# log(min_lmr)
# log("".join(strs))

l = 0
r = 0
for s in strs:
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                print("No")
                exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
def task(n, s):
    left = 0
    right = 0

    for ss in s:
        localleft = 0
        localright = 0

        for c in ss:
            if c == '(':
                localleft += 1
            elif c == ')':
                if localleft > 0:
                    localleft -= 1
                else:
                    localright += 1

        pairsleft = min(localleft, right)
        pairsright = min(localright, left)

        if pairsleft >= pairsright:
            right -= pairsleft
            localleft -= pairsleft
        else:
            left -= pairsright
            localright -= pairsright

        left += localleft
        right += localright

    if left == 0 and right == 0:
        print("Yes")
    else:
        print("No")


n = int(input())
s = []
for i in range(0, n):
    s.append(input())
task(n, s)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = ["" for _ in range(n)]
for i in range(n):
	s[i] = input()

balance = [0 for _ in range(n)]
min_balance = [0 for i in range(n)]

min_to_b = {}

for i in range(n):
	cur_bal = 0
	for j in range(len(s[i])):
		if s[i][j] == "(":
			cur_bal += 1
		else:
			cur_bal -= 1
		if cur_bal < min_balance[i]:
			min_balance[i] = cur_bal
	balance[i] = cur_bal
	min_to_b[min_balance[i]] = min_to_b.get(min_balance[i], []) + [balance[i]]

min_balance = list(set(min_balance))
min_balance.sort(reverse = True)
# print("min_balance", min_balance)

for item in min_balance:
	min_to_b[item].sort(reverse=True)

cur_bal = 0
flag_good = True
for min_b in min_balance:
	# print("min_b", min_b)
	for bal in min_to_b[min_b]:
		if min_b + cur_bal < 0:
			flag_good = False
			# print("flag break")
			break
		cur_bal += bal
		# print("cur_bal", cur_bal)

# print("min_to_b", min_to_b)

# # order = sorted(zip(min_balance, balance), reverse=True)

# flag_good = True
# cur_balance = 0
# for i in range(n):
# 	if order[i][0] + cur_balance >= 0:
# 		cur_balance += order[i][1]
# 	else:
# 		flag_good = False
# 		break
# print("cur_bal", cur_bal)
if flag_good and cur_bal == 0:
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
h = []
base = 10 ** 7
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  hpush(h, ls[x] * base - rs[x])
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l = 1
  if rs[i] == 0 and (ls[i] > 0): r = 1
if l & r == 0:
  print("No")
  exit(0)
print("Yes")

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [input() for i in range(N)]

def brancket(s):
    ans = [0, 0]
    l, r = 0, 0
    for i in s:
        if i == ')':
            if r == 0:
                ans[0] += 1
            else:
                r -= 1
        if i == '(':
            r += 1
    ans[1] = r
    return ans

L, R, tl, tr = 0, 0, False, False
bigl, bigr = 0, 0
for i in S:
    if (a := brancket(i)) != [0, 0]:
        if a[0] == 0:
            tl = True
        if a[1] == 0:
            tr = True
    L += a[0]
    R += a[1]
    bigl = max(bigl, a[0])
    bigr = max(bigr, a[1])

if L != 0 or R != 0:
    if bigl <= R - bigr and bigr <= L - bigl:
        print('Yes' if tl and tr and L == R else 'No')
    else:
        print('No')
        
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
import heapq
import sys

#input = sys.stdin.readline

def main():
    N = int(input())

    data = [0]*N
    for i in range(N):
        S = list(str(input()))
        s = 0
        m = 0
        for j in range(len(S)):
            if S[j] == "(":
                s += 1
            else:
                s -= 1
                m = min(m,s)
        data[i] = (-m,-s)


    heapq.heapify(data)
    x = 0
    valid = []
    heapq.heapify(valid)

    det = 0

###
#print("data",data)
#print("valid",valid)
#print(x)
###

    while data:
        while data and x - data[0][0] >= 0:
            y = heapq.heappop(data)
            heapq.heappush(valid,(y[1],y[0]))
    
        while valid and x >= 0:
            z = heapq.heappop(valid)
            x -= z[0]
    
        if data and x - data[0][0] < 0:
            det = -1
            break

    if det == 0 and x == 0 and valid == []:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 998244353
INF = float('inf')
# ----------------------------------------------------------- #

n = I()
s = []
su = 0
for i in range(n):
    mi_ = 0
    tmp = 0
    s_ = input()
    for x in s_:
        if x == "(":
            tmp += 1
        else:
            tmp -= 1
        mi_ = min(mi_, tmp)
    s.append((tmp, mi_))
    su += tmp

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

# print(s)
s.sort(key=itemgetter(0, 1), reverse=True)
# print(s)

acc = 0
for i in range(n):
    if acc + s[i][1] < 0:
        print("No")
        exit()
    acc += s[i][0]

print("Yes")

Submission status: Wrong Answer

Solution code:
n,*s=open(0)
n=int(n)
f=g=h=a=b=m=0
for t in s:
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
    x=r-c
    y=l-c
    if x==y==0:h+=1
    if x==0:f=1
    elif y==0:g=1
    else:m+=1
    a+=x
    b+=y
if ((h>1 and not m) or f and g) and a==b:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

lr = []

for i in range(N):
    tmp = 0
    tmp2 = float("inf")
    tmp3 = -float("inf")
    for j in range(len(S[i])):
        if S[i][j] == "(":
            tmp += 1
        else:
            tmp -= 1
        tmp2 = min(tmp2, tmp)
        tmp3 = max(tmp3, tmp)
    lr.append([i, tmp2, tmp3])

lr.sort(key = lambda x:x[2], reverse = True)
lr.sort(key = lambda x:x[1], reverse = True)

left = 0
right = 0
for i in range(N):
    for x in S[lr[i][0]]:
        if x == "(":
            left += 1
        else:
            right += 1
        if left < right:
            print("No")
            exit()

print("Yes" if left == right else "No")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

left = 0
right = 0

has_z_left = False
has_z_right = False
has_sep = False

for _ in range(N):
    S = list(input())
    L = len(S)

    r = 0
    l = 0
    for i in range(L):
        s = S[i]

        if s == ")":
            if l == 0:
                r += 1
            else:
                l -= 1
        elif s == "(":
            l += 1

    R = r

    r = 0
    l = 0
    for i in range(L - 1, -1, -1):
        s = S[i]

        if s == "(":
            if r == 0:
                l += 1
            else:
                r -= 1
        elif s == ")":
            r += 1

    L = l

    if L == 0 and R > 0:
        has_z_left = True

    if L == 0 and R > 0:
        has_z_right = True

    if not (L == R and L == 0):
        has_sep = True

    left += L
    right += R


if left == right:
    if not has_sep:
        print("Yes")
    else:
        if has_z_left and has_z_right:
            print("Yes")
        else:
            print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
R = L = 0
for _ in range(n):
    s = input()
    p = 0
    for i in range(len(s)):
        c = s[i]
        if p == 0 and c == ")":
            L += 1
        if c == "(":
            p += 1
        if p > 0  and c==")":
            p -= 1
    R += p
    #print(s,p,L,R)
if R == L:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
start = 0
end = 0
left = 0
double = []
right = 0
for i in range(n):
    s = str(input())
    kienaileft = 0
    kienairight = 0
    for j in range(len(s)):
        if s[j] == ")":
            kienaileft += 1
        else:
            break
    for j in range(len(s)):
        if s[-(j+1)] == "(":
            kienairight += 1
        else:
            break
    nowleft = 0
    nowright = 0
    for j in range(kienaileft,len(s)-kienairight):
        if s[j] == ")":
            nowleft += 1
        else:
            nowright += 1
    num = min(nowleft,nowright)
    kienaileft += nowleft -num
    kienairight += nowright -num
    if kienaileft != 0:
        if kienairight != 0:
            double.append([kienaileft,kienairight])
        else:
            left += kienaileft
    else:
        if kienairight != 0:
            right += kienairight
  # print(left,double,right)
if left + sum([double[i][0] for i in range(len(double))]) != sum([double[i][1] for i in range(len(double))]) + right:
    print("No")
    exit()
if not left or not right:
    print("No")
    exit()
double.sort(key=lambda x:x[0]-x[1])
double.sort()
now = left
for a,b in double:
    if now < a:
        print("No")
        exit()
    now += (b-a)
print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
data = []
le,ri = 0,0
for i in range(n):
    s = input()
    left,right = 0,0 #left (
    for j in s:
        if j == "(":
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                right += 1
    le += left
    ri += right
    data.append([left,right])

if le != ri: #閉じない
    print("No")
    exit()
if le == ri == 0: #全部それぞれで完結
    print("Yes")
    exit()

check1,check2,check3 = False,False,True
data.sort(key=lambda z:z[1])
now = 0
left,right = 0,0
for i,xy in enumerate(data):
    x,y = xy[0],xy[1]
    if x > 0 and y == 0:
        check1 = True
        left = i
    if x == 0 and y > 0:
        check2 = True
        right = i

now = data[left][0]
data.sort(key=lambda z:z[1])
for i,xy in enumerate(data):
    x,y = xy[0],xy[1]
    if i == left or i == right:continue
    now -= y
    if now < 0:
        check3 = False
        break
    now += x

print("Yes" if check1 and check2 and check3 else "No")

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n = int(input())
s = [input() for i in range(n)]
ls=list() #mn,end
nonk = list()
for i in range(n):
    now = 0
    mn = 0
    for c in s[i]:
        if c == '(':
            now += 1
        else:
            now -= 1
            mn = min(mn,now)
    ls.append([mn,now])
    if mn == 0 and now == 0:
        nonk.append(i)

ls.sort(reverse=True)
tmn = 0
tend =0
for mn,end in ls:
    tmn = mn + tend
    tend += end
    if tmn < 0 or tend < 0:
        print("No")
        break
else:
    if tend != 0:
        print("No")
    else:
        print('Yes')

Submission status: Wrong Answer

Solution code:
N = int(input())
li = []

for i in range(N):
    S = input()

    memo = 0
    memo2 = -10**10
    for j in range(len(S)):
        if S[j] == "(":
            memo -= 1
        else:
            memo += 1
        memo2 = max(memo,memo2)
    
    li.append([memo,memo2,S])

li = sorted(li,key=lambda x:x[0])

# print(li)

cnt = 0
for i in range(len(li)):
    
    if cnt+li[i][1] > 0:
        print("No")
        break
    cnt += li[i][0]
else:
    if cnt ==0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
braket =[]
left_flag = 0
right_flag = 0
tot_flag = 0
sum_braket = 0
for i in range(N):
    S = input()
    left = 0
    right = 0
    for j in range(len(S)):
        if S[j]==")":
            left += 1
        else:
            left_end = j
            break
    for j in range(len(S)-1,-1,-1):
        if S[j]=="(":
            right += 1
        else:
            right_end = j
            break
    left_tot=0
    right_tot=0
    for j in range(len(S)):
        if S[j]==")":
            left_tot += 1
        else:
            right_tot += 1
    left_bt = left_tot - left
    right_bt = right_tot - right
    if left_bt > right_bt:
        left += (left_bt-right_bt)
    elif left_bt < right_bt:
        right += (right_bt-left_bt)
    braket.append([left,right])
    if left==0:
        left_flag=1
    if right==0:
        right_flag=1
    if left==0 or right==0:
        tot_flag += 1
    sum_braket += right - left
    
if tot_flag >= 2 and sum_braket==0:
    print("Yes")
else:
    print("No")
#print(braket)

Submission status: Wrong Answer

Solution code:
def no():
    print("No")
    exit()

def yes():
    print("Yes")
    exit()

n = int(input())
def change(string):
    return [1 if c == "(" else -1 for c in string]
s = [change(input()) for i in range(n)]
t = []
k = 0
for si in s:
    minimum = 0
    cur = 0
    for c in si:
        cur += c
        if minimum > cur:
            minimum = cur
    if minimum == 0:
        k += cur
    else:
        t.append((minimum, cur))

t.sort(key = lambda x: (-x[0], -x[1]))
nxt = []
for ti in t:
    x,y = ti
    if y>=0 and k+x>=0:
        k += y
    else:
        nxt.append(ti)

if any(y >= 0 for x,y in nxt):
    no()

if -sum(y for x,y in nxt) != k:
    no()

nxt.sort(key=lambda x: (x[0], -x[1]))
for x,y in nxt:
    if k+x < 0:
        no()
    k += y

if k == 0:
    yes()
else:
    no()

Submission status: Wrong Answer

Solution code:

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()
if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    i = n-1
    while minsum:
        m, s = minsum[i]
        if m<0:
            break
        c += s
        i -= 1
        minsum.pop()
    minsum.sort(key=lambda x: x[1])
#     print(minsum, c)
    i = len(minsum)-1
    while minsum:
        m, s = minsum[i]
        if c+m>=0:
            minsum.pop(i)
            c += s
            i = len(minsum) - 1
        else:
            i -= 1
            if i<0:
                print("No")
                break
    else:
        print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    tp = 0 
    tm = []
    left = 0
    right = 0
    for i in range(N):
        S = input()
        w = 0
        wl = 0
        l = 0
        r = 0
        for j in S:
            if j == '(':
                l += 1
                wl += 1
            else:
                r += 1
                w -= 1
                w += wl
                wl = 0
        left += l
        right += r
        if w >= 0:
            tp += (l - r)
        else:
            tm.append((l - r, -w))
    if left != right:
        return False
    tm.sort(reverse=True)
    while tm:
        tmp = []
        for i in tm:
            if i[1] <= tp:
                tp += i[0]
                if tp < 0:
                    return False
            else:
                tmp.append(i)
        if len(tmp) == len(tm):
            return False
        tm = tmp
    return True
if main():
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = [input() for i in range(n)]
    s = []
    for i in range(n):
        k = []
        p = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            k.append(p)
        s.append((k,min(k),p))
    if sum([p for (k,a,p) in s]) != 0:
        print("No")
        return
    s.sort(key = lambda x:-x[1])
    k = 0
    for _,m,p in s:
        if k+m < 0:
            print("No")
            return
        k += p
    print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
data=[]

class newint(object):
    def __init__(self, mini, dif):
        #オブジェクトの定義
        self.mini = mini
        self.dif = dif

    def __lt__(self, other):
        # 比較演算子
        K=(min(self.dif-other.mini,self.mini))-min((other.mini,other.dif-self.mini))
        if K>=0:
            return True
        elif K<0:
            return False
            
          
        else:
            return False
    def __repr__(self):
        return repr((self.name, self.age))

for i in range(N):
    s=list(input())
    dif=0
    maxi=0
    mini=0
    for j in range(len(s)):
        if s[j]=="(":
            dif+=1
        else:
            dif-=1
        mini=min(mini,dif)        
    data.append(newint(mini,dif))
data.sort()
flag=True
sums=0
for some in data:
    mini,dif=some.mini,some.dif
    if sums+mini<0:
        flag=False
        break 
    else:
        sums+=dif
if flag and sums==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
b = 0
e = 0
for i in range(n):
    s = input()
    i_b = 0
    i_e = 0
    for j in s:
        if j == "(":
            i_b += 1
        else:
            if i_b > 0:
                i_b -= 1
            else:
                i_e += 1

    if i_b != 0 and i_e != 0:
        if b > e:
            if b >= i_e:
                b -= i_e
            else:
                i_e -= b
                b = 0
                e += i_e

        else:
            if e >= i_b:
                e -= i_b
            else:
                i_b -= e
                e = 0
                e += i_b
    elif i_b == 0:
        if b >= i_e:
            b -= i_e
        else:
            i_e -= b
            b = 0
            e += i_e
    elif i_e == 0:
        if e >= i_b:
            e -= i_b
        else:
            i_b -= e
            e = 0
            b += i_b

if b == e == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys

pos, neg = [], []
n = int(input())
for i in range(n):
    s = input()
    bal = 0
    min_bal = 0
    for c in s:
        bal += 1 if c == '(' else -1
        min_bal = min(bal, min_bal)

    if bal >= 0:
        pos.append((min_bal, bal))
    else:
        neg.append((min_bal, bal))

pos.sort(reverse=True)
neg.sort(key = lambda p: (p[0], -p[1]))

cur = 0
for m, e in pos:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

for m, e in neg:
    if cur + m < 0:
        print("No")
        sys.exit()

    cur += e

print("Yes" if cur == 0 else "No")

Submission status: Wrong Answer

Solution code:
n = int(input())
left_left = []
left_right = []
right_left = []
right_right = []
left = 0
right = 0

for i in range(n):
    S = input()
    l = len(S)
    left += S.count('(')
    right+= S.count(')')
    if S[0] == '(':
        if S[l - 1] == '(':
            left_left.append(S.count('(') - S.count(')'))
        else:
            left_right.append(S.count('(') - S.count(')'))
    else:
        if S[l - 1] == '(':
            right_left.append(S.count('(') - S.count(')'))
        else:
            right_right.append(S.count('(') - S.count(')'))
if left != right:
    print('No')
else:
    sum_ll = sum(left_left)
    sum_lr = sum(left_right)
    sum_rl = sum(right_left)
    sum_rr = sum(right_right)
    if sum_ll + sum_lr == -(sum_rl + sum_rr):
        if len(left_left) == 0 and len(right_right) == 0:
            print('No')
        else:
            print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n = I()
m = SR(n)
A = []
L = 0
R = 0
for b in m:
    l = 0
    r = 0
    m = []
    flg = 0
    for a in b:
        if flg and a == ')':
            r -= 1
        elif a == '(':
            r += 1
        else:
            l += 1
    A += [(l, r)]
    L += l
    R += r


if L != R:
    print('No')
else:
    A.sort()
    ret = 0
    for c, d in A:
        if c > ret:
            print('No')
            break
        ret -= c
        ret += d
    else:
        print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import deque

(N,) = [int(x) for x in input().split()]
brackets = [input() for i in range(N)]

delta = []
minDelta = []
for s in brackets:
    balance = 0
    mn = 0
    for c in s:
        if c == "(":
            balance += 1
        else:
            balance -= 1
        mn = min(mn, balance)
    delta.append(balance)
    minDelta.append(mn)

if sum(delta) == 0:
    # Want to get balance as high as possible
    # Take any positive delta first as long there's enough balance to absorb their minDelta
    # Can sort since any that works will only increase balance and the ones with worse minDelta comes last
    posIndices = [i for i in range(N) if delta[i] > 0]
    posIndices.sort(key=lambda i: -minDelta[i])

    # At the top can take all with delta zero
    eqIndices = [i for i in range(N) if delta[i] == 0]

    # When going back down, want to absorb any with large minDelta first while not eroding balance too quickly
    negIndices = [i for i in range(N) if delta[i] < 0]
    negIndices.sort(key=lambda i: (minDelta, -delta[i]))

    balance = 0
    for i in posIndices + eqIndices + negIndices:
        if balance + minDelta[i] < 0 or balance + delta[i] < 0:
            print("No")
            exit()
        balance += delta[i]
    assert balance == 0

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