Jellyfish and Math (Codeforces 1874B)
Tags: DP, shortest paths

Jellyfish is given the non-negative integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ and $$$m$$$. Initially $$$(x,y)=(a,b)$$$. Jellyfish wants to do several operations so that $$$(x,y)=(c,d)$$$.For each operation, she can do one of the following:  $$$x := x\,\&\,y$$$,  $$$x := x\,|\,y$$$,  $$$y := x \oplus y$$$,  $$$y := y \oplus m$$$. Here $$$\&$$$ denotes the bitwise AND operation, $$$|$$$ denotes the bitwise OR operation and $$$\oplus$$$ denotes the bitwise XOR operation.Now Jellyfish asks you for the minimum number of operations such that $$$(x,y)=(c,d)$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^5$$$). The description of the test cases follows.The only line of each test case contains five integers, $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ and $$$m$$$ ($$$0 \leq a, b, c, d, m < 2^{30}$$$).

Output: For each test case, output a single integer — the minimum number of operations. If this cannot be achieved, output $$$-1$$$ instead.

Note: In the first test case, we can do the operation $$$y = x \oplus y$$$.In the second test case, it is not possible to change $$$(x,y)=(1,2)$$$ using any sequence of operations.In the third test case, we can do the operation $$$x = x\,\&\,y$$$ followed by the operation $$$y = y \oplus m$$$.

Sample Inputs:
10
1 0 1 1 1
3 3 1 2 1
1 6 0 7 1
2 4 4 9 8
21 4 0 17 28
50 50 0 0 39
95 33 1 33 110
138 202 174 64 108
78 340 68 340 461
457 291 491 566 766

Sample Outputs:
1
-1
2
-1
-1
2
1
4
1
3

Solution (Python):
def f(n, i):
    return n >> i & 1
