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

8

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 .XX=apap+1aqpqpq

He intentado este proceso: para todo . Lo precalculé en y luego el valor de para algunos , tal que es: . Así:sumi=a0a1aiiO(n)Xpq(pq)X=sumqsump1

MinAns=min(p,q) s.t. pqsumqsump1MaxAns=max(p,q) s.t. pqsumqsump1

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

palatok
fuente
1
¿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:

7

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

Básicamente, el problema es que, dado n , k -bitk enteros Si , encuentre i,j tal que SiSj 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.SiO(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.SjSjjSjSj

Haga esto para cada , y encontrará la respuesta en el tiempo .jO(nk)

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
1
@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(nk)klog2n
Karolis Juodelė
1
@Aryabhata, debido a ese límite, también podrías decir que el algoritmo es . Sin embargo, eso no es muy descriptivo. O(1)
Karolis Juodelė
1
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 ! nk
JeffE
1
@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
5

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.maxx¬xx=sumi¬xO(nlogn)

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. ¬x
Karolis Juodelė
sumi,sumj 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. sumik
Karolis Juodelė
4

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 .minsumap,aqp<qap=aqap=ap+1ap=x0yaq=x1zx,y,zq>p+1ap+1=xbwb=0apap+1<apaqb=1ap+1aq<apaqq=p+1

Yuval Filmus
fuente