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: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
increasing = []
decreasing = []
dec_special = []
for _ in range(n):
    s = input().rstrip()
    minima = 0
    fin = 0
    for ch in s:
        if ch == ")":
            fin -= 1
            if fin < minima:
                minima = fin
        else:
            fin += 1
    if fin >= 0:
        increasing.append((minima, fin))
    elif minima < fin:
        dec_special.append((minima, fin))
    else:
        decreasing.append((minima, fin))

increasing.sort(reverse=True)
decreasing.sort()
dec_special.sort()

current = 0
for minima, diff in increasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in dec_special:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in decreasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
if current != 0:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
n = int(input())
plus_bracket = []
minus_bracket = []

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])
  else:
    minus_bracket.append([cur - mini, -cur])

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

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

Submission status: Accepted

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

def main():
    N = int(input())
    S = []
    for i in range(N):
        S.append(input())

    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: Accepted

Solution code:

def check(s):
    h = 0
    for p in s:
        b = h + p[0]
        if b < 0:
            return False
        h += p[1]
    return True


N = int(input())
S = []
left = []
right = []
total = 0
for i in range(N):
    last = 0
    bottom = 0
    s = input().strip()
    for c in s:
        if c == "(":
            last += 1
        else:
            last -= 1
        bottom = min(bottom, last)
    if last > 0:
        left.append((bottom, last))
    else:
        right.append((bottom-last, -last))
    total += last

left.sort(key=lambda x: -x[0])
right.sort(key=lambda x: -x[0])

if check(left) and check(right) and total == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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


def solve():
    N = int(input())
    brackets_gen = (readline().strip() 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(reverse=True)

    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: Accepted

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(reverse=True)

    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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n = int(input())
S = [ input() for _ in range(n)]

left = 0
right = 0

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

    left += l
    right += r

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]
for i in range(len(negatives)):
    # 負の要素だけ、裏返して末尾から見た値に変換する
    min_lmr, lmr = negatives[i]
    min_lmr = min_lmr - lmr
    lmr = -1 * lmr
    negatives[i] = (min_lmr, lmr)

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

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

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

print("Yes")

Submission status: Accepted

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]
for i in range(len(negatives)):
    min_lmr, lmr = negatives[i]
    min_lmr = min_lmr - lmr
    lmr = -1 * lmr
    negatives[i] = (min_lmr, lmr)

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

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

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

print("Yes")

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter


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


def _i(): return int(sys.stdin.readline().strip())


def parse(s):
    l, r = 0, 0
    for c in s:
        if c == '(':
            r += 1
        else:
            if r > 0:
                r -= 1
            else:
                l += 1
    return (l, r)


def main():
    n = _i()
    p = list(filter(lambda x: x != (0, 0), [parse(_s()) for _ in range(n)]))
    u, d = [], []
    for l, r in p:
        u.append((l, r)) if l <= r else d.append((l, r))
    u.sort(key=itemgetter(0))
    d.sort(key=itemgetter(1), reverse=True)
    r = 0
    for ll, rr in u+d:
        if ll > r:
            return 'No'
        r += (rr - ll)

    return 'Yes' if r == 0 else 'No'


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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 and not r_ok[i] ]
tails     = [ (MIN_LMR[i], LMR[i]) for i,x in enumerate(LMR) if x < 0 and r_ok[i]]

positives.sort(reverse=True)
negatives.sort()
tails.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 + tails:
    if h+min_lmr < 0:
        print("No")
        exit()
    h += lmr

