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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7


A=S()
B=S()
n=len(B)
A*=2
B*=2
l=[0]*n
r=[0]*n
for i in range(n):
    if A[i]!=B[i]:
        for j in range(n):
            if B[(i+j)%n]=="1":
                r[i]=j
                break
        for k in range(n):
            if B[(i-k)%n]=="1":
                l[i]=k
                break

D=[0]*n
for m in range(n):
    ret=0
    ss=[]
    for h in range(n):
        if D[h]:
            continue
        if B[(m+h)%n]:
            D[h]=1
        else:
            r[h]-=1
            ss+=l[h]
            ss+=r[h]
    ss.sort()
    
    ss*=2
    





print(l, r)

Submission status: Wrong Answer

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

####

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)
exit()
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: Wrong Answer

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)]
        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 + min(N, 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)
        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+min(N, 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: Wrong Answer

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)]
        res = sum(C)
        if res >= ans:
            if A[0] == 1:
                A = A[1:] + [1]
            else:
                A = A[1:] + [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 + min(N, 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)
        if res >= ans:
            if A[-1] == 1:
                A = [1] + A[:-1]
            else:
                A = [0] + A[:-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+min(N, 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: Wrong Answer

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
    
    for j in range(N):
        C = [a^b for a, b in zip(A, B)]
        res = sum(C)
        if res >= ans:
            if A[0] == 1:
                A = A[1:] + [1]
            else:
                A = A[1:] + [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]], CRo[i])
        
        cnt = 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, i + table[i+1])
        ans = min(ans, res + cnt + j)
        
        
        if A[0] == 1:
            A = A[1:] + [1]
        else:
            A = A[1:] + [0]
    
    A = Ao
    for j in range(N):
        C = [a^b for a, b in zip(A, B)]
        res = sum(C)
        if res >= ans:
            if A[-1] == 1:
                A = [1] + A[:-1]
            else:
                A = [0] + A[:-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]], CLo[i])
        
        for i in range(mc-1, -1, -1):
            table[i] = max(table[i+1], table[i])
        cnt = mc
        for i in range(mc):
            cnt = min(cnt, i+table[i+1])
        ans = min(ans, cnt + res + j)
        if A[-1] == 1:
            A = [1] + A[:-1]
        else:
            A = [0] + A[:-1]
else:
    ans = inf
    for i in range(N):
        if all(a==b for a, b in zip(A, B)):
            ans = min(ans, min(i, N-i))
        if A[-1] == 1:
            A = [1] + A[:-1]
        else:
            A = [0] + A[:-1]
    if ans == inf:
        ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
A = input("")
B = input("")

def left(x):
	return x[1:] + x[0]

def right(x):
	return x[-1] + x[:-2]

def rev(x,y):
	return bin(int(x,2) ^ 1<<(len(x)-y+1))

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)

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+(_-x+N)%N, 2*x+y+(y+_)%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+(_-x+N)%N, 2*x+y+(y+_)%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: 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)

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+(_-x+N)%N, 2*x+y+(y+_)%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+(_-x+N)%N, 2*x+y+(y+_)%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: 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)

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):
    # 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 = 0
    else:
        cur = min(max(tl), max(tr))

        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, 2*x+y)
            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, 2*x+y)
            for i in posr[y]:
                x = max(x, tl[i])

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

print(ans)

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

    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 = 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만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            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)):
            # 왼쪽으로 x만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            for i in posr[y]:
                x = max(x, tl[i])

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

print(ans)

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

    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 = 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만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            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)):
            # 왼쪽으로 x만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            for i in posr[y]:
                x = max(x, tl[i])

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

print(ans)

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
    ld = [i if B[i] == '1' else -1 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])

    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 = 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만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            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)):
            # 왼쪽으로 x만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            for i in posr[y]:
                x = max(x, tl[i])

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

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

print(ans)

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
    ld = [i if B[i] == '1' else -1 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])

    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 = 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만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            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)):
            # 왼쪽으로 x만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            for i in posr[y]:
                x = max(x, tr[i])

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

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

print(ans)

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']
    ld = [i if B[i] == '1' else -1 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])

    tl = []
    tr = []

    for i in range(N):
        if A[i] != B[i]:
            candl = []
            if dif[0] < i:
                candl.append((N + dif[0]) - i)
            if rd[i] >= i:
                candl.append(rd[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 ld[i] <= i:
                candr.append(i - ld[i])
            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만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            for i in posl[x]:
                y = max(y, tr[i])

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

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

print(ans)

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']
    ld = [i if B[i] == '1' else 0 for i in range(N)]
    rd = [i if B[i] == '1' else 0 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] = max(rd[i+1], rd[i])

    tl = []
    tr = []

    for i in range(N):
        if A[i] != B[i]:
            candl = []
            if dif[0] < i:
                candl.append((N + dif[0]) - i)
            if rd[i] >= i:
                candl.append(rd[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 ld[i] <= i:
                candr.append(i - ld[i])
            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만큼 갔다. 오른쪽으론 얼마만큼만 가면 되나?
            cur = min(cur, x+2*y, 2*x+y)
            for i in posl[x]:
                y = max(y, tr[i])

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

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

print(ans)