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())
S = [input() for i in range(n)]
MX = []
for i in range(n):
    m, x = 0, 0
    for c in S[i]:
        if c == '(':
            x += 1
        if c == ')':
            x -= 1
            m = min(m, x)
    MX.append((m, x))
MX.sort(reverse=True)
m0, x0 = 0, 0
for m, x in MX:
    m0, x0 = min(m0, x0 + m), x0 + x
    if m0 < 0:
        print('No')
        exit()
if x0 == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for i in range(n)]
MX = []
for i in range(n):
    m, x = 0, 0
    for c in S[i]:
        if c == '(':
            x += 1
        if c == ')':
            x -= 1
            m = min(m, x)
    MX.append((m, x))
MX.sort(reverse=True)
m0, x0 = 0, 0
for m, x in MX:
    m0, x0 = min(m0, x0 + m), x0 + x
if m0 >= 0 and x0 == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
x, y = [], []
for _i in range(n):
    s = input()
    p = 0
    m = [0]
    for j in range(len(s)):
        if s[j]=="(":
            p += 1
        else:
            p -= 1
            m.append(p)
    l = min(m)
    if p > 0:
        x.append([l, p])
    else:
        y.append([l, p])
x.sort(reverse=True)
y.sort()
r = 0
for s, t in x:
    if r+t < 0:
        print("No")
        sys.exit()
    r += t
for s, t in y:
    if r+t < 0 or r+s < 0:
        print("No")
        sys.exit()
    r += t
if r==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n-m]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort(reverse=1)
mab.sort(key=lambda x:x[1])
#print(pab)
#print(mab)
ab=pab+mab
n=0
for a,b in ab:
  n+=a
  if n<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('No')

Submission status: Wrong Answer

Solution code:
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n-m]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort(reverse=1)
mab.sort(key=lambda x:x[0]-x[1],reverse=1)
#print(pab)
#print(mab)
ab=pab+mab
n=0
for a,b in ab:
  n+=a
  if n<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('No')

Submission status: Wrong Answer

Solution code:
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n-m]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort(reverse=1)
mab.sort()
#print(pab)
#print(mab)
ab=pab+mab
n=0
for a,b in ab:
  n+=a
  if n<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('No')

Submission status: Wrong Answer

Solution code:
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n-m]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort(reverse=1)
mab.sort(reverse=1)
#print(pab)
#print(mab)
ab=pab+mab
n=0
for a,b in ab:
  n+=a
  if n<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('No')

Submission status: Wrong Answer

Solution code:
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n-m]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort()
mab.sort(reverse=1)
ab=pab+mab
n=0
for a,b in ab:
  n+=a
  if n<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('No')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# import numpy as np
# import matplotlib.pyplot as plt
# from matplotlib.image import imread
def init():
    global N, Sp, Sm
    N = int(input())
    Sp = []
    Sm = []
    for i in range(N):
      l = input()
      u = 0
      h = 0
      for j in range(len(l)):
        if l[j] == '(':
          h += 1
        else:
          h -= 1
        if h < u:
          u = h
      if h >= 0:
        Sp.append([u, h])
      else:
        Sm.append([u-h, -h])
    Sp.sort(reverse=True)
    Sm.sort(reverse=True)

def main():
  init()
  print(Sp, Sm)
  p = check(Sp)
  m = check(Sm)
  if p != -1 and m != -1 and p ==m:
    print('Yes')
  else:
    print('No')

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

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def checker(x):
    l = x.count('(', 1, -1)
    r = len(x[1:-1]) - l
    if l != r: return 0

    sum = 0
    for c in x:
        if c == '(':
            sum = sum + 1
        else:
            sum = sum - 1
        if sum < 0: return 0
    if sum != 0 : return 0

    return 1

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

    sorted_s = sorted(s)
    jud = checker(''.join(sorted_s))

    if jud == 1:
        print('Yes')
    else:
        print('No')
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def check(DR):
    D = 0
    for dr in DR:
        dmin, d = dr
        if D + dmin < 0:
            return False
        D += d
    return True

