Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
import sys
readline = sys.stdin.readline

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

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

if __name__ == '__main__':
  main()

def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  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
      u = min(u, h)
      if h > 0:
        Sp.append([u, h])
      else:
        Sm.append([u-h, -h])
      total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(reverse=True)
  p = check(Sp)
  if not p:
    print('No')
    exit()
  Sm.sort(reverse=True)
  m = check(Sm)
  if not m:
    print('No')
    exit()
  print('Yes')

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

if __name__ == '__main__':
  main()

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

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

if __name__ == '__main__':
  main()

import sys
readline = sys.stdin.readline

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

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

if __name__ == '__main__':
  main()

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

import sys
readline = sys.stdin.readline

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

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

if __name__ == '__main__':
  main()

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Accepted