Problem:


Score : 1400 points

Problem Statement

You are given strings s and t, both of length N.
s and t consist of 0 and 1. Additionally, in these strings, the same character never occurs three or more times in a row.

You can modify s by repeatedly performing the following operation:

Choose an index i (1 \leq i \leq N) freely and invert the i-th character in s (that is, replace 0 with 1, and 1 with 0), under the condition that the same character would not occur three or more times in a row in s after the operation.

Your objective is to make s equal to t.
Find the minimum number of operations required.

Constraints

1 \leq N \leq 5000

The lengths of s and t are both N.

s and t consists of 0 and 1.

In s and t, the same character never occurs three or more times in a row.

Input

Input is given from Standard Input in the following format:

N
s
t

Output

Find the minimum number of operations required to make s equal to t. It can be proved that the objective is always achievable in a finite number of operations.

Sample Input 1

4
0011
0101

Sample Output 1

4

One possible solution is 0011 → 1011 → 1001 → 1101 → 0101.

Sample Input 2

1
0
0

Sample Output 2

0

Sample Input 3

8
00110011
10101010

Sample Output 3

10



Sample input:
4
0011
0101


Sample output:
4

Submission status: Wrong Answer

Solution code:
def solve(N, s, t):
  if s == t: return 0
  if N == 1: return 1
  return bin(s ^ t).count('1') + N - 2

N = int(input())
s = int(input(), 2)
t = int(input(), 2)

print(solve(N, s, t))

Submission status: Runtime Error

Solution code:
def calc_m_value(M, A, B, N, h):
    return min([M[h - A[i]]+B[i] if A[i] <= h else B[i] for i in range(N)])

H, N = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

M = [0] * (H+1)
for i in range(1, H+1):
    M[i] = calc_m_value(M, A, B, N, i)

print(M[H])

Submission status: Runtime Error

Solution code:
# input
N = int(input())
S = input()
T = input()

# red nad blue bar pos
sr, sb = [], []
tr, tb = [], []
for i in range(N-1):
    if S[i:i+2] == '01':
        sr.append(i+1)
    if S[i:i+2] == '10':
        sb.append(i+1)
    if T[i:i+2] == '01':
        tr.append(i+1)
    if T[i:i+2] == '10':
        tb.append(i+1)

def dist(s, t):
    long, short = (s, t) if len(s) > len(t) else t, s
    dif = len(long) - len(short)
    res = []
    for ofs in range(dif + 1):
        fit = [0] * ofs + short + [N] * (dif-ofs)
        res.append(sum(abs(a-b) for a, b in zip(fit, long)))
    return res

dr, db = dist(sr, tr), dist(sb, tb)
long, short = (dr, db) if len(dr) > len(db) else db, dr
dif = len(long) - len(short)
res = []
for ofs in range(dif + 1):
    res.append(min(a+b for a, b in zip(short, long[ofs:ofs+len(short)])))

print(min(res))

Submission status: Runtime Error

Solution code:
# input
N = int(input())
S = input()
T = input()

# red nad blue bar pos
sr, sb = [], []
tr, tb = [], []
for i in range(N-1):
    if S[i:i+2] == '01':
        sr.append(i+1)
    if S[i:i+2] == '10':
        sb.append(i+1)
    if T[i:i+2] == '01':
        tr.append(i+1)
    if T[i:i+2] == '10':
        tb.append(i+1)

def dist(s, t):
    long, short = (s, t) if len(s) > len(t) else t, s
    dif = len(long) - len(short)
    res = []
    for ofs in range(dif + 1):
        fit = [0] * ofs + short + [N] * dif
        res.append(sum(abs(a-b) for a, b in zip(fit, long)))
    return min(res)

print(dist(sr, tr) + dist(sb, tb))

Submission status: Runtime Error

Solution code:
N = int(input())
s = input()
t = input()

# N=4
# s="0011"
# t="0101"

# N=1
# s="0"
# t="0"

# N=8
# s="00110011"
# t="10101010"

s_list = [True if i == "1" else False for i in s]
t_list = [True if i == "1" else False for i in t]
operation_num = 0

def change(index):
    global operation_num

    if (index == 0 or index == N - 1):
        prev_check = True
    else:
        prev_check = s_list[index] != s_list[index - 1] or s_list[index] != s_list[index + 1]

    if (index >= N - 2):
        post_check = True
    else:
        post_check = s_list[index] != s_list[index + 1] or s_list[index] != s_list[index + 2]

    if (not (prev_check and post_check)):
        change(index + 1)

    s_list[index] = not s_list[index]
    operation_num = operation_num + 1
#    print("change() >> operation:{} index:{} list:{}".format(operation_num, index, s_list))


for i in range(N):
    if s_list[i] != t_list[i]:
        change(i)

print(operation_num)

Submission status: Runtime Error

Solution code:
N = int(input())
s = input()
t = input()

