Bits and Pieces

Explicación

Sea $|$ la operación OR bit a bit y $\&$ la operación AND bit a bit.

La respuesta equivale a hallar un $x$ tal que $x=a_j\&a_k$ y $a_i|x$ se maximiza para tres índices $i<j<k$ .

Observemos que se puede buscar $x$ por bits, ya que $2^b>2^0+2^1+\dots+2^{b-1}$ , así que podemos recorrer cada $2^b$ en orden decreciente y comprobar si existe una respuesta para $z$ tal que $z$ es un superconjunto de $x|2^b$ . Cuando llegamos a un bit $2^b$ que ya está contenido en $a_i$ , no importa si está en el $x$ final porque $a_i|x$ ya contiene $2^b$ .

En otras palabras, hay que hallar un par $(j, k)$ tal que $i<j<k$ y $a_j\&a_k$ es un superconjunto de $x|2^b$ . Esto equivale a hallar $j$ y $k$ tales que $j, k>i$ , $a_j\supseteq x|2^b$ y $a_k\supseteq x|2^b$ . Esto se puede hacer con DP de suma sobre subconjuntos (o superconjuntos en este caso) manteniendo $f_x$ y $g_x$ , que guardan los dos $j$ más grandes tales que $a_j\supseteq x$ .

Implementación

Complejidad temporal: $\mathcal{O}(N\log A + A\log A)$ donde $A=\max a_i$ .

C++


#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6;
const int B = 21;
const int A = 1 << B;
 
int main() {
	int n;
	cin >> n;
 
	vector<int> a(n), f(A, -1), g(A, -1);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		// el segundo mayor pasa a ser el mayor; el mayor se actualiza a i
		f[a[i]] = g[a[i]];
		g[a[i]] = i;
	}
 
	for (int i = 0; i < B; i++) {
		for (int j = 0; j < A; j++) {
			if (j & (1 << i)) {
				int k = j ^ (1 << i);
				// actualizamos el mayor (g[k]) del superconjunto k al subconjunto j
				if (f[j] > g[k]) {  // caso 1: a la derecha
					f[k] = g[k], g[k] = f[j];
				} else if (f[j] > f[k]) {  // caso 2: en el medio
					f[k] = f[j];
				}
				// actualizamos el segundo mayor (f[k]) del superconjunto k al subconjunto j
				if (g[j] > g[k]) {  // caso 1: a la derecha
					f[k] = g[k], g[k] = g[j];
				} else if (g[j] > f[k]) {  // caso 2: en el medio
					f[k] = g[j];
				}
			}
		}
	}
 
	int ans = 0;
	for (int i = 0; i < n - 2; i++) {
		int c = 0;
		for (int j = B - 1; j >= 0; j--) {
			/*
			 * solo consideramos si a[i] no contiene 2^j y
			 * si el segundo mayor es mayor que i
			 */
			if ((a[i] & (1 << j)) == 0 && f[c | (1 << j)] > i) { c |= 1 << j; }
		}
		ans = max(ans, a[i] | c);
	}
 
	cout << ans << endl;
}