print("Yes")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    zeros = []
    incs = []
    decs = []
    s = [None] * N

    for i in range(N):
        s[i] = S()
        cur = 0
        mn = 0
        for c in s[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            mn = min(mn, cur)
        end = cur

        if end == 0:
            zeros.append((mn, end, i))
        elif end > 0:
            incs.append((mn, end, i))
            # heappush(incs, (-mn, end))
        else:
            decs.append((mn - end, end, i))
            # heappush(decs, (mn, end))

    incs.sort(reverse=True)
    decs.sort()

    ans = []
    for mn, end, idx in incs:
        ans.append(s[idx])

    for mn, end, idx in zeros:
        ans.append(s[idx])

    for mn, end, idx in decs:
        ans.append(s[idx])

    now = 0
    for i in range(len(ans)):
        for c in ans[i]:
            if c == '(':
                now += 1
            else:
                now -= 1
            if now < 0:
                print("No")
                return

    print(yn[now == 0])

    # now = 0
    # for mn, end, idx in incs:
    #     if now + mn < 0:
    #         print('No')
    #         return
    #     now += end

    # for mn, end, idx in zeros:
    #     if now + mn < 0:
    #         print('No')
    #         return
    #     now += end

    # for mn, end, idx in decs:
    #     if now + mn < 0:
    #         print('No')
    #         return
    #     now += end

    # print(yn[now == 0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = []
B = []
cur = 0
for i in range(N):
    S = input()
    tmp = []
    for s in S:
        if s == '(':
            tmp.append(s)
        else:
            if tmp and tmp[-1] == '(':
                tmp.pop()
            else:
                tmp.append(s)
    l = tmp.count('(')
    r = len(tmp) - l
    if r-l <= 0:
        A.append((l, r))
    else:
        B.append((l, r))
A.sort(key=itemgetter(1))
B.sort(key=itemgetter(0), reverse=1)

for l, r in A:
    cur += r
    if cur > 0:
        No()
        exit()
    cur -= l
for l, r in B:
    cur += r
    if cur > 0:
        No()
        exit()
    cur -= l
if cur == 0:
    Yes()
else:
    No()

Submission status: Accepted

Solution code:
def f_bracket_sequencing():
    N = int(input())
    Brackets = [input() for _ in range(N)]

    total = 0  # 正なら '(' が多い、負なら ')' が多い
    increase, decrease = [], []
    for s in Brackets:
        # 文字列を ±1 とみなして累積和を取ったとき、
        # ')' に対する '(' の多さの最終値と、それの最小値
        height, bottom = 0, 0
        for ch in s:
            height += 1 if ch == '(' else -1
            bottom = min(bottom, height)
        if height > 0:
            increase.append((bottom, height))
        else:
            decrease.append((bottom - height, -height))
        total += height
    increase.sort(reverse=True)
    decrease.sort(reverse=True)

    def accept(pairs):
        h = 0
        for p in pairs:
            b = h + p[0]
            if b < 0:
                return False  # '(' より ')' が多く、括弧列を構成できない
            h += p[1]
        return True

    return 'Yes' if accept(increase) and accept(decrease) and total == 0 else 'No'

print(f_bracket_sequencing())

Submission status: Accepted

Solution code:
N = int(input())
s = []
for i in range(N):
    s.append(input())
inc = []
dec = []
total = 0
for i in s:
    cn = 0
    mn = 0
    for j in i:
        if j=="(":
            cn+=1
        else:
            cn-=1
        mn = min(cn,mn)
    total += cn
    if cn>=0:
        inc.append([mn,cn])
    else:
        dec.append([mn-cn,-cn])

inc.sort(reverse=True,key=lambda x:x[0])
dec.sort(reverse=True,key=lambda x:x[0])

def check(lis):
    hi = 0
    for i in lis:
        if hi+i[0]<0:
            return False
        else:
            hi+=i[1]
    return True

if check(inc) and check(dec) and total==0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
def to_lines(s):
    h = 0
    b = 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
        b = min([b, h])
    return (b, h)


def check(lines):
    h = 0
    for line in lines:
        if h + line[0] < 0:
            return False
        h += line[1]
    return True


def main():
    N = int(input())
    up_lines = list()
    down_lines = list()
    total = 0
    for _ in range(N):
        line = to_lines(input())
        total += line[1]
        if line[1] >= 0:
            up_lines.append(line)
        else:
            inv_line = (line[0] - line[1], -line[1])
            down_lines.append(inv_line)
    up_lines.sort(key=lambda x: x[0], reverse=True)
    down_lines.sort(key=lambda x: x[0], reverse=True)
    if total == 0 and check(up_lines) and check(down_lines):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
lp=[]
lm=[]
for i in range(n):
    s=input()
    x,y=0,0
    for j in s:
        if j=="(":
            x+=1
        else:
            x-=1
        y=min(y,x)
    if x>0:
        lp.append((y,x))
    else:
        lm.append((y-x,-x))
lp.sort()
s=0
for i,j in lp[::-1]:
    if s+i<0:
        print("No")
        exit()
    s+=j
lm.sort()
t=0
for i,j in lm[::-1]:
    if t+i<0:
        print("No")
        exit()
    t+=j
if s==t:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
# **************************************************************************** #
#                                                                              #
#                                            __   __ .____  .__  __.  ____     #
#    F-bracketSequencing.py                 |  | |  ||  _ \ |  \/  | /    |    #
#                                           |  | |  || |_| || \  / ||  ,--'    #
#    By: ayahyao <y.anas1997@gmail.com>     |  | |  ||  __/ | |\/| ||  |       #
#                                           |  `-'  || |    | |  | ||  `--.    #
#    Created: 2020/05/10 18:38 by Anas       \_____/ |_|    |_|  |_| \____|    #
#    Updated: 2020/05/10 18:42 by Anas                                         #
#                                                                              #
# **************************************************************************** #

def     process(tab, beginning, end):
    total = beginning
    for i in tab:
        if (i[1] > total or total + i[0] < 0):
            return ("No")
        total += i[0]
    if (total == end):
        return ("Yes")
    return ("No")

def     parsing(N):
    beginning, ending = 0,0
    clean = 0
    total = 0
    tab = []

    for i in range(N):
        s = input()
        before, after = 0, 0
        for j in s:
            if (j == '('):
                after += 1
            elif (j == ')'):
                if (after > 0):
                    after -= 1
                else:
                    before += 1
        if (before == 0 and after > 0):
            beginning += after
        elif (after == 0 and before > 0):
            ending += before
        elif (before > 0 or after > 0):
            tab.append((after - before, before, after))
        else:
            clean += 1
        total += before - after
    tab = sorted(tab)[::-1]
    return tab, total, beginning, ending, clean


N  = int(input())
tab, total, beginning, ending, clean = parsing(N)
if (total == 0 and N == 1):
    res = "Yes"
elif ((total != 0) or ((min(beginning, ending) == 0 and clean == 0) 
                 or (max(beginning, ending) == 0 and clean == 1))):
    res = "No"
else:
    res = process(tab, beginning, ending)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = only_l
# print(exlr)
exlr.sort()
# exlr.sort(key=lambda x: x[1])

# print(exlr)
# for i in range(len(exlr)):
#     if exlr[i][1] <= a and exlr[i][0] <= 0:
#         a -= exlr[i][0]
#         exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if a-b == 0:
    print("Yes")
else:
    print("No")
# if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
#     print("Yes")
# elif exr+exl+only_l+only_r == 0:
#     print("Yes")
# else:
#     print("No")

Submission status: Accepted

Solution code:
N = int(input())
from collections import deque
L = deque([])
R = deque([])

for i in range(N):
  S = input()
  l = [0]*len(S)
  if S[0]=='(':
    l[0]=1
  else:
    l[0]=-1
  for j in range(1,len(S)):
    if S[j]=='(':
      l[j] = l[j-1] + 1
    else:
      l[j] = l[j-1] - 1
  if l[-1] < 0:
    R.append([min(l)-l[-1], -l[-1], min(l), l[-1]])
  else:
    L.append([min(0,min(l)),l[-1]])
    
R = sorted(R, key = lambda x:x[0])
L = sorted(L, key = lambda x:x[0], reverse = True)
now = 0
judge = True
    
for l in L:
  if now + l[0]<0:
    judge = False
    break
  else:
    now += l[1]
    
for r in R:
  if now+r[2]<0:
    judge = False
    break
  else:
    now += r[3]
    
if now!=0:
  judge = False
  
if judge:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
#!python3

def LI():
    return list(map(int, input().split()))

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


def judge(v):
    x = 0
    for b, l in v:
        if x + b < 0:
            return False
        x += l
    return True


def main():
    pl, ml = [], []
    t = 0
    for i in range(N):
        l = 0
        b = 0
        for s in S[i]:
            if s == "(":
                l += 1
            else:
                l -= 1
                b = min(b, l)
        t += l
        if l > 0:
            pl.append((b, l))
        else:
            ml.append((b - l, -l))

    pl.sort(reverse=True)
    ml.sort(reverse=True)

    if judge(pl) and judge(ml) and t == 0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = only_l
exlr.sort(key=lambda x: x[1])
exlr.sort()

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a and exlr[i][0] <= 0:
        a -= exlr[i][0]
        exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if a-b == 0:
    print("Yes")
else:
    print("No")
# if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
#     print("Yes")
# elif exr+exl+only_l+only_r == 0:
#     print("Yes")
# else:
#     print("No")

Submission status: Accepted

Solution code:
N = int(input())

S_list = []
for _ in range(N):
	S_list.append(input().strip())

data = []
for s in S_list:
	bottom = 0
	height = 0
	for c in s:
		if c == ")":
			height -= 1
			if bottom > height:
				bottom = height
		else:
			height += 1
	if height == 0:
		k1 = 1
		k2 = 0
	elif height > 0:
		k1 = 0
		k2 = -bottom
	else:
		k1 = 2
		k2 = bottom - height
	data.append((k1, k2, bottom, height, s))

data.sort()

def check():
	height = 0
	for k1, k2, b, h, s in data:
#		print(height, b, h, s)
		if height + b < 0:
			return False
		height += h
	return height == 0

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

Submission status: Accepted

Solution code:









def     process(tab, first, end):
    #print(tab)
    #print(first, end)
    total = first
    for i in tab:
        if (i[1] > total):
            return ("No")
        total += i[0]
        if (total < 0):
            return ("No")
    if (total == end):
        return ("Yes")
    return ("No")




N  = int(input())

first = 0
last = 0
clean = 0
tab = []
total = 0
for i in range(N):
    s = input()
    avant = 0
    apres = 0
    for j in s:
        if (j == '('):
            apres += 1
        elif (j == ')'):
            if (apres > 0):
                apres -= 1
            else:
                avant += 1
    if (avant == 0 and apres > 0):
        first += apres
    elif (apres == 0 and avant > 0):
        last += avant
    elif (avant > 0 or apres > 0):
        tab.append((apres - avant, avant, apres, s))
    else:
        clean += 1
    total += avant - apres
if (first == -1 and clean > 0):
    first = 0
    clean -= 1
if (last == -1 and clean > 0):
    last = 0


tab = sorted(tab)
tab = tab[::-1]
if (total == 0 and first > -1 and last > -1):
    res = process(tab, first, last)
else:
    if (total == 0 and N == 1):
        res = "Yes"
    else:
        res = "No"
print(res)

Submission status: Accepted

Solution code:









def     process(tab, first, end):
    #print(tab)
    #print(first, end)
    total = first
    for i in tab:
        if (i[1] > total):
            return ("No")
        total += i[0]
        if (total < 0):
            return ("No")
    if (total == end):
        return ("Yes")
    return ("No")




N  = int(input())

first = -1
last = -1
clean = 0
tab = []
total = 0
for i in range(N):
    s = input()
    avant = 0
    apres = 0
    for j in s:
        if (j == '('):
            apres += 1
        elif (j == ')'):
            if (apres > 0):
                apres -= 1
            else:
                avant += 1
    if (avant == 0 and apres > 0 and first == -1):
        first = apres
    elif (apres == 0 and avant > 0 and last == -1):
        last = avant
    elif (avant > 0 or apres > 0):
        tab.append((apres - avant, avant, apres, s))
    else:
        clean += 1
    total += avant - apres
if (first == -1 and clean > 0):
    first = 0
    clean -= 1
if (last == -1 and clean > 0):
    last = 0


tab = sorted(tab)
tab = tab[::-1]
if (total == 0 and first > -1 and last > -1):
    res = process(tab, first, last)
else:
    if (total == 0 and N == 1):
        res = "Yes"
    else:
        res = "No"
print(res)