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:
n = int(input())
List = []
flg_l = []
flg_r = []
sum = 0
for _ in range(n):
    s = input()
    left = 0
    tmp = 0
    for i in range(len(s)):
        if s[i] == ')':
            tmp += 1
        else:
            tmp -= 1
        left = max(left, tmp)
    right = 0
    tmp = 0
    for i in range(len(s)):
        if s[len(s)-1-i] == '(':
            tmp += 1
        else:
            tmp -= 1
        right = max(right, tmp)

    sum += right - left
    List.append((left, right))

if sum == 0 and len(flg_l) > 0 and len(flg_r) > 0:
    if len(flg_l) == 1 and len(flg_r) == 1 and flg_l == flg_r:
        print('No')
    else:
        print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys

sys.stdin.readline

N=int(input())


cand=[]
right=[]
left=[]
for _ in range(N):
    moji=input()
    if moji.count(")")-moji.count("(")>=0:
        right.append(moji)
    else:
        left.append(moji)
mx_r=[]
for item in right:
    mx=10**9
    temp=0
    for moji in item:
        if moji=="(":
            temp+=1
        else:
            temp-=1
        #print(temp)
        mx=min(temp,mx)
    mx_r.append([mx,item])

mx_l=[]
for item in left:
    mi=-10**9
    temp=0
    for moji in item:
        #print(temp)
        if moji=="(":
            temp+=1
        else:
            temp-=1
        mi=max(temp,mi)
    mx_l.append([mi,item])

mx_l.sort(key=lambda x:x[0],reverse=True)
mx_r.sort(key=lambda x:x[0],reverse=True)

#print(mx_r,mx_l)    

ans=""
for item in mx_l:
    ans+=item[1]
for item in mx_r:
    ans+=item[1]
#print(ans)

temp=0
for item in ans:
    if item=="(":
        temp+=1
    else:
        temp-=1
    if temp<0:
        print("No")
        exit()
if temp==0:
    print("Yes")
else:
    ans="("+ans+")"
    for item in ans:
        if item=="(":
            temp+=1
        else:
            temp-=1
        if temp<0:
            print("No")
            exit()
    print("No")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, S: "List[str]"):

    count = [[] for _ in range(N)]

    for i in range(N):
        r = 0
        l = 0
        for s in S[i]:
            if s == '(':
                l += 1
            else:
                r += 1
        count[i].append(l)
        count[i].append(r)
    
    count_sorted = sorted(enumerate(count),key = lambda x: -x[1][0])

    new_s = []
        
    def isvalid(s):
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}


        for char in s:

            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        return not stack

    for index,_ in count_sorted:
        new_s.append(S[index])
    
    if isvalid(''.join(new_s)):
        print(YES)
    else:
        print(NO)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [input() for _ in range(N)]
L = []
start = False
end = False
left_sum = 0
right_sum = 0

good_left_sum = 0
good_right_sum = 0
normal_left_sum = 0
normal_right_sum = 0
max_block = 0

for i in S:
    l_join = 0
    r_join = 0
    for j in i:
        if j == '(':
            r_join += 1
        else:
            if r_join > 0:
                r_join -= 1
            else:
                l_join += 1
    if r_join == 0 and l_join == 0:
        continue
    left_sum += l_join
    right_sum += r_join
    if r_join == 0:
        end = True
        good_left_sum += l_join
    elif l_join == 0:
        start = True
        good_right_sum += r_join
    elif r_join == l_join:
        max_block = max(max_block, r_join)
    elif r_join > l_join:
        normal_right_sum += r_join - l_join
    elif r_join < l_join:
        normal_right_sum += l_join - r_join
    # L.append((l_join, r_join))
# print(L)
# print(start)
# print(end)
if not((left_sum == right_sum) and start and end):
    print('No')
    exit()
if (normal_right_sum + good_right_sum >= max_block) and (normal_left_sum + good_left_sum >= max_block):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# MOD = 10**9+7
# MOD = 998244353


def count(idx, s):
    left = right = 0
    for i in range(len(s)):
        if s[i] == "(":
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                right += 1

    return left, right, idx


n = int(input())
S = [input() for i in range(n)]
A = [count(i, s) for i, s in enumerate(S)]
B = sorted(A, key=lambda x: (x[1], x[1]-x[0]))
C = sorted(A, key=lambda x: (x[1]-x[0], x[1]))
used = [False]*n

