Lisa and the Martians (Codeforces 1851F)
Tags: Math, strings

Lisa was kidnapped by martians! It okay, because she has watched a lot of TV shows about aliens, so she knows what awaits her. Let's call integer martian if it is a non-negative integer and strictly less than $$$2^k$$$, for example, when $$$k = 12$$$, the numbers $$$51$$$, $$$1960$$$, $$$0$$$ are martian, and the numbers $$$\pi$$$, $$$-1$$$, $$$\frac{21}{8}$$$, $$$4096$$$ are not.The aliens will give Lisa $$$n$$$ martian numbers $$$a_1, a_2, \ldots, a_n$$$. Then they will ask her to name any martian number $$$x$$$. After that, Lisa will select a pair of numbers $$$a_i, a_j$$$ ($$$i \neq j$$$) in the given sequence and count $$$(a_i \oplus x) \& (a_j \oplus x)$$$. The operation $$$\oplus$$$ means Bitwise exclusive OR, the operation $$$\&$$$ means Bitwise And. For example, $$$(5 \oplus 17) \& (23 \oplus 17) = (00101_2 \oplus 10001_2) \& (10111_2 \oplus 10001_2) = 10100_2 \& 00110_2 = 00100_2 = 4$$$.Lisa is sure that the higher the calculated value, the higher her chances of returning home. Help the girl choose such $$$i, j, x$$$ that maximize the calculated value.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of testcases.Each testcase is described by two lines.The first line contains integers $$$n, k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 30$$$) — the length of the sequence of martian numbers and the value of $$$k$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^k$$$) — a sequence of martian numbers.It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print three integers $$$i, j, x$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$, $$$0 \le x < 2^k$$$). The value of $$$(a_i \oplus x) \& (a_j \oplus x)$$$ should be the maximum possible.If there are several solutions, you can print any one.

Note: First testcase: $$$(3 \oplus 14) \& (1 \oplus 14) = (0011_2 \oplus 1110_2) \& (0001_2 \oplus 1110_2) = 1101_2 = 1101_2 \& 1111_2 = 1101_2 = 13$$$.Second testcase: $$$(1 \oplus 0) \& (1 \oplus 0) = 1$$$.Third testcase: $$$(9 \oplus 4082) \& (13 \oplus 4082) = 4091$$$.Fourth testcase: $$$(3 \oplus 7) \& (0 \oplus 7) = 4$$$.

Sample Inputs:
10
5 4
3 9 1 4 13
3 1
1 0 1
6 12
144 1580 1024 100 9 13
4 3
7 3 0 4
3 2
0 0 1
2 4
12 2
9 4
6 14 9 4 4 4 5 10 2
2 1
1 0
2 4
11 4
9 4
2 11 10 1 6 9 11 0 5

Sample Outputs:
1 3 14
1 3 0
5 6 4082
2 3 7
1 2 3
1 2 15
4 5 11
1 2 0
1 2 0
2 7 4

Solution (Python):
for _ in range(int(input())):
    _1 = input().split()
    a = input().split()
    k = int(_1[1])
    for i in range(len(a)):
        a[i] = int(a[i])
    l = a.copy()
    a.sort()
    lowest = a[0] ^ a[1]
    g = a[0]
    f = a[1]
    for b in range(len(a)):
        if b != len(a) - 1:
            if a[b] ^ a[b + 1] < lowest:
                lowest = a[b] ^ a[b + 1]
                g = a[b]
                f = a[b + 1]
    g_index = l.index(g)
    f_index = l.index(f, g_index + 1) if l.index(f) == l.index(g) else l.index(f)
    x = (1 << k) - 1 ^ g
    print(str(g_index + 1) + ' ' + str(f_index + 1) + ' ' + str(x))

Solution (Python):
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    arr = sorted(((int(e), i) for (i, e) in enumerate(input().split())))
    axorb = float('inf')
    for t in range(n - 1):
        ((a, i), (b, j)) = (arr[t], arr[t + 1])
        if axorb > a ^ b:
            axorb = a ^ b
            resa = a
            resb = b
            (resi, resj) = (i, j)
    res = 0
    for i in range(k):
        res += 1 - ((1 << i & resa) >> i) << i
    print(resi + 1, resj + 1, res)

Solution (Python):
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    ar = [[a[i], i + 1] for i in range(n)]
    ar.sort()
    m = 10 ** 12
    (f, s) = (-1, -1)
    for i in range(1, n):
        if m > ar[i - 1][0] ^ ar[i][0]:
            f = ar[i - 1][1]
            s = ar[i][1]
            m = ar[i - 1][0] ^ ar[i][0]
    ans = (1 << k) - 1 - (a[f - 1] | a[s - 1])
    print(f, s, ans)