Jellyfish and Math (Codeforces 1875E)
Tags: DP, bitmasks

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):
import sys
import random
input = sys.stdin.readline
rd = random.randint(10 ** 9, 2 * 10 ** 9)
pow5 = [1]
for _ in range(8):
    pow5.append(pow5[-1] * 5)

def in_(a, b, m):
    return (a << 2) + (b << 1) + m

def out(c, d):
    return (c << 1) + d

def getBit(mask, i):
    return mask // pow5[i] % 5
Mx = 5 ** 8
dis = [10 ** 18] * Mx

def op(mask, o):
    ret = 0
    for i in range(8):
        t = getBit(mask, i)
        (c, d) = (t // 2, t % 2)
        m = i % 2
        if o == 0:
            c &= d
        elif o == 1:
            c |= d
        elif o == 2:
            d ^= c
        else:
            d ^= m
        ret += out(c, d) * pow5[i]
    return ret

def bfs(mask):
    from collections import deque
    q = deque([(mask, 0)])
    while q:
        (T, x) = q.popleft()
        if dis[T] <= x:
            continue
        dis[T] = x
        for o in range(4):
            q.append((op(T, o), x + 1))
bfs(288900)
for mask in range(Mx):
    if dis[mask] != 10 ** 18:
        continue
    for i in range(8):
        if getBit(mask, i) == 4:
            dis[mask] = min(dis[mask - pow5[i]], dis[mask - 2 * pow5[i]], dis[mask - 3 * pow5[i]], dis[mask - 4 * pow5[i]])
            break
t = int(input())
for _ in range(t):
    (a, b, c, d, m) = map(int, input().split())
    mask = Mx - 1
    for i in range(30):
        ai = a >> i & 1
        bi = b >> i & 1
        ci = c >> i & 1
        di = d >> i & 1
        mi = m >> i & 1
        bit = in_(ai, bi, mi)
        if getBit(mask, bit) == out(ci, di):
            continue
        elif getBit(mask, bit) == 4:
            mask += out(ci, di) * pow5[bit] - 4 * pow5[bit]
        else:
            print(-1)
            break
    else:
        print(dis[mask] if dis[mask] != 10 ** 18 else -1)

Solution (Python):
import io, os
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
op1 = [0, 1, 2, 3, 0, 1, 6, 7]
op2 = [0, 1, 6, 7, 4, 5, 6, 7]
op3 = [0, 1, 2, 3, 6, 7, 4, 5]
op4 = [0, 3, 2, 1, 4, 7, 6, 5]
op = [op1, op2, op3, op4]
graph = [{} for _ in range(128)]
queue = deque()
for num in range(1, 128):
    ele = []
    s = bin(num)[2:]
    s = '0' * (7 - len(s)) + s
    for i in range(7):
        if s[i] == '1':
            ele.append(i + 1)
    queue.append(tuple(ele))
    graph[num][tuple(ele)] = 0
    while queue:
        ele = queue.popleft()
        for d in range(4):
            temp = []
            for i in range(len(ele)):
                temp.append(op[d][ele[i]])
            nextele = tuple(temp)
            if nextele in graph[num]:
                continue
            graph[num][nextele] = graph[num][ele] + 1
            queue.append(nextele)

def main(t):
    (a, b, c, d, m) = map(int, input().split())
    if a == c and b == d:
        print(0)
        return
    mapping = [-1] * 8
    for digit in range(30):
        pre = (a & 1 << digit > 0) * 4 + (b & 1 << digit > 0) * 2 + (m & 1 << digit > 0)
        new = (c & 1 << digit > 0) * 4 + (d & 1 << digit > 0) * 2 + (m & 1 << digit > 0)
        if pre == 0 and new > 0:
            print(-1)
            return
        if mapping[pre] >= 0 and mapping[pre] != new:
            print(-1)
            return
        mapping[pre] = new
    num = 0
    ele = []
    for i in range(1, 8):
        num = num * 2 + (mapping[i] >= 0)
        if mapping[i] >= 0:
            ele.append(mapping[i])
    ele = tuple(ele)
    if ele not in graph[num]:
        print(-1)
        return
    print(graph[num][ele])
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
memo = {}
from collections import deque

def solve():
    (a, b, c, d, m) = map(int, input().split())
    D = {}
    for i in range(30):
        (ai, bi, ci, di, mi) = (a >> i & 1, b >> i & 1, c >> i & 1, d >> i & 1, m >> i & 1)
        if (ai, bi, mi) in D:
            if D[ai, bi, mi] != (ci, di):
                print(-1)
                return
        else:
            D[ai, bi, mi] = (ci, di)
    res = []
    for (ai, bi, mi) in D:
        (ci, di) = D[ai, bi, mi]
        res.append((ai, bi, mi, ci, di))
    res.sort()
    (A, B, C, D, M) = (0, 0, 0, 0, 0)
    n = len(res)
    for i in range(n):
        (ai, bi, mi, ci, di) = res[i]
        A |= ai << i
        B |= bi << i
        C |= ci << i
        D |= di << i
        M |= mi << i
    key = (n, A, B, M)
    if key not in memo:
        dist = {}
        dist[A, B] = 0
        todo = deque([(0, A, B)])
        while todo:
            (d, x, y) = todo.pop()
            if (x & y, y) not in dist:
                dist[x & y, y] = d + 1
                todo.appendleft((d + 1, x & y, y))
            if (x | y, y) not in dist:
                dist[x | y, y] = d + 1
                todo.appendleft((d + 1, x | y, y))
            if (x, x ^ y) not in dist:
                dist[x, x ^ y] = d + 1
                todo.appendleft((d + 1, x, x ^ y))
            if (x, y ^ M) not in dist:
                dist[x, y ^ M] = d + 1
                todo.appendleft((d + 1, x, y ^ M))
        memo[key] = dist
    if (C, D) in memo[key]:
        print(memo[key][C, D])
    else:
        print(-1)
for _ in range(int(input())):
    solve()