def main():
    N = int(input())
    S = [ input() for i in range(N) ]
    DR1 = []
    DR2 = []
    total = 0
    for s in S:
        d = 0    # ["(" の数]  - [")" の数]
        d_min = 0 # ")" が最も深くなるときの ")" の数
        # d_min <= d
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                d_min = min(d, d_min)
        total += d
        if d > 0:
            DR1.append((d_min, d))
        else:
            DR2.append((d_min - d, -d))

    # d_minの大きい順に並べ替える
    DR1.sort()
    DR2.sort()
    if check(DR1) and check(DR2) and sum([d[1] for d in DR1]) == sum([d[1] for d in DR2]):
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
def check(DR):
    D = 0
    for dr in DR:
        dmin, d = dr
        if D + dmin < 0:
            return False
        D += d
    return True

def main():
    N = int(input())
    S = [ input() for i in range(N) ]
    DR1 = []
    DR2 = []
    total = 0
    for s in S:
        d = 0    # ["(" の数]  - [")" の数]
        d_min = 0 # ")" が最も深くなるときの ")" の数
        # d_min <= d
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                d_min = min(d, d_min)
        total += d
        if d > 0:
            DR1.append((d_min, d))
        else:
            DR2.append((d_min - d, -d))

    # print(DR)
    # 戦略
    # 1. d = 0とする
    # 2. d + d_min >= 0 となるものを選択
    #    選択後、d += di とする

    # d_minの大きい順に並べ替える
    DR1.sort()
    DR2.sort()
    if check(DR1) and check(DR2) and total == 0:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

    grads_positive = list()
    grads_negative = list()

    total = 0
    for brackets in brackets_gen:

        elevation, bottom = 0, 0

        for bk in brackets:

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

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

        total += elevation

    if total != 0:
        return False

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

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

        return True

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


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def check(DR):
    D = 0
    for dr in DR:
        dmin, d = dr
        if D + dmin < 0:
            return False
        D += d
    return True

def main():
    N = int(input())
    S = [ input() for i in range(N) ]
    DR1 = []
    DR2 = []
    total = 0
    for s in S:
        d = 0    # ["(" の数]  - [")" の数]
        d_min = 0 # ")" が最も深くなるときの ")" の数
        # d_min <= d
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                d_min = min(d, d_min)
        total += d
        if d > 0:
            DR1.append((d_min, d))
        else:
            DR2.append((d - d_min, -d))

    # print(DR)
    # 戦略
    # 1. d = 0とする
    # 2. d + d_min >= 0 となるものを選択
    #    選択後、d += di とする

    # d_minの大きい順に並べ替える
    DR1.sort()
    DR2.sort()
    if check(DR1) and check(DR2) and total == 0:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

    grads_positive = list()
    grads_negative = list()

    for brackets in brackets_gen:

        elevation, bottom = 0, 0

        for bk in brackets:

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

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

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

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

        if elevation == 0:
            return True
        else:
            return False

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


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def check(DR):
    D = 0
    for dr in DR:
        dmin, d = dr
        if D + dmin < 0:
            return False
        D += d
    return True

def main():
    N = int(input())
    S = [ input() for i in range(N) ]
    DR1 = []
    DR2 = []
    total = 0
    for s in S:
        d = 0    # ["(" の数]  - [")" の数]
        d_min = 0 # ")" が最も深くなるときの ")" の数
        # d_min <= d
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                d_min = min(d, d_min)
        total = 0
        if d > 0:
            DR1.append((d_min, d))
        else:
            DR2.append((d - d_min, -d))

    # print(DR)
    # 戦略
    # 1. d = 0とする
    # 2. d + d_min >= 0 となるものを選択
    #    選択後、d += di とする

    # d_minの大きい順に並べ替える
    DR1.sort()
    DR2.sort()
    if check(DR1) and check(DR2) and total == 0:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


def check(DR):
    D = 0
    for dr in DR:
        d, r = dr
        if D + r < 0:
            return False
        D += d
    return True

