Problem:


Score : 800 points

Problem Statement

Given is a string S, where each character is 0, 1, or ?.

Consider making a string S' by replacing each occurrence of ? with 0 or 1 (we can choose the character for each ? independently).
Let us define the unbalancedness of S' as follows:

(The unbalancedness of S') = \max \{ The absolute difference between the number of occurrences of 0 and 1 between the l-th and r-th character of S (inclusive) :\ 1 \leq l \leq r \leq |S|\}

Find the minimum possible unbalancedness of S'.

Constraints

1 \leq |S| \leq 10^6

Each character of S is 0, 1, or ?.

Input

Input is given from Standard Input in the following format:

S

Output

Print the minimum possible unbalancedness of S'.

Sample Input 1

0??

Sample Output 1

1

We can make S'= 010 and achieve the minimum possible unbalancedness of 1.

Sample Input 2

0??0

Sample Output 2

2

Sample Input 3

??00????0??0????0?0??00??1???11?1?1???1?11?111???1

Sample Output 3

4



Sample input:
0??


Sample output:
1

Submission status: Accepted

Solution code:
def main():
    S = input()
    size = [[[[0, 0]], []], [[], []]]
    length = 0

    for s in S:
        size2 = [[[], []], [[], []], [[], []]]
        if s != "0":
            for i in range(2):
                for j in range(2):
                    if size[i][j]:
                        for x, y in size[i][j]:
                            if y == length+i:
                                size2[i+1][j ^ 1].append([y+1, y+1])
                                if x != y:
                                    size2[i][j ^ 1].append([x+1, y-1])
                            else:
                                size2[i][j ^ 1].append([x+1, y+1])
        if s != "1":
            for i in range(2):
                for j in range(2):
                    if size[i][j]:
                        for x, y in size[i][j]:
                            if x == 0:
                                size2[i+1][j].append([0, 0])
                                if x != y:
                                    size2[i][j ^ 1].append([x+1, y-1])
                            else:
                                size2[i][j ^ 1].append([x-1, y-1])
        if len(size2[0][0]+size2[0][1]) == 0:
            size2 = size2[1:]
            length += 1
        else:
            size2.pop()
        for i in range(2):
            for j in range(2):
                size2[i][j] = sorted(size2[i][j])
        size = [[[], []], [[], []]]
        for i in range(2):
            for j in range(2):
                if len(size2[i][j]) == 0:
                    continue
                elif len(size2[i][j]) == 1:
                    size[i][j] = size2[i][j]
                    continue
                size[i][j] = [size2[i][j][0]]
                for x, y in size2[i][j][1:]:
                    p, q = size[i][j][-1]
                    if y <= q:
                        continue
                    if x <= q+2:
                        size[i][j][-1][1] = y
                    else:
                        size[i][j].append([x, y])
    print(length)


main()

Submission status: Accepted

Solution code:
S = input()

c = 0
cum = [c]
for s in S:
    if s == "1":
        c += 1
    else:
        c -= 1
    cum.append(c)
max_cum = [None] * (len(S) + 1)
max_cum[-1] = cum[-1]
for i in reversed(range(len(S))):
    max_cum[i] = max(cum[i], max_cum[i + 1])
z = max_cum[0]


def f(m):
    c = 0
    fz = c
    add = 0
    for i, s in enumerate(S):
        if s == "1":
            c += 1
        elif s == "0":
            c -= 1
            fz = min(fz, c)
        elif add + max_cum[i + 1] + 2 <= m:
            c += 1
            add += 2
        else:
            c -= 1
            fz = min(fz, c)
    return fz


fz = f(z)
fz1 = f(z + 1)

ans = min(z - fz, z + 1 - fz1)
print(ans)

Submission status: Accepted

Solution code:
from numba import njit
import numpy as np
s = np.array(list(map(lambda x: -1 if x == '?' else int(x), input())))
@njit
def test(c):
    # current point can be seen as xth smallest val, where x can be any value in [a, b] (subset of [0, c])
    # a <= b
    a, b = 0, c
    ok = True
    discrete = False # when True x = a, a+2, ..., b-2, b
    for si in s:
        if si == 1:
            if a == b == c:
                return False
            a += 1
            b += 1
            if b > c:
                b = c - 1 if discrete else c
        elif si == 0:
            if a == b == 0:
                return False
            a -= 1
            b -= 1
            if a < 0:
                a = 1 if discrete else 0
        else:
            if a == b == 0:
                a = b = 1
            elif a == b == c:
                a = b = c - 1
            elif a == b:
                discrete = True
                a -= 1
                b += 1
            else:
                a -= 1
                b += 1
                if a < 0:
                    a = 1 if discrete else 0
                if b > c:
                    b = c - 1 if discrete else c
    return True

l, r = 0, s.size
while r - l > 1:
    c = (l + r) // 2
    if test(c):
        r = c
    else:
        l = c
print(r)

Submission status: Accepted

Solution code:
S = input()
N = len(S)

A = [0]*(N+1)
for i,s in enumerate(S,1):
    if s=="1":
        A[i] = A[i-1]+1
    else:
        A[i] = A[i-1]-1

m = max(A)
B = [A[-1]]*(N+1)
C = [m-A[-1]]*(N+1)
for i in range(N):
    i = N-i-1
    B[i] = max(A[i],B[i+1])
    C[i] = m-B[i]

d = 0
e = 0
D = A[:]
E = A[:]
for i,s in enumerate(S,1):
    if s=='?' and C[i] >= d+2:
        d += 2
    if s=='?' and C[i] >= e+1:
        e += 2
    D[i] += d
    E[i] += e
ans = min(max(D)-min(D),max(E)-min(E))
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],i8)', cache=True)
def test(S, A):
    def f(L, R):
        if L > R:
            return False
        for x in S:
            if x == 1:
                L, R = L + 1, R + 1
                if R > A:
                    R -= 2
            elif x == -1:
                L, R = L - 1, R - 1
                if L < 0:
                    L += 2
            else:
                L -= 1
                R += 1
                if L < 0:
                    L += 2
                if R > A:
                    R -= 2
            if L > R:
                return False
        return True

    for parity in (0, 1):
        L, R = 0, A
        if parity == 0:
            R -= A & 1
        else:
            L = 1
            R -= 1 - (A & 1)
        if f(L, R):
            return True
    return False

