Problem:


Score : 1000 points

Problem Statement

You have two strings A = A_1 A_2 ... A_n and B = B_1 B_2 ... B_n of the same length consisting of 0 and 1.

You can transform A using the following operations in any order and as many times as you want:

Shift A by one character to the left (i.e., if A = A_1 A_2 ... A_n, replace A with A_2 A_3 ... A_n A_1).

Shift A by one character to the right (i.e., if A = A_1 A_2 ... A_n, replace A with A_n A_1 A_2 ... A_{n-1}).

Choose any i such that B_i = 1. Flip A_i (i.e., set A_i = 1 - A_i).

You goal is to make strings A and B equal.

Print the smallest number of operations required to achieve this, or -1 if the goal is unreachable.

Constraints

1 \leq |A| = |B| \leq 2,000

A and B consist of 0 and 1.

Input

Input is given from Standard Input in the following format:

A
B

Output

Print the smallest number of operations required to make strings A and B equal, or -1 if the goal is unreachable.

Sample Input 1

1010
1100

Sample Output 1

3

Here is one fastest way to achieve the goal:

Flip A_1: A = 0010

Shift A to the left: A = 0100

Flip A_1 again: A = 1100

Sample Input 2

1
0

Sample Output 2

-1

There is no way to flip the only bit in A.

Sample Input 3

11010
10001

Sample Output 3

4

Here is one fastest way to achieve the goal:

Shift A to the right: A = 01101

Flip A_5: A = 01100

Shift A to the left: A = 11000

Shift A to the left again: A = 10001

Sample Input 4

0100100
1111111

Sample Output 4

5

Flip A_1, A_3, A_4, A_6 and A_7 in any order.



Sample input:
1010
1100


Sample output:
3

Submission status: Wrong Answer

Solution code:
# B 하나씩 shift하면서 타겟을 정함. 이제 A -> B' 만드는 게 목표
A = input()
B = input()
N = len(A)

if B.count('1') == 0 and A != B:
    print(-1)
    exit()

ans = int(2e18)