left_rem = 0
bi = ci = 0
while bi < n and ci < n:
    while ci < n and used[C[ci][2]]:
        ci += 1
    while bi < n and used[B[bi][2]]:
        bi += 1
    if ci == n or bi == n:
        break

    if C[ci][1] <= left_rem:
        left_rem += C[ci][0] - C[ci][1]
        used[C[ci][2]] = True
        ci += 1

    elif B[bi][1] <= left_rem:
        left_rem += B[bi][0] - B[bi][1]
        used[B[bi][2]] = True
        bi += 1

    else:
        print("No")
        exit()

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

if left_rem == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
op = []
ed = []
mid = [0]
dg = 10**7

for _ in range(N):
    s = list(input())
    n = len(s)-1
    a,b,st = 0,0,0
    for e in s:
        if e == '(':
            st += 1
        elif e == ')':
            if st > 0:
                st -= 1
            else:
                a += 1
    st = 0
    for i in range(n-1,-1,-1):
        if s[i] == ')':
            st += 1
        else:
            if st > 0:
                st -= 1
            else:
                b += 1
    if a > b:
        ed.append(b**dg + a)
    elif a == b:
        mid.append(a)
    else:
        op.append(a**dg + b)

op.sort()
ed.sort()
p = 0
for e in op:
    a,b = divmod(e,dg)
    if p < a:
        print('No')
        exit()
    p += b-a

q = 0
for e in ed:
    b,a = divmod(e,dg)
    if q < b:
        print('No')
        exit()
    q += a-b

if p == q and p >= max(mid):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [[self.ide_ele, i] for i in range (2*self.num)]
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele,0
        p += self.num-1
        q += self.num-2
        res = [self.ide_ele, self.ide_ele] 
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N = Int()
Sum = 0

Min = []
Now = []

for i in range(N):
    s = rl()
    now = 0
    minimum = 0
    for j in s:
        if j=='(':
            now += 1
        elif j == ')':
            now -= 1
        minimum = min(minimum,now)
    Sum += now
    Min.append(minimum)
    Now.append([now, i])
    #A.append([minimum,now])

#print(A)
# zipで二つの配列を統合
c = zip(Min, Now)
# 統合していた配列をもとに戻す
Min, Now = zip(*sorted(c))
    
if Sum!=0:
    print('No')
    sys.exit()

INF = 10**7
ide_ele = -INF
Seg = SegTree(Now,ide_ele,max)

import bisect

count = 0
now = 0

#print(Min)
#print(Now)

for _ in range(N):
    i = bisect.bisect_left(Min,-now)
    #print(i,N)
    j,k = Seg.query(i, N)
    
    #print(j)
    now += j
    Seg.update(k,[-INF,k])
    
    if now<0:
        print('No')
        sys.exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