def main():
    N = int(input())
    S = [ input() for i in range(N) ]
    DR1 = []
    DR2 = []
    total = 0
    for s in S:
        d = 0    # ["(" の数]  - [")" の数]
        d_min = 0 # ")" が最も深くなるときの ")" の数
        # d_min <= d
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                d_min = min(d, d_min)
        total = 0
        if d > 0:
            DR1.append((d_min, d))
        else:
            DR2.append((d - d_min, -d))

    # print(DR)
    # 戦略
    # 1. d = 0とする
    # 2. d + d_min >= 0 となるものを選択
    #    選択後、d += di とする

    # d_minの大きい順に並べ替える
    DR1.sort(key=lambda x: (-x[0], -x[1]))
    DR2.sort(key=lambda x: (-x[0], -x[1]))
    if check(DR1) and check(DR2) and total == 0:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def checker(x):
    l = x.count('(', 1, -1)
    r = len(x[1:-1]) - l
    if l != r: return 0

    sum = 0
    for c in x:
        print(c)
        if c == '(':
            sum = sum + 1
        else:
            sum = sum - 1
        if sum < 0:
            return 0
    if sum != 0 : return 0
    return 1

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

    sorted_s = sorted(s)
    jud = checker(''.join(sorted_s))

    if jud == 1:
        print('Yes')
    else:
        print('No')
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def checker(x):
    l = x.count('(', 1, -1)
    r = len(x[1:-1]) - l
    if l != r: return 0

    sum = 0
    for c in x:
        print(c)
        if c == '(':
            sum = sum + 1
        else:
            sum = sum - 1
        if sum < 0:
            return 0
    return 1

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

    sorted_s = sorted(s)
    jud = checker(''.join(sorted_s))

    if jud == 1:
        print('Yes')
    else:
        print('No')
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x.count('(', 1, -1)
    r = len(x[1:-1]) - l
    if l != r: return 0

    sum = 0
    for c in x:
        if c == '(':
            sum = sum + 1
        else:
            sum = sum - 1
        if sum < 0:
            return 0
    return 1

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

    sorted_s = sorted(s)
    jud = checker(''.join(sorted_s))

    if jud == 1:
        print('Yes')
    else:
        print('No')
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def main():
    N = int(input())
    S = [ input() for i in range(N) ]
    DR = []
    for s in S:
        d = 0    # ["(" の数]  - [")" の数]
        rmax = 0 # ")" が最も深くなるときの ")" の数
        # rmax <= d
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                rmax = min(d, rmax)

        DR.append((d, rmax))

    # print(DR)
    # 戦略
    # 1. d = 0とする
    # 2. d + rmax >= 0 となるものを選択
    #    選択後、d += di とする

    # rmaxの大きい順に並べ替える
    DR.sort(key=lambda x: (-x[1], x[0]))
    # print(DR)
    D = 0
    ans = 'Yes'
    for dr in DR:
        d, r = dr
        if D + r < 0:
            ans = 'No'
            break
        D += d
    
    if D != 0:
        ans = 'No'
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x.count('(', 1, -1)
    r = len(x[1:-1]) - l
    if l != r: return 0

    lm = x.count('(', 1, len(x) % 2)
    rm = x.count(')', 1, len(x) % 2)
    if lm != rm : return 0

    return 1

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

    sorted_s = sorted(s)
    jud = checker(''.join(sorted_s))

    if jud == 1:
        print('Yes')
    else:
        print('No')
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def check(p):
    H = 0
    for p0, p1 in p:
        B = H + p0
        if B < 0:
            return False
        H += p1
        return True


n = int(input())
ls = []
rs = []
total = 0
for i in range(n):
    s = input()
    h = 0
    b = 0
    for j in s:
        if j == "(":
            h += 1
        else:
            h -= 1
        b = min(b, h)
    if h > 0:
        ls.append([b, h])
    else:
        rs.append([b - h, -h])
ls.sort(reverse=True)
rs.sort(reverse=True)
if check(ls) and check(rs) and total == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

def brace_info(s):
    pp = 0
    nn = 0

    for c in s:
        if c == '(':
            nn += 1
        else:
            if nn > 0:
                nn -= 1
            else:
                pp += 1

    return (nn, pp)

brace_infos = [brace_info(ss) for ss in s]
braces = [b for b in brace_infos if b[0] != 0 and b[1] != 0]
braces.sort(key=lambda b: b[1]-b[0])
l_ba = sum(b[0] for b in brace_infos if b[1] == 0)
r_ba = sum(b[1] for b in brace_infos if b[0] == 0)

for l, r in braces:
    l_ba += (l-r)

if l_ba == r_ba:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

