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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
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)


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)


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)


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


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)


N = int(input())
enc = input().split()
S = []
for e in enc:
	if e == '1':
		S.append('(')
	else:
		S.append(')')
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
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

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()))
INF = float('inf')
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_symbols += 1
	if arr[ind] == 1:
		seq += 1
		if seq > max_nest:
			max_nest = seq
			nest_pos = ind
	else:
		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)


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)


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)


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
	start_max_len_seq = 0
	max_depth = 0
	start_depth = 0
	t1 = 0
	t2 = 0
	t3 = 0
	t4 = 0
	n = 0
	for i in range(num):
		if n == 0:
			t2 = i
		b = brackets[i]
		if b == 1:
			n += 1
			t3 += 1
			t4 = i
			t1 += 1
		elif b == 2:
			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)
except:
	pass


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