def calc(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        elif s == ')':
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = s.count(')')
        if l >= r:
            P.append((less, s))
        else:
            L.append((less, s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]
ans = ''.join(H) + ''.join(P) + ''.join(L)

l = ans.count('(')
r = ans.count(')')

if l == r and calc(ans) == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp[0] = m
        temp[1] = (s.count("(")-s.count(")"))
        if temp[1] >= 0:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: -x[0])
    s3.sort(key=lambda x: x[1])
    cnt = 0
    for i, j in s2:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        if cnt+i < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = 0
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(":
      t += 1
      rs[x] += 1
    if S[i] == ")":
      t -= 1
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
if t:
  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:
  print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[input() for i in range(N)]
dl,dr,dml,dmr=0,0,0,0
f=0
for i,s in enumerate(S):
    l,r=0,0
    for c in s:
        if c=='(':
            l+=1
        else:
            if l>0:l-=1
            else: r+=1
    if l>0 and r>0:
        x=min(dml,r)
        dml-=x
        dml+=l
        dmr-=r-x
        f=1
    elif l>0:
        dl+=l
    elif r>0:
        dr-=r
print(['No','Yes'][dl+dr+dml+dmr==0 and (f==0 or dl+dmr>=0)])

Submission status: Wrong Answer

Solution code:
N = int(input())
LR = [[0]*2 for i in range(N)]
for i in range(N):
    S = input()
    M = len(S)
    L = 0
    R = 0
    R0 = 0
    t = 0
    if S[0]==")":
        while t<M:
            if S[t]==")":
                R0+=1
                t+=1
            else:
                t+=1
                break
    while t<M:
        if S[t]=="(":
            t+=1
            L+=1
        else:
            t+=1
            R+=1
    if L>R:
        LR[i][0]=L-R
        LR[i][1]=R0
    if L<R:
        LR[i][0]=0
        LR[i][1]=R0+R-L
    if L==R:
        LR[i][0]=0
        LR[i][1]=R0

LP = 0
RP = 0
minLS = float('inf')
minRS = float('inf')
LS = 0
RS = 0
for i in range(N):
    L = LR[i][0]
    R = LR[i][1]
    if (L==0)and(R==0):
        continue
    elif L==0:
        RP += R
    elif R==0:
        LP += L
    else:
        LS += L
        RS += R
        if LS < minLS:
            minLS = LS
        if RS < minRS:
            minRS = RS

if (LP==RP)and(LS==0)and(RS==0):
    print("Yes")

else:
    LS += -1*LP
    RS += -1*RP
    if (LS<0)and(RS<0)and(LS%2==RS%2):
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for i in range(n):
    temp = input()
    count = 0
    min_count = 0
    for j in temp:
        if j == "(":
            count += 1
        else:
            count -= 1
            min_count = min(min_count, count)
    s.append([count, min_count])
sum_count = sum([s[i][0] for i in range(n)])
if sum_count != 0:
    print("No")
else:
    s2 = [s[i] for i in range(n) if s[i][0] >= 0]
    s3 = [s[i] for i in range(n) if s[i][0] < 0]
    s2.sort(key = lambda x: x[1], reverse = True)
    s3.sort(key = lambda x: x[1])
    flag = True
    count = 0
    for i in range(len(s2)):
        if count + s2[i][1] < 0:
            flag = False
            break
        else:
            count += s2[i][0]
    for i in range(len(s3)):
        if count + s3[i][1] < 0:
            flag = False
            break
        else:
            count += s3[i][0]
    if flag == True:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

n=int(input())
l=[]
for i in range(n):
    l.append(list(input()))

p=0
q=0
for i in range(n):
    for j in l[i]:
        if j=='(':
            p+=1
        else:
            q+=1
if p!=q:
    print('No')
    exit()
pl=[]
ql=[]
ml=[]
for i in range(n):
    a=l[i]
    p=0
    q=0
    for j in a:
        if j=='(':
            p+=1
        else:
            q+=1
    if p>q:
        pl.append(a)
    elif p<q:
        ql.append(a)
    else:
        ml.append(a)
# if pl:
#     pl.sort()
# if ql:
#     ql.sort()
# if ml:
#     ml.sort()
# if pl:
#     if pl[0][0]==')':
#         print('No')
#         exit()
# else:
#     if ml[0][0]==')':
#         print('No')
#         exit()

# if ql:
#     if ql[-1][-1]=='(':
#         print('No')
#         exit()
# else:
#     if ml[-1][-1]=='(':
#         print('No')
#         exit()


if pl:
    pp=[]
    for i in pl:
        d=0
        t=0
        for j in i:
            if j=='(':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    d=0
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a
if ql:
    pp=[]
    for i in ql:
        d=0
        t=0
        for j in range(len(i)):
            if i[len(i)-1-j]==')':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    d=0
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a

print('Yes')

Submission status: Wrong Answer

Solution code:
import itertools

n=int(input())
S=[]
for i in range(n):
    s=input()
    count=0
    mins=0
    for j in range(len(s)):
        if s[j]=='(':
            count+=1
        elif s[j]==')':
            count-=1
            if count<mins:
                mins=count
    S.append([count,mins*-1])
    
S.sort(reverse=True)

count=0
flag=True

for i in range(n):
    if count>=S[i][1]:
        count+=S[i][0]
    else:
        flag=False
        break

if flag and count==0:
    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 len(double) != 0:
    if not left or not right:
        print("No")
        exit()
else:
    if left == right:
        print("Yes")
        exit()
double.sort(key=lambda x: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:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
stack=[]
idleR=10**7
if lr:
    L,R=lr[0]
    stack=[[L,R]]
    for n in range(1,len(lr)):
        #print(stack)
        L,R=lr[n]
        visited=set()
        nstack=[]
        while stack:
            l,r=stack.pop()
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in visited:
                        visited.add(X)
                        nstack.append([xl,xr])
if not stack:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

for l,r in stack:
    if l-llst==0 and r-rlst==0:
        print("Yes")
        exit()
print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

right = False
left = False

right_sum = 0
left_sum = 0

for i in range(N):
    S = input()
    br_q = deque()
    for s_index, c in enumerate(S):
        br_is_right = (c == "(")
        if len(br_q) == 0:
            br_q.append(br_is_right)
        else:
            if br_q[-1] and not br_is_right:
                br_q.pop()
            else:
                br_q.append(br_is_right)
    right_count = 0
    left_count = 0
    for is_right in br_q:
        if is_right:
            right_count += 1
        else:
            left_count += 1
    right_sum += right_count
    left_sum += left_count
    if right_count == 0 and not left:
        left = True
    elif left_count == 0:
        right = True

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

Submission status: Wrong Answer

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

def count(s):
    n = len(s)
    n1 = 0
    n2 = 0
    for i in range(n):
        if s[i]=='(':
            n2 += 1
        else:
            if n2 > 0:
                n2 -= 1
            else:
                n1 += 1
    return n1,n2

l = []
for i in range(N):
    n1,n2 = count(S[i])
    if n1+n2!=0:
        l.append([n1,n2])

l.sort(key=lambda x:x[1]-x[0])
l.sort(key=lambda x:x[0])

N = len(l)
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [[INF,INF,INF]]*(4*N0)

def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])


def query(l, r):
    L = l + N0; R = r + N0
    s = [INF,INF,INF]
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

d = []
for i in range(N):    
    a,b = l[i]
    d.append(a)
    update(i, [a-b,a,i])

ans = True
n = 0
for i in range(N):
    i = bisect(d,n)-1
    c,a,i = query(0,i+1)
    if c == INF:
        ans = False
        break
    if n < a:
        ans = False
        break
    update(i,[INF,a,i])
    n -= c
if n!=0:
    ans = False
if ans:
    ans = 'Yes'
else:
    ans = 'No'
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = []
for _ in range(n):
  s = input()
  state = [0,0]
  for c in s:
    if c == ')' and state[1]==0:
      state[0] += 1
    elif c ==')':
      state[1] -= 1
    elif c == '(':
      state[1] += 1
      
  S.append(state)
x,y = S[0]
for l,r in S[1:]:
  if x<y:
    y -= l
    if y<0:
      x-=y
      y = r
  else:
    x -= r
    if x<0:
      y-=x
      x = l
if x ==0 and y==0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
check = []
same = 0
another = 0
total_left_count = 0
total_right_count = 0
for i in range(N):
  S = input()
  check.append(S)
for i in check:
  if len(i) > 1:
    if i[0] == '(' and i[len(i)-1] == ')':
      total_left_count += 1
      total_right_count += 1
      same += 1
    elif i[0] == '(' and i[len(i)-1] == ')':
      total_right_count += 1
      total_left_count += 1
      same += 1
    else:
      if i[0] == '(':
        total_left_count += 1
        another += 1
      if i[len(i)-1] == ')':
        total_right_count += 1
        another += 1
  else:
    num = another
    if i[0] == '(':
      total_left_count += 1
      another += 1
    if i[len(i)-1] == ')' and num == another:
      total_right_count += 1
      another += 1
      
if same == 0 and another == 0:
  print('No')
elif same % 2 == 0 and another % 2 == 0:
  print('Yes')
elif same % 2 != 0 and another % 2 == 1:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
print("Yes")

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csr_matrix, csgraph
N = int(input())
lefts, rights = [], []
count = 0
indices = {}
ind = 0
for i in range(N):
    left, right = 0, 0
    for c in input():
        if c == "(":
            left += 1
        if c == ")":
            if left:
                left -= 1
            else:
                right += 1
    if any((left, right)):
        count += 1
        try:
            lind = indices[left]
        except:
            indices[left] = ind
            lind = ind
            ind += 1
        try:
            rind = indices[right]
        except:
            indices[right] = ind
            rind = ind
            ind += 1
        lefts.append(lind)
        rights.append(rind)
graph = csr_matrix(([1] * count, (lefts, rights)), shape=(ind, ind))
if (csgraph.connected_components(graph, return_labels=False) == 1):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())

