Zonal Computing Olympiad 2012, 26 Nov 2011

A sequence of opening and closing brackets is well-bracketed if we can pair up each opening bracket with a matching closing bracket in the usual sense.  For instance, the sequences (), (()) and ()(()) are well-bracketed, while (, ()), (()(), and )(  are not well-bracketed.

The nesting depth of a well-bracketed sequence tells us the maximum number of levels of inner matched brackets enclosed within outer matched brackets.  For instance, the nesting depth of () and ()()() is 1, the nesting depth of (()) and ()(()) is 2, the nesting depth of ((())) is 3, and so on.  

Given a well-bracketed sequence, we are interested in computing the following: 
-  The nesting depth, and the first position where it occurs–this will be the position of the first opening bracket at this nesting depth, where the positions are numbered starting with 1.
-  The maximum number of symbols between any pair of matched  brackets, including both the outer brackets, and the first position where this occurs–that is, the position of the first opening bracket of this segment

For instance, the nesting depth of ()(())()(()())(()()) is 2 and the first position where this occurs is 4.  The opening bracket at position 10 is also at nesting depth 2 but we have to report the first position where this occurs, which is 4.

In this sequence, the maximum number of symbols between a pair of matched bracket is 6, starting at position 9. There is another such sequence of length 6 starting at position 15, but this is not the first such position.

-----Input format-----
The input consists of two lines. The first line is a single integer N, the length of the bracket sequence. Positions in the sequence are numbered 1,2,…,N. The second line is a sequence of N space-separated integers that encode the bracket expression as follows: 1 denotes an opening bracket ( and 2 denotes a closing bracket ).  Nothing other than 1 or 2 appears in the second line of input and the corresponding expression is guaranteed to be well-bracketed.

-----Output format-----
Your program should print 4 space-separated integers in a line, denoting the four quantities asked for in the following order: nesting depth, first position that achieves the nesting depth, length of the maximum sequence between matching brackets and the first position where such a maximum length sequence occurs.  

-----Testdata-----

You may assume that 2 ≤ N ≤ 105.  In 30% of the test cases, 2 ≤ N ≤ 103.

- Subtask 1 (30 marks)
- Subtask 2 (70 marks)

-----Sample Input-----
20
1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 2 1 2 2

-----Sample Output-----
2 4 6 9

Difficulty: interview

Starter code:

Solutions:
# cook your dish here

T = int(input())
l = list(map(int, input().strip().split(" ")))

depth = 0
max_depth = 0
max_depth_index = 0

max_l=0
max_l_index=0
last_zero=-1

for i in range(T):
    if l[i] == 1:
        depth += 1
        if depth > max_depth:
            max_depth = depth
            max_depth_index = i + 1
    else:
        depth-=1
        if depth == 0:
            length = i - last_zero
            if length > max_l:
                max_l = length
                max_l_index = last_zero + 2
            last_zero = i
        
print(max_depth, max_depth_index, max_l, max_l_index)

"""
2 4 6 9
"""

N = int(input())
s = input()
d = 0
md = 0
mdpos = 0
pl = 0
mpl = 0
plstart = 0
for i in range(N):
    t = s[i*2]
    if t == '1':
        d += 1
        if d > md :
            md = d
            mdpos = i
    else:
        d -= 1
    pl += 1
    if d == 0:
        if pl> mpl:
            mpl = pl
            mplstart = plstart
        plstart = i+1
        pl = 0
print(md,mdpos+1,mpl,mplstart+1)



n=int(input())
s=list(map(int,input().split()))
dans=0
fd=0
c=0
count=0
maxs=0
fs=n
for i in range(n):
    if s[i]==1:
        c-=1
        count+=1
        if abs(c)>dans:
            dans=abs(c)
            if fd<i:
                fd=i
    else:
        c+=1
        if c==0: 
            if count>maxs:
                maxs=count+1
                fs=i-maxs+2

            count=0
        else:
            count+=1

print(dans,fd+1,maxs,fs)


# cook your dish here
n = int(input())
a = list(map(int,input().strip().split()))
i = 0
x = 0
z = 0
nest = 1
pos = 0
seq = 1 
posq = 0
while(i<n):
    j= i + 1
    x = 1
    z = 1
    q = i
    while(j<n and x>0):
        if(a[j] == 1):
            x +=1 
            z +=1
            if(nest < x):
                nest = x
                pos = j
            if(seq<z):
                seq = z
                posq = q
        else:
            x-=1
        i = j + 1
        j+=1
print(nest, pos+1, 2*seq, posq+1)


n = int(input())
seq = list(map(lambda x: 1 if x=="1" else -1, input().split()))
sums = [seq[0]]
for i in seq[1:]:
    sums.append(sums[-1]+i)
fin_pos = -1
pos = -1
counter = -1
m = -1
for i in range(n):
    v = sums[i]
    if counter == -1 and v == 1:
        counter = 0
        pos = i
    elif v == 0:
        if counter > m:
            m = counter
            fin_pos = pos
        counter = -1
    elif counter != -1:
        counter += 1

print(max(sums), sums.index(max(sums))+1, m + 2, fin_pos+1)

# cook your dish here
def is_seq_brackets_right(input_seq):
    stack = []
    highest_depth = 0
    highest_depth_index = 0
    max_inner_symbols_no = 0
    max_inner_symbols_index = 0
    for index_ in range(len(input_seq)):
        i = input_seq[index_]
        if i == "1":
            stack.append(["1", index_])
        else:
            temp = stack.pop(-1)
            if index_ - temp[1] + 1 > max_inner_symbols_no:
                max_inner_symbols_no = index_ - temp[1] + 1
                max_inner_symbols_index = temp[1]

        if len(stack) > highest_depth:
            highest_depth = len(stack)
            highest_depth_index = index_
    return len(stack) == 0, highest_depth, highest_depth_index + 1, max_inner_symbols_no, max_inner_symbols_index + 1



N = int(input().strip())
input_string = input().strip()
bracket_input = input_string.replace(" ", "")
ans = is_seq_brackets_right(bracket_input)
print(ans[1], " ", ans[2], " ", ans[3], " ", ans[4])


# cook your dish here

def is_seq_brackets_right(input_seq):
    stack = []
    highest_depth = 0
    highest_depth_index = 0
    max_inner_symbols = []
    max_inner_symbols_no = 0
    max_inner_symbols_index = 0
    for index_ in range(len(input_seq)):
        i = input_seq[index_]
        if i == "(":
            stack.append("(")
            max_inner_symbols.append([index_, 1, True])
        else:
            stack.pop(-1)
            max_inner_symbols.pop(-1)

        for j in range(len(max_inner_symbols)):
            max_inner_symbols[j][1] = max_inner_symbols[j][1] + 1
            if max_inner_symbols[j][1] > max_inner_symbols_no:
                max_inner_symbols_no = max_inner_symbols[j][1]
                max_inner_symbols_index = max_inner_symbols[j][0]

        if len(stack) > highest_depth:
            highest_depth = len(stack)
            highest_depth_index = index_
    return len(stack) == 0, highest_depth, highest_depth_index + 1, max_inner_symbols_no, max_inner_symbols_index + 1


N = int(input().strip())
input_string = input().strip()
bracket_input = input_string.replace(" ", "").replace("1", "(").replace("2", ")")
ans = is_seq_brackets_right(bracket_input)
print(ans[1], " ", ans[2], " ", ans[3], " ", ans[4])


# cook your dish here
import sys
input=sys.stdin.readline
n=int(input())
l=input().split()
stack=[]
li=[int(i) for i in l]
maxa1=0
ans1=0
match=[0 for i in range(n)]
maxa2=0
ans2=0
for i in range(n):
    if(li[i]==2):
        if(len(stack)>maxa1):
            maxa1=len(stack)
            ans1=stack[-1]
        match[stack[-1]]=i
        stack.pop(-1)
    else:
        stack.append(i)
for i in range(n):
    if(match[i]-i>maxa2):
        maxa2=match[i]-i
        ans2=i
print(maxa1,ans1+1,maxa2+1,ans2+1)


# cook your dish here
N = int(input())

enc = input().split()
S = []

for e in enc : 
    if e == "1" : S.append("(")
    else : S.append(")")



# task 1 : max depth 

closures = []
d = 0
max_d = 0
max_d_idx = 0
start = 0
for idx in range(N) :
    
    
    s = S[idx]
    if s == "(" : 

        d += 1
        
        if d > max_d : 
            max_d = d 
            max_d_idx = idx + 1
        
    else : 
        d -= 1
    
    if d == 0 : 
        finish = idx
        closures.append([start, finish])
        start = idx + 1
    
    
    
    
# task 2 : maximum closure


diff = [x[1] - x[0] for x in closures]
max_diff = max(diff)
max_diff_idx = closures[diff.index(max_diff)][0] + 1


        
print(max_d, max_d_idx, max_diff + 1, max_diff_idx)

import sys
# import math as mt
# from collections import Counter
# from itertools import permutations
# from functools import reduce
# from heapq import nsmallest, nlargest, heapify, heappop, heappush, heapreplace

def get_inpt(): return sys.stdin.readline().strip()
def get_int(): return int(sys.stdin.readline().strip())
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))