S = np.array(list(read().rstrip().decode()), 'U1')
Si = np.zeros(len(S), np.int64)
Si[S == '0'] = -1
Si[S == '1'] = 1
S = Si

low = 0  # むり
high = len(S) + 10  # おさめられる
while low + 1 < high:
    x = (low + high) // 2
    if test(S, x):
        high = x
    else:
        low = x

print(high)

Submission status: Accepted

Solution code:
S = list(input())
N = len(S)


Z = 0
SUM = 0
for s in S:
  if s == "1":
    SUM += 1
    Z = max(Z,SUM)
  else:
    SUM -= 1

ruiseki_max = [0]
MAX = SUM
for s in S[1:][::-1]:
  if s == "1":
    SUM -= 1
  else:
    SUM += 1
    MAX = max(MAX,SUM)
  ruiseki_max.append(MAX-SUM)

def f(Z):
  SUM = 0
  MIN = 0
  for i in range(N):
    s = S[i]
    if s == "1":
      SUM += 1
    elif s == "0":
      SUM -= 1
      MIN = min(MIN,SUM)
    else:
      if SUM + 1 + ruiseki_max[N-1-i] <= Z:
        SUM += 1
      else:
        SUM -= 1
        MIN = min(MIN,SUM)
  return MIN

print(min(Z-f(Z),(Z+1-f(Z+1))))

Submission status: Accepted

Solution code:

def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