import bisect
for _ in range(N):
    # A -> B 만드는 게 목표임
    # 연산: B 왼쪽/오른쪽 shift, B가 1인 거 flip
    dif = [i for i in range(N) if B[i] == '1']
    tl = []
    tr = []

    for i in range(N):
        if A[i] != B[i]:
            candl = []
            if dif[0] < i:
                candl.append((N + dif[0]) - i)
            if dif[-1] >= i:
                candl.append(dif[bisect.bisect_left(dif, i)] - i)
            tl.append(min(candl) if len(candl) > 0 else int(1e9))

            candr = []
            if dif[-1] > i:
                candr.append(i - (dif[-1] - N))
            if dif[0] <= i:
                candr.append(i - dif[bisect.bisect_right(dif, i) - 1])
            tr.append(min(candr) if len(candr) > 0 else int(1e9))

    if len(tl) == 0:
        cur = 0
    else:
        cur = min(max(tl), max(tr))

        # 전략: only left, only right, left x -> right x+y, right y -> left x+y
        # x, y 정해놓고 min(2*x+y, x+2*y) = min(x,y) + x+y를 업뎃하면 됨. 어떻게 O(n)에?
        # x 고정하면 사라지는 index들 있고, 사라지지 않은 것들 중 최대가 y임. 그래서 역순 처리하면 뚝딱?
        posl = [[] for x in range(N)]
        for i, v in enumerate(tl): posl[v].append(i)

        y = 0
        for x in reversed(range(N)):
            # 왼쪽으로 x만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            for i in posl[x]:
                y = max(y, tr[i])
            cur = min(cur, x+2*y, 2*x+y)

    cur += len(tl) + min(_, N - _)

    ans = min(ans, cur)
    B = B[1:] + B[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF=10**18

A=list(map(lambda x:ord(x)-48,list(input())))
B=list(map(lambda x:ord(x)-48,list(input())))

fl=False

for i in B:
	fl|=i

if fl==False:
	for i in A:
		if i:
			print("-1")
			exit(0)
	print("0")
	exit(0)

n=len(A)

bi=[]

for i in range(n):
	bi.append([0,0,i])
	for j in range(n):
		if B[(i-j)%n]:
			bi[i][0]=-j
			break
	for j in range(n):
		if B[(i+j)%n]:
			bi[i][1]=j
			break

bi.sort()

ans=INF

def Update(d):
	q=[]
	nr=max(0,d)
	for i in range(n):
		x=bi[i][2]
		if A[x]!=B[(x+d)%n]:
			q.append(bi[i][:2])
	ans=INF
	for i in q:
		ans=min(ans,2*(nr-min(0,min(d,i[0])))-abs(d))
		nr=max(nr,i[1])
	ans=min(ans,2*(nr-min(0,d))-abs(d))+len(q)
	return ans

for i in range(-n,n):
	ans=min(ans,Update(i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF=10**18

A=list(map(lambda x:ord(x)-48,list(input())))
B=list(map(lambda x:ord(x)-48,list(input())))

fl=False

for i in B:
	fl|=i

if fl==False:
	for i in A:
		if i:
			print("-1")
			exit(0)
	print("0")
	exit(0)

n=len(A)

bi=[]

for i in range(n):
	bi.append([0,0])
	for j in range(n):
		if B[(i-j)%n]:
			bi[i][0]=-j
			break
	for j in range(n):
		if B[(i+j)%n]:
			bi[i][1]=j
			break

ans=INF

def Update(d):
	q=[]
	nr=max(0,d)
	for i in range(n):
		if A[i]!=B[(i+d)%n]:
			q.append(bi[i])
	q.sort()
	ans=INF
	for i in q:
		ans=min(ans,2*(nr-min(0,min(d,i[0])))-abs(d))
		nr=max(nr,i[1])
	ans=min(ans,2*(nr-min(0,d))-abs(d))+len(q)
	return ans

for i in range(-n,n):
	ans=min(ans,Update(i))

print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    N = len(A)

    if A == B:
        print(0)
        exit()
    if int(B) == 0:
        print(-1)
        exit()

    def solve(A, B):
        left = [0] * N
        right = [0] * N
        for i in range(N):
            for j in range(N):
                if B[(i-j)%N] == "1":
                    left[i] = j
                    break
        for i in range(N):
            for j in range(N):
                if B[(i+j)%N] == "1":
                    right[i] = j
                    break
        ret = 10**9
        for k in range(N):
            f = 0
            i_list = []
            for i in range(N):
                if A[i] != B[(i-k)%N]:
                    f += 1
                    i_list.append(i)
            lr = [0] * N
            lmax = 0
            rmax = 0
            for i in i_list:
                if left[i] <= k:
                    continue
                lr[left[i] - k] = max(lr[left[i] - k], right[i])
                lmax = max(lmax, left[i] - k)
            ret = min(ret, f + 2 * lmax + k)
            for l in range(N-1, 0, -1):
                rmax = max(rmax, lr[l])
                ret = min(ret, f + 2 * (l - 1 + rmax) + k)
        return ret
    print(min(solve(A, B), solve(A[::-1], B[::-1])))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
A=input()
B=input()
N=len(A)

if B.count("1")==0:
    if A==B:
        print(0)
    else:
        print(-1)
    exit()

L=[-1]*N
R=[-1]*N

for i in range(N):
    id=0
    while B[(i-id)%N]!="1":
        id+=1
    L[i]=id
    id=0
    while B[(i+id)%N]!="1":
        id+=1
    R[i]=id

ans=10**18

for i in range(N):
    #Left
    rtemp=[[] for j in range(N)]
    lmin=[i]*N
    for j in range(N):
        if A[j]!=B[(j-i)%N]:
            rtemp[R[j]].append(L[j])
    for j in range(N-2,-1,-1):
        temp=lmin[j+1]
        for val in rtemp[j+1]:
            temp=max(temp,val)
        lmin[j]=temp

    test=0
    for j in range(N):
        if A[(j+i)%N]!=B[j]:
            test+=1

    for j in range(N):
        temp=i+2*j+2*(lmin[j]-i)
        ans=min(test+temp,ans)

    #Right
    ltemp=[[] for j in range(N)]
    rmin=[N-i]*N
    for j in range(N):
        if A[j]!=B[(j-i)%N]:
            ltemp[L[j]].append(R[j])
    for j in range(N-2,-1,-1):
        temp=rmin[j+1]
        for val in ltemp[j+1]:
            temp=max(temp,val)
        rmin[j]=temp

    test=0
    for j in range(N):
        if A[(j+i)%N]!=B[j]:
            test+=1

    for j in range(N):
        temp=N-i+2*j+2*(rmin[j]-(N-i))
        ans=min(ans,test+temp)

print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#11:00

in1 = input()
in2 = input()
n = len(in1)
a,b = [],[]

for i in range(n):
    a.append(int(in1[i]))
    b.append(int(in2[i]))

if(sum(b)==0):
    if(sum(a)==0):
        print(0)
    else:
        print(-1)
    exit()

ok=1
for i in range(n):
    if(a[i]!=b[i]):
        ok=0
if(ok==1):
    print(0)
    exit()

####

left = []
rightest = -1-n
for i in range(n):
    if(b[i]==1):
        rightest = i-n

for i in range(n):
    if(b[i]==1):
        rightest = i
    left.append(rightest-i)


right = []
leftest = 2*n
for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i +n

for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i
    right.append(leftest - (n-1-i))
right = [right[n-1-i] for i in range(n)]

#print(left,right)

ans = 10**18
for i in range(n):
    toFix = [0 for i in range(n)]
    lrs = []
    for j in range(n):
        ij = (i+j)%n
        if(a[j]!=b[ij]):
            toFix[j]=1
            lrs.append([left[j],right[j]])
    lrs.sort(key = lambda x : x[0])
    #print(lrs)
    if(len(lrs)==0):
        ans = min(ans,i,n-i)
        continue
    leftmin = lrs[0][0]
    leftmax = lrs[-1][0]
    rightmin = n
    for j in lrs:
        rightmin = min(rightmin,j[1])
    
    rangemin = leftmin
    rangemax = leftmax
    for j in range(len(lrs)):
        dist = len(lrs)
        dist += abs(rangemin)
        dist += abs(rangemax-rangemin)
        dist1 = dist + abs(rangemax-i)
        dist2 = dist + abs(rangemax-(i-n))
        dist = len(lrs)
        dist += abs(rangemax)
        dist += abs(rangemax-rangemin)
        dist3 = dist + abs(rangemin-i)
        dist4 = dist + abs(rangemin-(i-n))
        #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
        ans = min(ans,dist1,dist2,dist3,dist4)

        rangemin = lrs[(j+1)%len(lrs)][0]
        rangemax = max(rangemax,lrs[j][1])
    rangemin = rightmin
    dist = len(lrs)
    dist += abs(rangemin)
    dist += abs(rangemax-rangemin)
    dist1 = dist + abs(rangemax-i)
    dist2 = dist + abs(rangemax-(i-n))
    dist = len(lrs)
    dist += abs(rangemax)
    dist += abs(rangemax-rangemin)
    dist3 = dist + abs(rangemin-i)
    dist4 = dist + abs(rangemin-(i-n))
    #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
    ans = min(ans,dist1,dist2,dist3,dist4)

    #print(i,"finish")

print(ans)

Submission status: Accepted

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

A = list(map(int, readline().strip()))
B = list(map(int, readline().strip()))
N = len(A)
Ao = A[:]
inf = 10**9+7
if sum(B):
    ans = inf
    CRo = [None]*N
    A2 = A + A
    B2 = B + B
    pre = None
    for i in range(2*N-1, N-1, -1):
        if B2[i]:
            pre = i
    for i in range(N-1, -1, -1):
        if B2[i]:
            pre = i
        CRo[i] = pre - i
    
    prel = None
    for i in range(N-1, -1, -1):
        if B[i]:
            prel = i - N
            break
    prer = None
    for i in range(N):
        if B[i]:
            prer = N + i
            break
    
    CLo = [None]*N
    pre = prel
    for i in range(N):
        if B[i]:
            pre = i
        CLo[i] = i - pre
    
    CR = CRo[:]
    for j in range(N):
        C = [a^b for a, b in zip(A, B)]
        for i in range(N):
            if B[i]:
                CR[i] = 0
        res = sum(C)
        if res >= ans:
            A = A[1:] + [A[0]]
            CR = CR[1:] + [CR[0]]
            continue
        CL = [0]*N
        pre = prel
        for i in range(N):
            if B[i]:
                pre = i
            if C[i]:
                CL[i] = i - pre
        
        mc = max(CL)
        table = [0]*(1+mc)
        for i in range(N):
            if CL[i]:
                table[CL[i]] = max(table[CL[i]], CR[i])
        cnt = min(N, 2*mc)
        for i in range(mc-1, -1, -1):
            table[i] = max(table[i+1], table[i])
        for i in range(mc):
            cnt = min(cnt, 2*i+2*table[i+1])
        ans = min(ans, res + cnt + j)

        A = A[1:] + [A[0]]
        CR = CR[1:] + [CR[0]]
    
    A = Ao
    CL = CLo[:]
    for j in range(N):
        C = [a^b for a, b in zip(A, B)]
        res = sum(C)
        for i in range(N):
            if B[i]:
                CL[i] = 0
        if res >= ans:
            A = [A[-1]] + A[:-1]
            CL = [CL[-1]] + CL[:-1]
            continue
        CR = [0]*N
        pre = prer
        for i in range(N-1, -1, -1):
            if B[i]:
                pre = i
            if C[i]:
                CR[i] = pre - i
        mc = max(CR)
        table = [0]*(mc+1)
        for i in range(N):
            if CR[i]:
                table[CR[i]] = max(table[CR[i]], CL[i])
        
        for i in range(mc-1, -1, -1):
            table[i] = max(table[i+1], table[i])
        cnt = min(N, 2*mc)
        for i in range(mc):
            cnt = min(cnt, 2*i+2*table[i+1])
        ans = min(ans, cnt + res + j)

        A = [A[-1]] + A[:-1]
        CL = [CL[-1]] + CL[:-1]
else:
    ans = -1 if sum(A) else 0
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    A,B=(list(map(int,input())) for _ in range(2))
    n=len(A)

    # B が全て0のときだけ例外処理
    if(all(b==0 for b in B)):
        if(all(a==0 for a in A)):
            print(0)
        else:
            print(-1)
        return

    def calc():
        L=[INF]*n # L[i]: i 以下で B の bit が立っているもののうち、i-L[i] が最大となるもの
        R=[INF]*n # R[i]: i 以上で B の bit が立っているもののうち、i+R[i] が最小となるもの

        tmp=0
        for i,b in enumerate(2*B):
            if(b==1):
                tmp=i
            if(i>=n):
                L[i-n]=i-tmp

        tmp=0
        for i,b in enumerate(2*B[::-1]):
            if(b==1):
                tmp=i
            if(i>=n):
                R[i-n]=i-tmp
        R.reverse()

        res=INF
        for d in range(n): # トータルの右シフトが d 回
            LR=[]
            cnt=0 # flip する回数
            for i in range(n):
                if(A[i]==B[(i+d)%n]): continue
                cnt+=1
                if(R[i]<=d): continue
                LR.append((L[i],R[i]-d))

            if(not LR): # 左右に余分に移動する必要が無い場合
                res=min(res,cnt+d)
                continue

            LR.sort()
            k=len(LR)
            X,Y=[[None]*k for _ in range(2)]
            for i in range(k):
                X[i],Y[i]=LR[i]
            for i in range(k-1,0,-1):
                Y[i-1]=max(Y[i-1],Y[i])

            score=min(X[-1],Y[0]) # maxX, maxY
            for i in range(k-1):
                score=min(score,X[i]+Y[i+1])
            res=min(res,cnt+d+score*2)
        return res

    ans=INF
    ans=min(ans,calc())
    A.reverse()
    B.reverse()
    ans=min(ans,calc())
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

A = np.array(list(readline().rstrip()),np.int32)-ord('0')
B = np.array(list(readline().rstrip()),np.int32)-ord('0')

N = len(A)

if np.count_nonzero(B)==0:
    if np.count_nonzero(A)==0:
        print(0)
    else:
        print(-1)
    exit()

def F(A,B):
    # 終了位置が右シフトしている場合
    # まず、B[0]=0となるようにシフト
    shift = np.where(B)[0][0]
    A = np.roll(A,-shift)
    B = np.roll(B,-shift)
    B2 = np.tile(B,2)
    # 自身の左右にある1の位置
    x = np.arange(N) * B; np.maximum.accumulate(x,out=x); left=x
    x = (N*(1-B) + np.arange(N)*B)[::-1]; np.minimum.accumulate(x,out=x); right = x[::-1]
    left = np.concatenate([left,left+N])
    right = np.concatenate([right,right+N])
    opt = 10**18
    for n in range(N+1):
        # 右にn回動かす
        diff = (A != B2[n:n+N]) # 書き換えるもの
        change_cost = np.count_nonzero(diff)
        move_left = np.maximum(0,np.arange(N) - np.maximum(left[:N],left[n:n+N]))
        move_left[~diff] = 0
        move_right = np.maximum(0,np.minimum(right[:N],right[n:n+N])-np.arange(n,n+N))
        move_right[~diff] = 0
        ind = (move_left)>0
        L=move_left[ind]; R=move_right[ind]
        I = np.lexsort((R,L)); L=L[I]; R=R[I]
        x = np.zeros(N,np.int32) # 左移動回数ごとの右移動回数
        x[L-1] = R
        x = x[::-1]; np.maximum.accumulate(x,out=x); x=x[::-1]
        move_cost = n + 2*(np.arange(N)+x).min()
        cost = move_cost + change_cost
        if opt > cost:
            opt = cost
    return opt

x = F(A,B)
A = A[::-1]; B = B[::-1]
y = F(A,B)
A = A[::-1]; B = B[::-1]
answer = min(x,y)
print(answer)

Submission status: Accepted

Solution code:
# B 하나씩 shift하면서 타겟을 정함. 이제 A -> B' 만드는 게 목표
A = input()
B = input()
N = len(A)

if B.count('1') == 0 and A != B:
    print(-1)
    exit()

ans = int(2e18)

ld = [i if B[i] == '1' else -int(1e9) for i in range(N)]
rd = [i if B[i] == '1' else  int(1e9) for i in range(N)]
for i in range(1, N): ld[i] = max(ld[i-1], ld[i])
for i in reversed(range(N-1)): rd[i] = min(rd[i+1], rd[i])

for _ in range(N): # right shift _ times
    # A -> B 만드는 게 목표임
    # 연산: B 왼쪽/오른쪽 shift, B가 1인 거 flip

    tl = []
    tr = []

    for i in range(N):
        if A[i] != B[i]:
            tl.append(min(rd[i] - i, (N + rd[0]) - i))
            tr.append(min(i - ld[i], i - (ld[-1] - N)))

    if len(tl) == 0:
        cur = min(_, N - _)
    else:
        cur = int(1e9)

        posl = [[] for x in range(N)]
        for i, v in enumerate(tl): posl[v].append(i)

        y = 0
        for x in reversed(range(N)):
            cur = min(cur, x+2*y+min((_-x+N)%N,(x-_+N)%N), 2*x+y+min((y-(-_)+N)%N,((-_)-y+N+N)%N))
            for i in posl[x]:
                y = max(y, tr[i])

        posr = [[] for y in range(N)]
        for i, v in enumerate(tr): posr[v].append(i)

        x = 0
        for y in reversed(range(N)):
            cur = min(cur, x+2*y+min((_-x+N)%N,(x-_+N)%N), 2*x+y+min((y-(-_)+N)%N,((-_)-y+N+N)%N))
            for i in posr[y]:
                x = max(x, tl[i])

    cur += len(tl)
    ans = min(ans, cur)
    B = B[1:] + B[0]

print(ans)

Submission status: Runtime Error

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#11:00

in1 = input()
in2 = input()
n = len(in1)
a,b = [],[]

for i in range(n):
    a.append(int(in1[i]))
    b.append(int(in2[i]))

if(sum(b)==0):
    if(sum(a)==0):
        print(0)
    else:
        print(-1)
    exit()

if(a==b):
    print(0)
    exit()
    
b3 = []
for i in range(3):
    for j in range(n):
        b3.append(b[j])

####

left = []
rightest = -1-n
for i in range(n):
    if(b[i]==1):
        rightest = i-n

for i in range(n):
    if(b[i]==1):
        rightest = i
    left.append(rightest-i)


right = []
leftest = 2*n
for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i +n

for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i
    right.append(leftest - (n-1-i))
right = [right[n-1-i] for i in range(n)]

#print(left,right)

ans = 10**18
for i in range(n):
    toFix = [0 for i in range(n)]
    lrs = []
    for j in range(n):
        ij = (i+j)%n
        if(a[j]!=b[ij]):
            toFix[j]=1
            lrs.append([left[j],right[j]])
    lrs.sort(key = lambda x : x[0])
    #print(lrs)
    leftmin = lrs[0][0]
    leftmax = lrs[-1][0]
    rightmin = n
    for j in lrs:
        rightmin = min(rightmin,j[1])
    
    rangemin = leftmin
    rangemax = leftmax
    for j in range(len(lrs)):
        dist = len(lrs)
        dist += abs(rangemin)
        dist += abs(rangemax-rangemin)
        dist1 = dist + abs(rangemax-i)
        dist2 = dist + abs(rangemax-(i-n))
        dist = len(lrs)
        dist += abs(rangemax)
        dist += abs(rangemax-rangemin)
        dist3 = dist + abs(rangemin-i)
        dist4 = dist + abs(rangemin-(i-n))
        #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
        ans = min(ans,dist1,dist2,dist3,dist4)

        rangemin = lrs[(j+1)%len(lrs)][0]
        rangemax = max(rangemax,lrs[j][1])
    rangemin = rightmin
    dist = len(lrs)
    dist += abs(rangemin)
    dist += abs(rangemax-rangemin)
    dist1 = dist + abs(rangemax-i)
    dist2 = dist + abs(rangemax-(i-n))
    dist = len(lrs)
    dist += abs(rangemax)
    dist += abs(rangemax-rangemin)
    dist3 = dist + abs(rangemin-i)
    dist4 = dist + abs(rangemin-(i-n))
    #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
    ans = min(ans,dist1,dist2,dist3,dist4)

    #print(i,"finish")

print(ans)

Submission status: Runtime Error

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#11:00

in1 = input()
in2 = input()
n = len(in1)
a,b = [],[]

for i in range(n):
    a.append(int(in1[i]))
    b.append(int(in2[i]))

if(sum(b)==0):
    if(sum(a)==0):
        print(0)
    else:
        print(-1)
    exit()

    
b3 = []
for i in range(3):
    for j in range(n):
        b3.append(b[j])

####

left = []
rightest = -1-n
for i in range(n):
    if(b[i]==1):
        rightest = i-n

for i in range(n):
    if(b[i]==1):
        rightest = i
    left.append(rightest-i)


right = []
leftest = 2*n
for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i +n

for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i
    right.append(leftest - (n-1-i))
right = [right[n-1-i] for i in range(n)]

#print(left,right)

ans = 10**18
for i in range(n):
    toFix = [0 for i in range(n)]
    lrs = []
    for j in range(n):
        ij = (i+j)%n
        if(a[j]!=b[ij]):
            toFix[j]=1
            lrs.append([left[j],right[j]])
    lrs.sort(key = lambda x : x[0])
    #print(lrs)
    leftmin = lrs[0][0]
    leftmax = lrs[-1][0]
    rightmin = n
    for j in lrs:
        rightmin = min(rightmin,j[1])
    
    rangemin = leftmin
    rangemax = leftmax
    for j in range(len(lrs)):
        dist = len(lrs)
        dist += abs(rangemin)
        dist += abs(rangemax-rangemin)
        dist1 = dist + abs(rangemax-i)
        dist2 = dist + abs(rangemax-(i-n))
        dist = len(lrs)
        dist += abs(rangemax)
        dist += abs(rangemax-rangemin)
        dist3 = dist + abs(rangemin-i)
        dist4 = dist + abs(rangemin-(i-n))
        #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
        ans = min(ans,dist1,dist2,dist3,dist4)

        rangemin = lrs[(j+1)%len(lrs)][0]
        rangemax = max(rangemax,lrs[j][1])
    rangemin = rightmin
    dist = len(lrs)
    dist += abs(rangemin)
    dist += abs(rangemax-rangemin)
    dist1 = dist + abs(rangemax-i)
    dist2 = dist + abs(rangemax-(i-n))
    dist = len(lrs)
    dist += abs(rangemax)
    dist += abs(rangemax-rangemin)
    dist3 = dist + abs(rangemin-i)
    dist4 = dist + abs(rangemin-(i-n))
    #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
    ans = min(ans,dist1,dist2,dist3,dist4)

    #print(i,"finish")

print(ans)