ba = 0
flag1 = 0
flag2 = False
flag3 = False
for _ in range(n):
    s = input()
    for i in s:
        if i == "(":
            ba += 1
        else:
            ba -= 1
    if s[0] == "(" and s[-1] == ")":
        flag1 += 1
    elif s[0] == "(":
        flag2 = True
    elif s[-1] == ")":
        flag3 = True
if ba != 0:
    print("No")
else:
    if flag2:
        if flag3 or (flag1 > 0):
            print("Yes")
        else:
            print("No")
    else:
        if (flag1 > 1) or (flag3 and (flag1 > 0)):
            print("Yes")
        else:
            print("No")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    return 'No'
    l = []
    r = []
    b = [[0, 0]]
    for s in S:
        stack = []
        for c in s:
            if c == '(':
                stack.append('(')
            else:
                if stack and stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(')')
        lc = stack.count('(')
        rc = stack.count(')')
        if lc != 0 and rc != 0:
            b.append([lc, rc])
        elif lc != 0:
            l.append(lc)
        elif rc != 0:
            r.append(rc)

    if sum(l) != sum(r):
        return 'No'

    sl = sum(l)
    sr = sum(r)
    b.append([sl, 0])
    b.append([0, sr])
    b.sort(key=lambda x: x[1]-x[0])

    while len(b) > 1:
        x = b.pop()
        y = b.pop()
        if x[1] - x[0] < y[1] - y[0]:
            x, y = y, x
        if x[1] < y[0]:
            z = [x[0] + y[0]-x[1], y[1]]
        else:
            z = [x[0], x[1]-y[0] + y[1]]
        b.append(z)

    if b[0][0] == 0 and b[0][0] == 0:
        return 'Yes'

    return 'No'