def solve(S):
    d = {'0':0,'1':1,'?':2}
    S = tuple(d[c] for c in S)
    lookup = ((-1,-1),(1,1), (-1,1))

    def judge(target_lo, target_hi):
        lo,hi = 0,0
        pl = target_lo%2 == 0
        ph = target_hi%2 == 0
        for s in S:
            a,b = lookup[s]
            lo = max(lo+a, target_lo+pl)
            hi = min(hi+b, target_hi-ph)
            if hi < lo:
                return False
            pl = not pl
            ph = not ph
        return True

    best = 10**6*2
    n0,n1,n2 = S.count(0), S.count(1), S.count(2)
    lo = -n0-n2
    hi = n1+n2
    while True:
        hi = bisect(-1, hi, lambda x: judge(lo, x))
        lo = bisect(1, lo, lambda x: judge(x, hi))
        if hi-lo >= best:
            break
        else:
            best = hi-lo
    hi += 1
    lo = bisect(1, lo, lambda x: judge(x, hi))
    return min(best, hi-lo)

# from itertools import product, accumulate
# from random import shuffle

# def naive(S):
#     d = {'0':(-1,), '1':(1,), '?': (-1,1)}
#     return min(max(0,max(accumulate(X)))-min(0,min(accumulate(X))) for X in product(*(d[c] for c in S)))

if __name__ == '__main__':
    S = input()
    print(solve(S))

    # for _ in range(50):
    #     S = ['0']*15+['1']*15+['?']*14
    #     shuffle(S)
    #     S = ''.join(S)
    #     print(S, naive(S), solve(S))

Submission status: Accepted

Solution code:
S = input()

max0 = 0
max1 = 0
amax0 = []
amax1 = []
mi0 = 0
mi1 = 0
h0 = 0
h1 = 0
for i, c in enumerate(S):
    if c=="1":
        h1 += 1
        if h1-mi1 > max1:
            max1 = h1-mi1
            amax1 = [i]
        elif h1-mi1 == max1:
            amax1.append(i)
        h0 -= 1
        if h0 < mi0:
            mi0 = h0
    elif c=="0":
        h1 -= 1
        if h1 < mi1:
            mi1 = h1
        h0 += 1
        if h0-mi0 > max0:
            max0 = h0-mi0
            amax0 = [i]
        elif h0-mi0 == max0:
            amax0.append(i)
    else:
        h1 -= 1
        if h1 < mi1:
            mi1 = h1
        h0 -= 1
        if h0 < mi0:
            mi0 = h0
if max0 < max1:
    if len(set([i%2 for i in amax1]))==1:
        print(max1)
    else:
        print(max1+1)
elif max0 > max1:
    if len(set([i%2 for i in amax0]))==1:
        print(max0)
    else:
        print(max0+1)
else:
    if len(set([i%2 for i in amax1]+[(max0+i)%2 for i in amax0]))==1:
        print(max0)
    else:
        print(max0+1)

Submission status: Accepted

Solution code:
S = input()

max0 = 0
max1 = 0
amax0 = []
amax1 = []
mi0 = 0
mi1 = 0
h0 = 0
h1 = 0
for i, c in enumerate(S):
    if c=="1":
        h1 += 1
        if h1-mi1 > max1:
            max1 = h1-mi1
            amax1 = [i]
        elif h1-mi1 == max1:
            amax1.append(i)
        h0 -= 1
        if h0 < mi0:
            mi0 = h0
    elif c=="0":
        h1 -= 1
        if h1 < mi1:
            mi1 = h1
        h0 += 1
        if h0-mi0 > max0:
            max0 = h0-mi0
            amax0 = [i]
        elif h0-mi0 == max0:
            amax0.append(i)
    else:
        h1 -= 1
        if h1 < mi1:
            mi1 = h1
        h0 -= 1
        if h0 < mi0:
            mi0 = h0
# if max0 < max1:
#     ma = max1
#     idx_max = amax1
# else:
#     ma = max0
#     idx_max = amax0
if max0 < max1:
    if len(set([i%2 for i in amax1]))==1:
        print(max1)
    else:
        print(max1+1)
elif max0 > max1:
    if len(set([i%2 for i in amax0]))==1:
        print(max0)
    else:
        print(max0+1)
