En el problema Chip Factory (HDU5536), se proporciona una secuencia de n números enteros. El objetivo es encontrar tres índices distintos i, j y k de tal manera que la expresión (s_i + s_j) XOR s_k se maximice.

El enfoque de fuerza bruta es factible debido al límite de tiempo indulgente de 9 segundos, ya que itera sobre todas las combinaciones triples. Sin embargo, también se puedee emplear un trie binario (01 trie) para optimizar el rendimeinto. Es esencial almacenar los elementos s_i en el trie y realizar consultas sobre (s_j + s_k), en lugar de almacenar (s_i + s_j) y buscar s_k, para evitar teimpos de ejecución excesivos.

Implementación de Fuerza Bruta

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int pruebas;
    cin >> pruebas;
    while (pruebas--) {
        int cantidad;
        cin >> cantidad;
        vector<int> numeros(cantidad);
        for (int idx = 0; idx < cantidad; idx++) {
            cin >> numeros[idx];
        }
        long long maximo = -1;
        for (int a = 0; a < cantidad; a++) {
            for (int b = a + 1; b < cantidad; b++) {
                for (int c = b + 1; c < cantidad; c++) {
                    long long suma_ab = numeros[a] + numeros[b];
                    maximo = max(maximo, suma_ab ^ numeros[c]);
                    long long suma_ac = numeros[a] + numeros[c];
                    maximo = max(maximo, suma_ac ^ numeros[b]);
                    long long suma_bc = numeros[b] + numeros[c];
                    maximo = max(maximo, suma_bc ^ numeros[a]);
                }
            }
        }
        cout << maximo << endl;
    }
    return 0;
}

Solución con Trie Binario (01 Trie)

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_NODOS = 130000;
const int BITS = 31;

struct NodoArbol {
    int contador;
    int subarboles[2];
    void inicializar() {
        contador = 0;
        subarboles[0] = subarboles[1] = -1;
    }
};

NodoArbol trie[MAX_NODOS];
int siguiente_libre;

void insertar(int valor, int raiz) {
    int actual = raiz;
    for (int bit = BITS - 1; bit >= 0; bit--) {
        int digito = (valor >> bit) & 1;
        if (trie[actual].subarboles[digito] == -1) {
            trie[siguiente_libre].inicializar();
            trie[actual].subarboles[digito] = siguiente_libre++;
        }
        actual = trie[actual].subarboles[digito];
        trie[actual].contador++;
    }
}

long long buscar_maximo(int valor, int raiz) {
    int actual = raiz;
    long long resultado = 0;
    for (int bit = BITS - 1; bit >= 0; bit--) {
        int digito = (valor >> bit) & 1;
        int opuesto = 1 - digito;
        if (trie[actual].subarboles[opuesto] != -1 && trie[trie[actual].subarboles[opuesto]].contador > 0) {
            resultado |= (1LL << bit);
            actual = trie[actual].subarboles[opuesto];
        } else {
            actual = trie[actual].subarboles[digito];
        }
    }
    return resultado;
}

void eliminar(int valor, int raiz) {
    int actual = raiz;
    for (int bit = BITS - 1; bit >= 0; bit--) {
        int digito = (valor >> bit) & 1;
        actual = trie[actual].subarboles[digito];
        trie[actual].contador--;
    }
}

int main() {
    int pruebas;
    cin >> pruebas;
    while (pruebas--) {
        int cantidad;
        cin >> cantidad;
        vector<int> datos(cantidad);
        siguiente_libre = 1;
        trie[0].inicializar();
        for (int i = 0; i < cantidad; i++) {
            cin >> datos[i];
            insertar(datos[i], 0);
        }
        long long respuesta = -1;
        for (int i = 0; i < cantidad; i++) {
            eliminar(datos[i], 0);
            for (int j = 0; j < i; j++) {
                if (i == j) continue;
                eliminar(datos[j], 0);
                long long consulta = buscar_maximo(datos[i] + datos[j], 0);
                respuesta = max(respuesta, consulta);
                insertar(datos[j], 0);
            }
            insertar(datos[i], 0);
        }
        cout << respuesta << endl;
    }
    return 0;
}