# N = 8
# s = "0011" * 2
# t = "1010" * 2
s_list = [i for i in range(N-1) if s[i:i+2] in ("00", "11")]
s_list2 = [-1 for i in range(N+1)] + s_list + [(N-1) for i in range(N+1)]
t_list = [i for i in range(N-1) if t[i:i+2] in ("00", "11")]
ans = 10 ** 10
if s[0] == t[0]:
    for i in range(-(len(t_list) + len(s_list))//2 - 1, len(t_list) + len(s_list) + 2):
        new_ans = sum([abs(a-b) for a, b in zip(s_list2[N+1+2*i:N+1+2*i+len(t_list)], t_list)])
        if N+1+2*i > N+1:
            new_ans += sum(s_list2[N+1:min(N+1+2*i, N+1+len(s_list2))]) + min(2*i, len(s_list2))
        if N+1+len(s_list) > N+1+2*i+len(t_list):
            new_ans += (N-1) * (N+1+len(s_list) - max(N+1+2*i+len(t_list), N+1)) - \
                       sum(s_list2[max(N+1+2*i+len(t_list), N+1):N+1+len(s_list)])
        if new_ans < ans:
            ans = new_ans
else:
    add_one = 0
    if s_list[0] == 0:
        s_list = s_list[1:]
        s_list2 = [-1 for i in range(N + 1)] + s_list + [N for i in range(N + 1)]
        add_one = 1
    for i in range(-(len(t_list) + len(s_list))//2 - 1, len(t_list) + len(s_list) + 2):
        new_ans = sum([abs(a-b) for a, b in zip(s_list2[N+1+2*i:N+1+2*i+len(t_list)], t_list)])
        if N+1+2*i > N+1:
            new_ans += sum(s_list2[N+1:min(N+1+2*i, N+1+len(s_list2))]) + min(2*i, len(s_list2))
        if N+1+len(s_list) > N+1+2*i+len(t_list):
            new_ans += (N-1) * (N+1+len(s_list) - max(N+1+2*i+len(t_list), N+1)) - \
                       sum(s_list2[max(N+1+2*i+len(t_list), N+1):N+1+len(s_list)])
        if new_ans + add_one < ans:
            ans = new_ans + add_one
print(str(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
s = input()
t = input()

# N = 8
# s = "0011" * 2
# t = "1010" * 2
s_list = [i for i in range(N-1) if s[i:i+2] in ("00", "11")]
s_list2 = [-1 for i in range(N+1)] + s_list + [(N-1) for i in range(N+1)]
t_list = [i for i in range(N-1) if t[i:i+2] in ("00", "11")]
ans = 10 ** 10
if s[0] == t[0]:
    for i in range(-(len(t_list) + len(s_list))//2 - 1, len(t_list) + len(s_list) + 2):
        new_ans = sum([abs(a-b) for a, b in zip(s_list2[N+1+2*i:N+1+2*i+len(t_list)], t_list)])
        if N+1+2*i > N+1:
            new_ans += sum(s_list2[N+1:min(N+1+2*i, N+1+len(s_list2))]) + min(2*i, len(s_list2))
        if N+1+len(s_list) > N+1+2*i+len(t_list):
            new_ans += (N-1) * (N+1+len(s_list) - max(N+1+2*i+len(t_list), N+1)) - \
                       sum(s_list2[max(N+1+2*i+len(t_list), N+1):N+1+len(s_list)])
        if new_ans < ans:
            ans = new_ans
else:
    add_one = 0
    if s_list[0] == 0:
        s_list = s_list[1:]
        s_list2 = [-1 for i in range(N + 1)] + s_list + [N for i in range(N + 1)]
        add_one = 1
    for i in range(-(len(t_list) + len(s_list))//2 - 1, len(t_list) + len(s_list) + 2):
        new_ans = sum([abs(a-b) for a, b in zip(s_list2[N+1+2*i:N+1+2*i+len(t_list)], t_list)])
        if N+1+2*i > N+1:
            new_ans += sum(s_list2[N+1:min(N+1+2*i, N+1+len(s_list2))]) + min(2*i, len(s_list2))
        if N+1+len(s_list) > N+1+2*i+len(t_list):
            new_ans += (N-1) * (N+1+len(s_list) - max(N+1+2*i+len(t_list), N+1)) - \
                       sum(s_list2[max(N+1+2*i+len(t_list), N+1):N+1+len(s_list)])
        if new_ans < ans + add_one:
            ans = new_ans + add_one
print(str(ans))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
S = np.array(list(map(int,list(input()))),dtype=np.int)
T = np.array(list(map(int,list(input()))),dtype=np.int)

def lessthan3(s,t,N,k,f):
    if k >= N:
        return 0
    elif s[k]==t[k]:
        if f==0:
            return lessthan3(s,t,N,k+1,0)
        elif f==1:
            if k < N-1:
                return lessthan3(s,t,N,k+1,2)
            else:
                s[k] ^= 1
                return lessthan3(s,t,N,k,1) + 1
        else:
            s[k] ^= 1
            return lessthan3(s,t,N,k,2) + 1
    elif (k >= 2 and s[k-1]==t[k] and s[k-2] == t[k]) or (N-k >= 3 and s[k+1]==t[k] and s[k+2]==t[k]) or (k>=1 and N-k>=2 and s[k-1]==t[k] and s[k+1]==t[k]):
        return lessthan3(s,t,N,k+1,1)+1
#    elif f==0:
    else:
        s[k] = t[k]
        return lessthan3(s,t,N,k+1,0)+1
#    else:
#        return lessthan3(s,t,N,k-f,0)

print(lessthan3(S,T,N,0,0))