Encontrar el máximo y mínimo de valores XOR consecutivos

Dada una matriz entera (tamaño máximo 50000), tengo que encontrar la mínima y máxima de tal manera que para alguna , con . $X$ $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ $p$ $q$ $p \leq q$

He intentado este proceso: para todo . Lo precalculé en y luego el valor de para algunos , tal que es: . Así: $\text{sum}_i = a_0 \oplus a_1 \oplus \dots \oplus a_i$ $i$ $O(n)$ $X$ $p$ $q$ $(p\leq q)$ $X = \text{sum}_q \oplus \text{sum}_{p-1}$

M i n A n s = min_{(p, q) s.t. p \leq q} {sum}_{q} \oplus {sum}_{p - 1} M a x A n s = max_{(p, q) s.t. p \leq q} {sum}_{q} \oplus {sum}_{p - 1}

$\mathrm{MinAns} = \min_{(p,q) \text{ s.t. } p\le q}{\text{sum}_q \oplus \text{sum}_{p-1}} \\ \mathrm{MaxAns} = \max_{(p,q) \text{ s.t. } p\le q}{\text{sum}_q \oplus \text{sum}_{p-1}} \\$

Pero este proceso es de $O(n^2)$ . ¿Cómo puedo hacer eso de manera más eficiente?

algorithms algorithm-analysis performance binary-arithmetic arithmetic palatok
fuente

¿Has considerado ordenar tu lista de 'suma'? Parece que los valores adyacentes serían más propensos a cancelar muchos bits y terminar cerca de 0.

Craig Gidney

Respuestas:

Si $k$ es el tamaño de bits de los enteros, puede calcular el Max en tiempo $O(n k)$ .

Básicamente, el problema es que, dado $n$ , $k$ enteros $S_i$ , encuentre $i,j$ tal que $S_i \oplus S_j$ es máximo.

cada como una cadena binaria (mirando la representación binaria) y crea un trie a partir de esas cadenas. Esto lleva tiempo. $S_i$ $O(nk)$

Ahora, para cada , intentas recorrer el complemento de en el trie que creaste (tomando la mejor rama básicamente en cada paso), encontrando una tal que sea máxima. $S_j$ $S_j$ $j'$ $S_j \oplus S_{j'}$

Haga esto para cada , y encontrará la respuesta en el tiempo . $j$ $O(n k)$

Dado que sus enteros están acotados, este algoritmo para max es básicamente lineal, y también lo es el algoritmo para min obtenido al ordenar (ya que la clasificación se puede hacer en tiempo lineal).

Por cierto, si no hubiera límites, puede reducir la distinción de elementos a la versión mínima.

Aryabhata
fuente

"Básicamente, el problema es que, dados n, enteros de k bits Si, encuentre i, j tal que Si⊕Sj sea máximo". No entiendo esta línea. quiero que Si⊕Si + 1⊕ ... ⊕ Sj sea el máximo?

corrígeme

@Aryabhata, es injusto considerar lineal. Después de todo, , (a menos que la lista pueda tener duplicados). Sin embargo, sigue siendo una buena solución.

O (n k)

$O(nk)$

k \geq \log_{2} n

$k \geq \log_2 n$

Karolis Juodelė

@Aryabhata, debido a ese límite, también podrías decir que el algoritmo es . Sin embargo, eso no es muy descriptivo.

O (1)

$O(1)$

Karolis Juodelė

La pregunta no dice que los enteros están delimitados; dice que la matriz tiene un tamaño máximo de 50000. ¡De hecho, es constante, no !

n

$n$

k

$k$

JeffE

@JeffE: ¡Oh! Y ahora que usted señala (y estoy de acuerdo con esa interpretación), los comentarios de Karolis ahora tienen sentido para mí. ¡Gracias!

Aryabhata

La clasificación también ayuda con . Un poquito, al menos. Claramente, alcanzaría el máximo . Entonces, para cada una búsqueda binaria de . Ese es el tiempo , igual que la clasificación, por lo que sigue siendo la complejidad de todo el procedimiento. $\max$ $x \oplus \neg x$ $x = \text{sum}_i$ $\neg x$ $O(n \log n)$

Karolis Juodelė
fuente

¿Qué pasa con el valor mínimo?

palatok

¿Qué pasa si no encuentro ¬x?

palatok

@palatok, el valor mínimo ya se explicó. Si no encuentra , verifique las dos sumas más cercanas a donde estaría.

\neg x

$\neg x$

Karolis Juodelė

s u m_{i}, s u m_{j}

$sum_i, sum_j$ debe ser 0 o 1. La tabla hash será suficiente.

Strin

@Strin, no entiendo a qué te refieres. tiene una longitud de bits. ¿Cómo sería útil una tabla hash? Cerrar, no se necesitan valores exactos.

{sum}_{i}

$\text{sum}_i$

k

$k$

Karolis Juodelė

Aquí es por qué la sugerencia de Strilanc funciona para . Considere su matriz , y suponga que logra el mínimo , donde . O bien (en cuyo caso ), o , para algunos . Suponga , y deje . Si entonces , mientras que si entonces . Por lo tanto . $\min$ $\mathrm{sum}$ $a_p,a_q$ $p<q$ $a_p = a_q$ $a_p = a_{p+1}$ $a_p = x0y$ $a_q = x1z$ $x,y,z$ $q > p+1$ $a_{p+1} = xbw$ $b = 0$ $a_p \oplus a_{p+1} < a_p \oplus a_q$ $b = 1$ $a_{p+1} \oplus a_q < a_p \oplus a_q$ $q = p+1$

Yuval Filmus
fuente