Lisa and the Martians

Pista

Inventa algunos pares aleatorios de $a$ y $b$ , y elige $x$ para maximizar $(a \oplus x) \& (b \oplus x)$ . ¿Notas algún patrón? Esto puede ser más fácil si escribes todo en binario.

Solución

Análisis oficial (C++)

Explicación

Para hallar el máximo de $(a \oplus x) \& (b \oplus x)$ de dos enteros entre muchos, podemos dividir esta tarea en dos partes:

Hallar el máximo de dos enteros dados
Comparar los máximos y elegir el más alto

Parte 1

Enfoquémonos primero en hallar el máximo de $(a \oplus x) \& (b \oplus x)$ de dos enteros dados $a$ y $b$ . Para quienes no están del todo familiarizados con las operaciones de bits, esta expresión puede parecer intimidante. Pero no hay que temer, ya que todas las operaciones de bits son independientes entre dígitos, podemos simplificar nuestro caso a interacciones de un solo dígito.

Vemos que si tanto $a$ como $b$ son 1 o 0, siempre podemos hacer que la suma final de $\&$ sea 1 manipulando nuestro $x$ . Por el contrario, si $a$ y $b$ son opuestos, no importa qué $x$ elijamos, siempre dará 0.

Si damos un paso atrás y miramos el panorama completo, entonces para elegir $x$ que maximice la suma de $\&$ de los dos, todo lo que necesitamos saber es el número de dígitos en los que comparten un bit en común.

Parte 2

Ahora la pregunta que debemos hacernos es: dados dos pares de enteros $(a_1, b_1)$ y $(a_2, b_2)$ , ¿cuál suma máxima de $\&$ es más alta?

Esta pregunta es fácil de responder. Como solo los dígitos de dos enteros que comparten un bit en común pueden dar un 1 en la suma final de $\&$ . El par que comparte un bit en común más a la izquierda que el otro tiene una suma de $\&$ más alta. En otras palabras, su suma $\oplus$ es la menor de las dos.

Extendiendo esto a $n$ ( $\sim 10^5$ ) enteros, vemos que formar $n^2$ pares de enteros y compararlos todos es inviable. Así que aquí hacemos la siguiente observación importante: los ordenamos. En una lista ordenada de enteros, todo lo que necesitamos comparar son los pares adyacentes de enteros.

¿Por qué es cierto? Consideremos tres enteros $a, b, c$ en esta lista ordenada. Es imposible que $a$ y $c$ tengan una suma $\oplus$ menor que $a$ y $b$ . Porque $b$ siempre compartirá más bits tempranos con $a$ que $c$ con $a$ , debido a que están ordenados.

Implementación

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, k;
		cin >> n >> k;
		vector<pair<int, int>> nums(n);
		for (int i = 0; i < n; i++) {
			cin >> nums[i].first;
			nums[i].second = i + 1;
		}
		sort(nums.begin(), nums.end());
 
		int mins = INT_MAX;
		int curr = 0;
		for (int i = 0; i < n - 1; i++) {
			if ((nums[i].first ^ nums[i + 1].first) < mins) {
				mins = (nums[i].first ^ nums[i + 1].first);
				curr = i;
			}
		}
 
		cout << nums[curr].second << " " << nums[curr + 1].second << " ";
		cout << (nums[curr].first ^ ((1 << k) - 1)) << "\n";
	}
}


import java.io.*;
import java.util.*;
 
public class LisaAndMartians {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int testNum = sc.nextInt();
		for (int t = 0; t < testNum; t++) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			int[][] nums = new int[n][2];
			for (int i = 0; i < n; i++) {
				nums[i][0] = sc.nextInt();
				nums[i][1] = i + 1;
			}
			Arrays.sort(nums, Arrays::compare);
 
			int mins = Integer.MAX_VALUE;
			int curr = 0;
			for (int i = 0; i < n - 1; i++) {
				if ((nums[i][0] ^ nums[i + 1][0]) < mins) {
					mins = (nums[i][0] ^ nums[i + 1][0]);
					curr = i;
				}
			}
 
			System.out.print(nums[curr][1] + " " + nums[curr + 1][1] + " ");
			System.out.println((nums[curr][0] ^ ((1 << k) - 1)));
		}
	}
}


for _ in range(int(input())):
	n, k = map(int, input().split())
	arr = [int(i) for i in input().split()]
	nums = [(arr[i], i + 1) for i in range(n)]
	nums.sort()
 
	mins = float("inf")
	curr = 0
	for i in range(n - 1):
		if nums[i][0] ^ nums[i + 1][0] < mins:
			mins = nums[i][0] ^ nums[i + 1][0]
			curr = i
 
	print(f"{nums[curr][1]} {nums[curr + 1][1]} {nums[curr][0] ^ ((1 << k) - 1)}")