from collections import deque
import sys
input = sys.stdin.readline
print = sys.stdout.write
answer = {}
a1 = set()
for _ in range(int(input())):
    (a, b, c, d, m) = map(int, input().split())
    l = [-1] * 8
    ans = 0
    for i in range(30):
        if l[f(a, i) * 4 + f(b, i) * 2 + f(m, i)] not in [-1, f(c, i) * 2 + f(d, i)]:
            ans = -1
        else:
            l[f(a, i) * 4 + f(b, i) * 2 + f(m, i)] = f(c, i) * 2 + f(d, i)
    if ans == -1:
        print('-1\n')
        continue
    w1 = 0
    x1 = 0
    y = 0
    z = 0
    m1 = 0
    for i in range(8):
        if l[i] != -1:
            w1 ^= (1 << i) * (i // 4)
            x1 ^= (1 << i) * (i // 2 % 2)
            y ^= (1 << i) * (l[i] // 2)
            z ^= (1 << i) * (l[i] & 1)
            m1 ^= (1 << i) * (i & 1)
    if (w1, x1, m1) in a1:
        if (w1, x1, y, z, m1) in answer:
            print(str(answer[w1, x1, y, z, m1]) + '\n')
        else:
            print('-1\n')
        continue
    start = 0
    q = deque()
    q.append(w1 * 256 + x1)
    dist = {}
    dist[q[0]] = 0
    while len(q) > 0:
        a = q.popleft()
        w = a // 256
        x = a % 256
        answer[w1, x1, w, x, m1] = dist[a]
        for i in [256 * (w & x) + x, 256 * (w | x) + x, 256 * w + (w ^ x), 256 * w + (x ^ m1)]:
            if not i in dist:
                dist[i] = dist[a] + 1
                q.append(i)
    if not y * 256 + z in dist:
        dist[y * 256 + z] = -1
    print(str(dist[y * 256 + z]) + '\n')
    a1.add((w1, x1, m1))

Solution (Python):
def f(n, i):
    return n >> i & 1
from collections import deque
import sys
input = sys.stdin.readline
print = sys.stdout.write
answer = {}
a1 = set()
for _ in range(int(input())):
    (a, b, c, d, m) = map(int, input().split())
    l = [-1] * 8
    ans = 0
    for i in range(30):
        if l[f(a, i) * 4 + f(b, i) * 2 + f(m, i)] not in [-1, f(c, i) * 2 + f(d, i)]:
            ans = -1
        else:
            l[f(a, i) * 4 + f(b, i) * 2 + f(m, i)] = f(c, i) * 2 + f(d, i)
    if ans == -1:
        print('-1\n')
        continue
    w1 = 0
    x1 = 0
    y = 0
    z = 0
    m1 = 0
    for i in range(8):
        if l[i] != -1:
            w1 ^= (1 << i) * (i // 4)
            x1 ^= (1 << i) * (i // 2 % 2)
            y ^= (1 << i) * (l[i] // 2)
            z ^= (1 << i) * (l[i] & 1)
            m1 ^= (1 << i) * (i & 1)
    if (w1, x1, m1) in a1:
        if (w1, x1, y, z, m1) in answer:
            print(str(answer[w1, x1, y, z, m1]) + '\n')
        else:
            print('-1\n')
        continue
    start = 0
    q = deque()
    q.append(w1 * 256 + x1)
    dist = {}
    dist[q[0]] = 0
    while len(q) > 0:
        a = q.popleft()
        w = a // 256
        x = a % 256
        answer[w1, x1, w, x, m1] = dist[a]
        for i in [256 * (w & x) + x, 256 * (w | x) + x, 256 * w + (w ^ x), 256 * w + (x ^ m1)]:
            if not i in dist:
                dist[i] = dist[a] + 1
                q.append(i)
    if not y * 256 + z in dist:
        dist[y * 256 + z] = -1
    print(str(dist[y * 256 + z]) + '\n')
    a1.add((w1, x1, m1))
    assert len(answer) <= 22214

Solution (Python):
from collections import defaultdict
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
pow2 = [1]
for _ in range(30):
    pow2.append(2 * pow2[-1])
inf = pow(10, 9) + 1
ans1 = defaultdict(lambda : inf)
r = random.randint(1, pow2[30] - 1)
for i in range(pow2[8]):
    (x, y, m) = (0, 0, 0)
    for j in range(8):
        if i & pow2[j]:
            if j & 4:
                x ^= pow2[j]
            if j & 2:
                y ^= pow2[j]
            if j & 1:
                m ^= pow2[j]
    q = [(x, y)]
    dist = defaultdict(lambda : inf)
    dist[x, y] = 0
    for (x0, y0) in q:
        d0 = dist[x0, y0]
        for (x1, y1) in [(x0 & y0, y0), (x0 | y0, y0), (x0, x0 ^ y0), (x0, y0 ^ m)]:
            if dist[x1, y1] == inf:
                q.append((x1, y1))
                dist[x1, y1] = d0 + 1
    for (x0, y0) in q:
        u = [-1] * 8
        for j in range(8):
            if not i & pow2[j]:
                continue
            z = 0
            if x0 & pow2[j]:
                z ^= 2
            if y0 & pow2[j]:
                z ^= 1
            u[j] = z
        z = 0
        for j in u:
            z ^= j + 1
            z <<= 3
        ans1[z ^ r] = dist[x0, y0]
for _ in range(t):
    (a, b, c, d, m) = map(int, input().split())
    if not (a | b | m) & (c | d) == c | d:
        ans0 = -1
        ans.append(ans0)
        continue
    (u, v) = ([0] * 30, [0] * 30)
    for i in range(30):
        p = pow2[i]
        x1 = min(a & p, 1)
        x2 = min(b & p, 1)
        x3 = min(m & p, 1)
        x4 = min(c & p, 1)
        x5 = min(d & p, 1)
        u[i] = x1 << 2 ^ x2 << 1 ^ x3
        v[i] = x4 << 1 ^ x5
    x = [-1] * 8
    ok = 1
    for (i, j) in zip(u, v):
        if x[i] == -1:
            x[i] = j
        if x[i] ^ j:
            ok = 0
            break
    if not ok:
        ans0 = -1
        ans.append(ans0)
        continue
    z = 0
    for i in x:
        z ^= i + 1
        z <<= 3
    z ^= r
    ans0 = -1 if not z in ans1 else ans1[z]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))