XOR and Distance (Codeforces 1553H)
Tags: Others, divide and conquer

You are given an array $$$a$$$ consisting of $$$n$$$ distinct elements and an integer $$$k$$$. Each element in the array is a non-negative integer not exceeding $$$2^k-1$$$.Let's define the XOR distance for a number $$$x$$$ as the value of $$$$$$f(x) = \min\limits_{i = 1}^{n} \min\limits_{j = i + 1}^{n} |(a_i \oplus x) - (a_j \oplus x)|,$$$$$$where $$$\oplus$$$ denotes the bitwise XOR operation.For every integer $$$x$$$ from $$$0$$$ to $$$2^k-1$$$, you have to calculate $$$f(x)$$$.

Input: The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le 19$$$; $$$2 \le n \le 2^k$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^k-1$$$). All these integers are distinct.

Output: Print $$$2^k$$$ integers. The $$$i$$$-th of them should be equal to $$$f(i-1)$$$.

Note: Consider the first example:  for $$$x = 0$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[6, 0, 3]$$$, and the minimum absolute difference of two elements is $$$3$$$;  for $$$x = 1$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[7, 1, 2]$$$, and the minimum absolute difference of two elements is $$$1$$$;  for $$$x = 2$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[4, 2, 1]$$$, and the minimum absolute difference of two elements is $$$1$$$;  for $$$x = 3$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[5, 3, 0]$$$, and the minimum absolute difference of two elements is $$$2$$$;  for $$$x = 4$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[2, 4, 7]$$$, and the minimum absolute difference of two elements is $$$2$$$;  for $$$x = 5$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[3, 5, 6]$$$, and the minimum absolute difference of two elements is $$$1$$$;  for $$$x = 6$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[0, 6, 5]$$$, and the minimum absolute difference of two elements is $$$1$$$;  for $$$x = 7$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[1, 7, 4]$$$, and the minimum absolute difference of two elements is $$$3$$$. 

Sample Inputs:
3 3
6 0 3

3 4
13 4 2

Sample Outputs:
3 1 1 2 2 1 1 3

2 2 6 6 3 1 2 2 2 2 1 3 6 6 2 2

Solution (Python):
import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = [*map(int, input().split())]
N = 1 << k
ma = [-N] * N
mi = [N] * N
dp = [N] * N
for v in a:
    ma[v] = mi[v] = 0
for i in range(k):
    nma = ma[:]
    nmi = mi[:]
    ndp = dp[:]
    for x in range(N):
        M = 1 << i
        y = x ^ M
        ma[x] = max(nma[x], nma[y] + M)
        mi[x] = min(nmi[x], nmi[y] + M)
        dp[x] = min(ndp[x], ndp[y], nmi[y] + (M - nma[x]))
print(*dp)

Solution (Python):
import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = [*map(int, input().split())]
N = 1 << k
ma = [[-N] * N for _ in range(k + 1)]
mi = [[N] * N for _ in range(k + 1)]
dp = [[N] * N for _ in range(k + 1)]
for v in a:
    ma[0][v] = mi[0][v] = 0
for i in range(k):
    for x in range(N):
        M = 1 << i
        y = x ^ M
        ma[i + 1][x] = max(ma[i][x], ma[i][y] + M)
        mi[i + 1][x] = min(mi[i][x], mi[i][y] + M)
        dp[i + 1][x] = min(dp[i][x], dp[i][y], mi[i][y] + (M - ma[i][x]))
print(*dp[k])

Solution (Python):
import sys
input = sys.stdin.readline
N = 1 << 19
K = 20
ma = [[-N] * N for _ in range(K)]
mi = [[N] * N for _ in range(K)]
dp = [[N] * N for _ in range(K)]
(n, k) = map(int, input().split())
a = [*map(int, input().split())]
for v in a:
    ma[0][v] = mi[0][v] = 0
for i in range(k):
    for x in range(1 << k):
        M = 1 << i
        y = x ^ M
        ma[i + 1][x] = max(ma[i][x], ma[i][y] + M)
        mi[i + 1][x] = min(mi[i][x], mi[i][y] + M)
        dp[i + 1][x] = min(dp[i][x], dp[i][y], mi[i][y] + (M - ma[i][x]))
print(*dp[k][:1 << k])