# sys.setrecursionlimit(10**7)
INF = float('inf')
# MOD1, MOD2 = 1000000007, 998244353

n = get_int()
arr = get_array()

curr_nest = 0
max_nest = 1
nest_pos = 0

curr_symbols = 0
max_symbols = 2
max_symbols_open_pos = 0

seq = 0

for ind in range(n):
    
   # curr_nest += 1
   curr_symbols += 1
   
   if arr[ind] == 1:  # Open Parenthesis
      seq += 1
      if seq > max_nest:
         max_nest = seq
         nest_pos = ind
     
   else:  # Closed Parenthesis
      seq -= 1
      if seq == 0:
         if curr_symbols > max_symbols:
            max_symbols = curr_symbols
            max_symbols_open_pos = ind - curr_symbols + 1
         curr_symbols = 0

print(max_nest, nest_pos+1, max_symbols, max_symbols_open_pos+1)

# cook your dish here
import sys
n=int(input().strip())
stringa=input().strip().split()
stringa=''.join(stringa)
counter=0
max_width=0
max_depth=0
for i in range(n):
    if stringa[i]=='1':
        if counter==0:
            start=i
        counter+=1 
    else:
        if counter>max_depth:
            max_depth=counter
            depth_idx=i
        counter-=1
        if counter==0:
            end=i
            if end-start+1>max_width:
                max_width=end-start+1
                start_idx=start+1