else:
    if len(set([i%2 for i in amax1]+[(max0+i)%2 for i in amax0]))==1:
        print(max0)
    else:
        print(max0+1)

Submission status: Runtime Error

Solution code:
for i in range(int(input())):
	s=input()
	o=0
	z=0
	l=[]
	q=[]
	for j in range(len(s)):
		if s[j]=="0":
			z+=1
			q.append("0")
		elif s[j]=="1":
			o+=1
			q.append("1")
		else:
			if z>o:
				o+=1
				q.append("1")
			elif o>z:
				z+=1
				q.append("0")
			else:
				if len(l)>0:
					ma=max(l)
					if q[j-ma:j].count("1")>q[j-ma:j].count("0"):
						z+=1
						q.append("0")
					else:
						o+=1
						q.append("1")
				else:
					if s.count("1")>s.count("0"):
						z+=1
						q.append("0")
					else:
						o+=1
						q.append("0")
		l.append(abs(o-z))
	print(max(l))

Submission status: Runtime Error

Solution code:
z=0
n=0
s=input()
l=[]
for i in range(len(s)):
	if s[i]=="0":
		z+=1
	elif s[i]=="1":
		n+=1
	else:
		if z>n:
			n+=1
		elif z<n:
			z+=1
		else:
			if s[i-1]=="1":
				z+=1
			elif s[i-1]=="?":
				t1=s[max(l):i].count("1")
				t2=s[max(l):i].count("0")
				if t1>=t2:
					z+=1
				else:
					n+=1
			else:
				n+=1
	
	l.append(abs(z-n))
print(max(l))

Submission status: Runtime Error

Solution code:
import numpy as np
s = np.array(list(map(lambda x: -1 if x == '?' else int(x), input())))

def test(c):
    # current point can be seen as xth smallest val, where x can be any value in [a, b] (subset of [0, c])
    # a <= b
    a, b = 0, c
    ok = True
    discrete = False # when True x = a, a+2, ..., b-2, b
    for si in s:
        if si == 1:
            if a == b == c:
                return False
            a += 1
            b += 1
            if b > c:
                b = c - 1 if discrete else c
        elif si == 0:
            if a == b == 0:
                return False
            a -= 1
            b -= 1
            if a < 0:
                a = 1 if discrete else 0
        else:
            if a == b == 0:
                a = b = 1
            elif a == b == c:
                a = b = c - 1
            elif a == b:
                discrete = True
                a -= 1
                b += 1
            else:
                a -= 1
                b += 1
                if a < 0:
                    a = 1 if discrete else 0
                if b > c:
                    b = c - 1 if discrete else c
    return True

l, r = 0, s.size
while r - l > 1:
    c = (l + r) // 2
    if test(c):
        r = c
    else:
        l = c
print(r)

Submission status: Runtime Error

Solution code:
import itertools
import copy

syokiti = list(input())

last=[]
for i in itertools.product("10",repeat=syokiti.count("?")):
    yousuu=0
    a=copy.deepcopy(syokiti)
    for kai,j in enumerate(a):
        if j == "?":
            a[kai]=i[yousuu]
            yousuu+=1
    
    ls = [j+1 for j in range(len(a))]
    handan = []
    for j in itertools.combinations(ls,2):
        
        j = list(j)
        renzoku=0
        saisyo=a[0]
        saikouti=0
        for k in range(j[0]-1,j[1]):
            if a[k] == saisyo:
                renzoku += 1
            else:
                saisyo = a[k]
                renzoku = 1
            if saikouti < renzoku:
                saikouti = renzoku
                
        handan.append(saikouti)
    last.append(max(handan))

print(min(last))

Submission status: Runtime Error

Solution code:
import random

s_ori=input()
cycle=10000
unb=[0]*10000 ##(len(s_ori)*(len(s_ori)+1)//2)
zero=0
one=0
ans=1000000
un=0
s=s_ori
ran=0