def brace_info(s):
    pp = 0
    nn = 0

    for c in s:
        if c == '(':
            nn += 1
        else:
            if nn > 0:
                nn -= 1
            else:
                pp += 1

    return (nn, pp)

brace_infos = [brace_info(ss) for ss in s]
braces = [b for b in brace_infos if b[0] != 0 and b[1] != 0]
braces.sort(key=lambda b: b[0]-b[1])
l_ba = sum(b[0] for b in brace_infos if b[1] == 0)
r_ba = sum(b[1] for b in brace_infos if b[0] == 0)

solved = False
for l, r in braces:
    if r > l_ba:
        print('No')
        solved = True
    else:
        l_ba += (l-r)

if not solved:
    if l_ba == r_ba:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
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()))
#for i in range(len(S)):
#    c=S[i]
#    S[i]=(c.count(")"),c.count("("))
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:
import sys
input = sys.stdin.readline


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

    grads_positive = list()
    grads_even = list()
    grads_negative = list()

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

        current_p = 0
        lowest_p = 0

        for s in S:
            if s == '(':
                current_p += 1
            elif s == ')':
                current_p -= 1
                lowest_p = min(lowest_p, current_p)

        if current_p > 0:
            grads_positive.append((lowest_p, current_p))
        elif current_p == 0:
            grads_even.append((lowest_p, 0))
        elif current_p < 0:
            grads_negative.append((lowest_p, current_p))

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

    current_p = 0
    for grad in grads_positive + grads_even + grads_negative:
        lowest_p = current_p + grad[0]
        if lowest_p < 0:
            return False
        current_p += grad[1]

    if current_p == 0:
        return True
    else:
        return False


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

# 改行区切りの入力を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 = [0] * n

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

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

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

# log(l_ok)
# log(r_ok)

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


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

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

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

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

print("Yes")
exit()

Submission status: Wrong Answer

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

min_revr, min_revl = 10**20, 10**20
left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack and stack[-1] == ')':
                stack.append('(')
                l = 1
            else:
                stack.append('(')
                l += 1
        else:   # s==')'
            if stack and stack[-1] == '(':
                stack.pop()
                l -= 1
            else:
                stack.append(')')
                r += 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
        min_revr = min(min_revr, rev_r)
        min_revl = min(min_revl, rev_l)
    # print('{} l:{} r:{} left:{} rev_l:{} rev_r:{} right:{}'.format(
        # S, l, r, left, rev_l, rev_r, right))

if min_revr == 10**20:
    min_revr = 0
if min_revl == 10**20:
    min_revl = 0

if left+rev_l == rev_r+right and left >= min_revr and min_revl <= right:
    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)
from heapq import heappush, heappop

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


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

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

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

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

print("Yes")

Submission status: Wrong Answer

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

min_revr, min_revl = 10**20, 10**20
left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack and stack[-1] == ')':
                stack.append('(')
                l = 1
            else:
                stack.append('(')
                l += 1
        else:   # s==')'
            if stack and stack[-1] == '(':
                stack.pop()
                l -= 1
            else:
                stack.append(')')
                r += 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
        min_revr = min(min_revr, rev_r)
        min_revl = min(min_revl, rev_l)
    # print('{} l:{} r:{} left:{} rev_l:{} rev_r:{} right:{}'.format(
        # S, l, r, left, rev_l, rev_r, right))

if left+rev_l == rev_r+right and left >= min_revr and min_revl <= right:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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


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

    grads_positive = list()
    grads_even = list()
    grads_negative = list()

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

        current_p = 0
        lowest_p = 0

        for s in S:
            if s == '(':
                current_p += 1
            elif s == ')':
                current_p -= 1
                lowest_p = min(lowest_p, current_p)

        if current_p > 0:
            grads_positive.append((lowest_p, current_p))
        elif current_p == 0:
            grads_even.append((lowest_p, 0))
        elif current_p < 0:
            grads_negative.append((lowest_p, current_p))

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

    current_p = 0
    for grad in grads_positive + grads_even + grads_negative:
        lowest_p = current_p + grad[0]
        if lowest_p < 0:
            return False
        current_p += grad[1]

    if current_p == 0:
        return True
    else:
        return False


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


if __name__ == "__main__":
    main()