Trouver le maximum et le minimum de valeurs XOR consécutives

Étant donné un tableau entier (taille maximale 50000), je dois trouver le minimum et le maximum $X$ tel que $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ pour certains $p$ , $q$ avec $p \leq q$ .

J'ai essayé ce processus: $\text{sum}_i = a_0 \oplus a_1 \oplus \dots \oplus a_i$ pour tous $i$ . Je l'ai pré-calculé en $O(n)$ puis la valeur de $X$ pour certains $p$ , $q$ tel que $(p\leq q)$ est: $X = \text{sum}_q \oplus \text{sum}_{p-1}$ . Donc:

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}} \\$

Mais ce processus est de . Comment puis-je le faire plus efficacement? $O(n^2)$

algorithms algorithm-analysis performance binary-arithmetic arithmetic palatok
la source

Avez-vous envisagé de trier votre liste de «somme»? Il semble que les valeurs adjacentes seraient plus susceptibles d'annuler beaucoup de bits et de se retrouver près de 0.

Craig Gidney

Réponses:

Si $k$ est la taille des bits des entiers, alors vous pouvez calculer le temps Max en $O(n k)$ .

Fondamentalement, le problème est, étant donné $n$ , $k$ entiers $S_i$ , trouver $i,j$ tels que $S_i \oplus S_j$ est maximum.

Vous traitez chaque comme une chaîne binaire (en regardant la représentation binaire) et créez un trie à partir de ces chaînes. Cela prend du temps . $S_i$ $O(nk)$

Maintenant, pour chaque , vous essayez de parcourir le complément de dans le trie que vous avez créé (en prenant la meilleure branche à chaque étape en gros), en trouvant un tel que est maximum. $S_j$ $S_j$ $j'$ $S_j \oplus S_{j'}$

Faites cela pour chaque , et vous trouverez la réponse en temps . $j$ $O(n k)$

Puisque vos entiers sont bornés, cet algorithme pour max est fondamentalement linéaire, tout comme l'algorithme pour min obtenu par tri (car le tri peut être effectué en temps linéaire).

Soit dit en passant, s'il n'y avait pas de limites, vous pouvez réduire la distinction des éléments à la version min.

Aryabhata
la source

"Fondamentalement, le problème est, étant donné n, k entiers Si, trouver i, j tel que Si⊕Sj est maximum." Je ne comprends pas cette ligne. je veux que Si⊕Si + 1⊕ ... ⊕ Sj soit maximum? corrigez-moi si je manque quelque chose

palatok

@Aryabhata, il est injuste de considérer linéaire. Après tout, , (sauf si la liste peut avoir des doublons). C'est quand même une bonne solution.

O (n k)

$O(nk)$

k \geq \log_{2} n

$k \geq \log_2 n$

Karolis Juodelė

@Aryabhata, à cause de cette limite, vous pourriez aussi bien dire que l'algorithme est . Ce n'est pas très descriptif cependant.

O (1)

$O(1)$

Karolis Juodelė

La question ne dit pas que les entiers sont bornés; il dit que la taille du tableau est au plus de 50000. Donc en fait, est constant, pas !!

n

$n$

k

$k$

JeffE

@JeffE: Oh! Et maintenant que vous le signalez (et je suis d'accord avec cette interprétation), les commentaires de Karolis ont tous un sens pour moi maintenant. Merci!

Aryabhata

Le tri est également utile avec . Un peu au moins. De toute évidence, le maximum serait atteint par . Donc pour chaque faites une recherche binaire pour . Il s'agit du temps , identique au tri, de sorte que la complexité de toute la procédure reste à régler. $\max$ $x \oplus \neg x$ $x = \text{sum}_i$ $\neg x$ $O(n \log n)$

Karolis Juodelė
la source

qu'en est-il de la valeur min?

palatok

que faire si je ne trouve pas ¬x?

palatok

@palatok, la valeur min a déjà été expliquée. Si vous ne trouvez pas , vérifiez les deux sommes les plus proches de l'endroit où il se trouverait.

\neg x

$\neg x$

Karolis Juodelė

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

$sum_i, sum_j$ devrait être 0 ou 1. La table de hachage suffira.

Strin

@Strin, je ne vois pas ce que tu veux dire. longueur de bits. Comment une table de hachage serait-elle utile - des valeurs proches et non exactes sont nécessaires.

{sum}_{i}

$\text{sum}_i$

k

$k$

Karolis Juodelė

Voici pourquoi la suggestion de Strilanc fonctionne pour . Considérez votre tableau , et supposez que le minimum est atteint par , où . Soit (auquel cas ), soit , pour certains . Supposons , et laissons . Si alors , tandis que si alors . Donc . $\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
la source