print(max_depth, depth_idx, max_width, start_idx)

n=int(input())
x=[int(i) for i in input().split()]
a=0
b=0
y1=[]
y2=[]
p=0
q=0
for i in range(1,n+1):
    if x[i-1]==1:
        y1.append(i)
        y2.append(i)
    elif x[i-1]==2:
        if len(y1)>a:
            a=len(y1)
            p=y1[-1]   
        if len(y1)==1:
            if len(y2)+1>b:
                b=len(y2)+1
                q=y2[0]
            y2=[]
        else:
            y2.append(i)
        y1.pop()
print(a,p,b,q)

n=int(input())

a=[int(i) for i in input().split()]

md=0
mr=0
st1=[]
st2=[]
dno=0
rno=0

for i in range(1,n+1):
    if a[i-1]==1:
        st1.append(i)
        st2.append(i)
    elif a[i-1]==2:
        if len(st1)>md:
            md=len(st1)
            dno=st1[-1]
            
        if len(st1)==1:
            if len(st2)+1>mr:
                mr=len(st2)+1
                rno=st2[0]
            st2=[]
        else:
            st2.append(i)
        st1.pop()
print(md,dno,mr,rno)
                
    


# cook your dish here
x = int(input())
y = list(map(int, input().strip().split(" ")))
d, pd, l, pl = 0, 0, 0, 0
md, ml = 0, 0
for i in range(0,x):
    if(y[i] == 1):
        d = d+1
        if(d > md): md, pd = d, i+1
    if(y[i] == 2): d = d-1
    if(d != 0):
        l = l+1
        if(l > ml): ml, pl = l, i-l+1
    else:
        l = 0
print(md, pd, ml+1, pl+1)

# cook your dish here
n = int(input())
l = input().split()

ml = []
mnd, mndi = -1, -1
c = 1
maxc, maxci = 0, 0
for i in range(n):
    if l[i] == '1':
        ml.append('1')
        if len(ml) > mnd:
            mnd = len(ml)
            mndi = i
    if l[i] == '2':
        ml.pop()
        if ml == []:
            if c > maxc:
                maxc = c
                maxci = i
            c = 0
    c += 1
