Zero-One (Easy Version) (Codeforces 1733D1)
Tags: Greedy, constructive algorithms

This is the easy version of the problem. In this version, $$$n \le 3000$$$, $$$x \ge y$$$ holds. You can make hacks only if both versions of the problem are solved.You are given two binary strings $$$a$$$ and $$$b$$$, both of length $$$n$$$. You can do the following operation any number of times (possibly zero).   Select two indices $$$l$$$ and $$$r$$$ ($$$l < r$$$).  Change $$$a_l$$$ to $$$(1 - a_l)$$$, and $$$a_r$$$ to $$$(1 - a_r)$$$.  If $$$l + 1 = r$$$, the cost of the operation is $$$x$$$. Otherwise, the cost is $$$y$$$. You have to find the minimum cost needed to make $$$a$$$ equal to $$$b$$$ or say there is no way to do so.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 600$$$) — the number of test cases.Each test case consists of three lines. The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$5 \le n \le 3000$$$, $$$1 \le y \le x \le 10^9$$$) — the length of the strings, and the costs per operation.The second line of each test case contains the string $$$a$$$ of length $$$n$$$. The string only consists of digits $$$0$$$ and $$$1$$$.The third line of each test case contains the string $$$b$$$ of length $$$n$$$. The string only consists of digits $$$0$$$ and $$$1$$$.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3000$$$.

Output: For each test case, if there is no way to make $$$a$$$ equal to $$$b$$$, print $$$-1$$$. Otherwise, print the minimum cost needed to make $$$a$$$ equal to $$$b$$$.

Note: In the first test case, selecting indices $$$2$$$ and $$$3$$$ costs $$$8$$$, which is the minimum possible cost.In the second test case, we cannot make $$$a$$$ equal to $$$b$$$ using any number of operations.In the third test case, we can perform the following operations:  Select indices $$$3$$$ and $$$6$$$. It costs $$$3$$$, and $$$a$$$ is 0101011 now.  Select indices $$$4$$$ and $$$6$$$. It costs $$$3$$$, and $$$a$$$ is 0100001 now. The total cost is $$$6$$$.In the fourth test case, we don't have to perform any operations.

Sample Inputs:
4
5 8 7
01001
00101
5 7 2
01000
11011
7 8 3
0111001
0100001
5 10 1
01100
01100

Sample Outputs:
8
-1
6
0

Solution (Python):
test = int(input())
while test > 0:
    test -= 1
    (n, x, y) = map(int, input().split())
    str1 = input()
    str2 = input()
    singles = 0
    doublles = 0
    curr = 0
    ans = 0
    for i in range(n):
        if str1[i] != str2[i]:
            curr += 1
        else:
            if curr == 2:
                doublles += 1
            else:
                ans += y * (curr // 2)
                if curr % 2 == 1:
                    singles += 1
            curr = 0
    if curr == 2:
        doublles += 1
    else:
        ans += y * (curr // 2)
        if curr % 2 == 1:
            singles += 1
        curr = 0
    extr = True
    if ans > 0:
        extr = False
    if singles % 2 == 1:
        print('-1')
        continue
    ans += 2 * y * (doublles // 2)
    ans += y * (singles // 2)
    if doublles == 1 and singles == 0 and extr:
        ans += min(2 * y, x)
    elif doublles % 2 == 1:
        ans += y
    print(ans)

Solution (Python):
t = int(input())
for i in range(0, t):
    (n, x, y) = map(int, input().split())
    a = input()
    b = input()
    cnt = 0
    for i in range(0, n):
        if a[i] != b[i]:
            cnt += 1
    if cnt % 2 == 1:
        print(-1)
    else:
        ans = None
        if cnt > 2:
            print(y * (cnt // 2))
        else:
            flag = True
            for i in range(0, n - 1):
                if a[i] != b[i] and a[i + 1] != b[i + 1]:
                    if n == 3:
                        ans = x
                    elif n == 4:
                        if i == 0 or i == 3:
                            ans = min(x, y * 2)
                        else:
                            ans = x
                    else:
                        ans = min(x, y * 2)
                    flag = False
            if flag == True:
                print(y * (cnt // 2))
            else:
                print(ans)

Solution (Python):
t = int(input())
for _ in range(t):
    (n, x, y) = map(int, input().split())
    a = input()
    b = input()
    d = []
    for i in range(n):
        if int(a[i]) ^ int(b[i]) == 1:
            d.append(i)
    length = len(d)
    if length == 2:
        if d[0] + 1 == d[1]:
            print(min(x, 2 * y))
        else:
            print(y)
    elif length % 2 == 1:
        print(-1)
    else:
        print(length // 2 * y)