for a in range(cycle):
  s=s_ori
  s=list(s)
  for i in range(len(s)):
    if s[i]=='?':
      s[i]=random.randrange(2)
  s=list(map(int,s))
  for j in range(len(s)//2):
    for k in range(len(s)//2,len(s)):
      if j==k:
        unb[len(s)*j+k]=0
      else:
        zero=s[j:k].count(0)
        one=s[j:k].count(1)
        unb[len(s)*j+k]=abs(zero-one)
  un=max(unb)
  if un<ans:
    ans=un
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4[::1],i4[::1])', cache=True)
def f(S, T):
    m, x, M = 0, 0, 0
    for i in range(len(S)):
        if S[i] == -1:
            x -= 1
        elif S[i] == 1:
            x += 1
        else:
            if x - 1 + T[i] >= m:
                x -= 1
            else:
                x += 1
        m = min(m, x)
        M = max(M, x)
    return M - m

S = np.array(list(read().rstrip().decode()), 'U1')

Si = np.zeros(len(S), np.int32)
Si[S == '0'] = -1
Si[S == '1'] = 1
S = Si

T = S.copy()
T[S == 0] = 1
T = np.cumsum(T)
T = np.minimum.accumulate(T[::-1])[::-1] - T
print(f(S, T))

Submission status: Runtime Error

Solution code:
import random

s_ori=input()
cycle=10000
unb=[0]*2000 ##(len(s_ori)*(len(s_ori)+1)//2)
zero=0
one=0
ans=1000000
un=0
s=s_ori
ran=0


for a in range(cycle):
  s=s_ori
  s=list(s)
  for i in range(len(s)):
    if s[i]=='?':
      s[i]=random.randrange(2)
  s=list(map(int,s))
  for j in range(len(s)//2):
    for k in range(len(s)//2,len(s)):
      if j==k:
        unb[len(s)*j+k]=0
      else:
        zero=s[j:k].count(0)
        one=s[j:k].count(1)
        unb[len(s)*j+k]=abs(zero-one)
  un=max(unb)
  if un<ans:
    ans=un
    
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = dict(Counter(list(input())))
if not '0' in n:
    n['0'] = 0
if not '1' in n:
    n['1'] = 0

if n['?'] % 2 == 0:
    print(abs(n['1'] - n['0']))
else:
    print(abs(n['1'] - n['0']) - 1)

Submission status: Runtime Error

Solution code:
S =  input()

j = 0
diff = []
for ltr in S:
    if ltr == '?':
        j += 1
        # print(j)
        diff.append(j)
    else:   
        j = 0
if S[-1] == '?':
    print(max(diff) - min(diff))
else:
    print(max(diff))

Submission status: Runtime Error

Solution code:
a =  input()
X = a.count("0")
Y = a.count("1")
Z = a.count("?") % 2
q = (abs(X - Y) - Z)
input(q)

Submission status: Runtime Error

Solution code:
s=input()
qus=s.count("?")
zeros=s.count("0")
ones=s.count("1")
result=abs(zeros-ones)
if qus%2 ==1:
  result+= -1
max1=1
max2=0
last=""
news=""
for subs in s:
  if subs == "?":
    if last=="0":
      news+="1"
    elif last =="1":
      news+="0"
    else:
      if len(news)>1:
        if news[-1]=="0":
          news+=1
        else:
          news +=0
      else:
        news += "1"
    max1=1
    last=subs
    continue
  if last == subs:
    max1+=1
  else:
    max1=1
    last=subs
  max2=max(max1,max2)  
result=max(result,max2)
zeros=news.count("0")
ones=news.count("1")
max2=abs(zeros-ones)
result=max(result,max2)
max1=1
last=""
max2=0
for subs in news:
  if last == subs:
    max1+=1
  else:
    max1=1
    last=subs
  max2=max(max1,max2)  
result=max(result,max2)
print(result)

Submission status: Runtime Error

Solution code:
S = input()
def check(S):
    j = 0
    diff = []
    for ltr in S:
        if ltr == '?':
            j += 1
        else:
            if j not in diff:    
                diff.append(j)
            j = 0
    # print(diff)
    return max(diff)
print(check(S))