def main():
    N = read_int()
    S = [read_str() for _ in range(N)]
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
left = 0
right = 0
mid_right = 0
mid_left = 0
mid = 0

for _ in range(N):
	s = input()
	L = len(s)
	while True:
		s = s.replace('()', '')
		tmp = len(s)
		if tmp == L:
			break
		else:
			L = tmp
	
	if s:
		if L == 1:
			if s == '(':
				left += 1
			else:
				right += 1
		elif L > 1:
			if s[0] == s[-1]:
				if s[0] == '(':
					left += L
				else:
					right += L
			else:
				mid = 1
				for i in range(L):
					if s[i] == '(':
						mid_right += i
						mid_left += (L - i)
						break

if mid:
	if 0 in [right, left]:
		print('No')
	else:
		if (mid_left + left) == (mid_right + right):
			print('Yes')
		else:
			print('No')
else:
	if right == left:
		print('Yes')
	else:
		print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
s_s = []
for i in range(n):
  l = 0
  r = 0
  cur = 0
  s = input()
  for j in s:
    if j == '(':
      l += 1    
    else:
      if l >= 1:
        l -= 1
      else:
        r += 1
  s_s.append( (l, r) )

s_s.sort(key=lambda ss: ss[1])
print(s_s)

failed = False
b = 0
ll = 0
rr = 0
for s in s_s:
  b -= s[1]
  if b < 0:
    failed = True
    break
  b += s[0]
  
if failed:
  ans = 'No'
else:
  if b == 0:
    ans = 'Yes'
  else:
    ans = 'No'

print(ans)

Submission status: Wrong Answer

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

for i, s in enumerate(S):
    current_len = len(s)
    while True:
        s = s.replace('()', '')
        if len(s) == current_len:
            S[i] = s
            break
        current_len = len(s)
cnt_1 = 0
cnt_2 = 0
for s in S:
    if len(s) == 0:
        continue
    if s[0] == ')':
        cnt_1 += len(s)
    elif s[0] == '(':
        cnt_2 += len(s)
if cnt_1 == cnt_2:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

import collections
buf = collections.deque()

def solve(S):
    for s in S:
        if buf:
            if s == ')':
                if buf[0] == '(':
                    buf.popleft()
                else:
                    buf.appendleft(s)

            else:
                buf.appendleft(s)

        else:
            buf.appendleft(s)

    ret = []
    while buf:
        ret.append(buf.pop())

    return ''.join(ret)


S = [solve(input()) for _ in range(N)]
S.sort()
S = ''.join(S)
if len(solve(S)) == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def kton(S):
    r = 0
    m = 0
    for s in S:
        r += 1 if s == '(' else -1
        m = min(m, r)
    return r, m
        
def main():
    N = int(input())
    RM = [kton(input()) for _ in range(N)]
    pos = 0
    negp = []
    negn = []
    posn = []
    for r, m in RM:
        if m < 0:
            if r >= 0:
                negp.append((-m, r))
            else:
                negn.append((-(-r+m), -r, m))
        else:
            pos += r

    negp.sort()
    for m, r in negp:
        if pos - m < 0:
            return False
        pos += r
    negn.sort()
    for _, r, m in negn:
        if pos + m < 0:
            return False
        pos -= r
    return pos == 0

print('Yes' if main() else 'No')

Submission status: Wrong Answer

Solution code:
N = int(input())

cnt = 0
start = 0
goal = 0
kanpeki = 1
for _ in range(N):
    S = input()
    k = 0
    for i in S:
        if i == "(":
            k += 1
        else:
            k -= 1
        if k < 0:
            kanpeki = 0       
    cnt += k
    if S[0] == "(" and k > 0:
        start = 1
    if S[-1] == ")" and k < 0:
        goal = 1

if kanpeki == 1:
    print("Yes")
elif cnt == 0 and start == 1 and goal == 1:
    print("Yes")
else:
    print("No")