if c > maxc:
    maxc = c
    maxci = i
print(mnd, mndi+1, maxc, maxci-maxc+2)



try : 
    import sys
    
    num = int(input())
    brackets = list(map(int, sys.stdin.readline().strip().split()))
    
    max_len_seq = 0			 #len of max sequence bw matching brackets
    start_max_len_seq = 0	 #index where max length sequence occurs
    max_depth = 0            
    start_depth = 0			 #Index of where the nesting depth is achieved
    
    #temp vars
    t1=0
    t2=0
    t3=0
    t4=0
    
    n = 0   #number of brackets
    
    for i in range(num):
        if n == 0:
            t2 = i
    
        b = brackets[i]
        
        if b == 1: #opening bracket
            n+=1
            t3 +=1
            t4 = i
            t1+=1
        
        elif b == 2: #closing bracket
            n-=1
            t1+=1
            t3-=1
        
        if t3 > max_depth:
            max_depth = t3
            start_depth = t4
        
        if t1 > max_len_seq:
            max_len_seq = t1
            start_max_len_seq = t2
        
        if n == 0:
            t1=0
            t2=0
            t3=0
            t4=0
    
    print(max_depth, start_depth+1, max_len_seq, start_max_len_seq+1)   # +1 since list index starts from 0


except : pass

# cook your dish here
# cook your dish here
l = int(input())
a = list(map(int, input().split()))
stack = []
p, md, d = 0, 0, 0
mp, ml, l = 0, 0, 0
mpIndex = 0

for i in range(len(a)):
    if(d == 0):
        l = 0
        mpIndex = i+1
        
    l += 1
    
    if(a[i] == 1):
        d+=1
    else:
        d-=1
    
    if(d > md):
        md = d
        p = i+1
    
    if(l > ml):
        ml = l
        mp = mpIndex

print(md, p, ml, mp)

# cook your dish here
l = int(input())
a = list(map(int, input().split()))
stack = []
p, md, d = 0, 0, 0
mp, ml, l = 0, 0, 0
mpIndex = 0

for i in range(len(a)):
    if(d == 0):
        l = 0
        mpIndex = i+1
        
    l += 1
    
    if(a[i] == 1):
        d+=1
    else:
        d-=1
    
    if(d > md):
        md = d
        p = i+1
    
    if(l > ml):
        ml = l
        mp = mpIndex

print(md, p, ml, mp)

l = int(input())
a = list(map(int, input().split()))
stack = []
p, md, d = 0, 0, 0
mp, ml, l = 0, 0, 0
mpIndex = 0

for i in range(len(a)):
    if(d == 0):
        l = 0
        mpIndex = i+1
        
    l += 1
    
    if(a[i] == 1):
        d+=1
    else:
        d-=1
    
    if(d > md):
        md = d
        p = i+1
    
    if(l > ml):
        ml = l
        mp = mpIndex

print(md, p, ml, mp)

n=int(input())
a=list(map(int,input("").strip().split()))[:n]
s=list()
li=list()
k=0;
pos=0;
sik=list()
for l in range(len(a)):
    if a[l]==1:
        li.append('(')
        s.append('(')
    elif a[l]==2:
        s.append(')')
        if len(li)!=0:
            if k<len(li):
                pos=l;
                k=len(li)
            del li[len(li)-1]
        if len(li)==0:
            sik.append(s);
            s=list()
le=0;
for i in sik:
    if le<len(i):
        le=len(i);
se=0;
for i in sik:
    if le==len(i):
        break;
    se+=len(i);
print(k,pos,le,se+1)


n=int(input())
total,distance,new_first=0,0,0
a=[]
answer = []
length =list(map(str,input().split()))
string ="".join(length)        
for i in range(len(string)):
    if(string[i]=='1'):
        a.append(i)
        if(total<len(a)):
            total=len(a)
            start=a[len(a)-1]
    elif(len(a)!=0 and string[i]=='2'):        
        if(len(a)==1):
            if(distance<i-a[len(a)-1]):
                distance=i-a[len(a)-1]
                new_first=a[len(a)-1]
        a.pop()
answer.append(total)
answer.append(' ')
answer.append(start+1)
answer.append(' ')
answer.append(distance+1)
answer.append(' ')
answer.append(new_first+1)
print(''.join(map(str, answer)))