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

8

Étant donné un tableau entier (taille maximale 50000), je dois trouver le minimum et le maximum X tel que X=apap+1aq pour certains p, q avec pq.

J'ai essayé ce processus: sumi=a0a1ai pour tous i. Je l'ai pré-calculé enO(n) puis la valeur de X pour certains p, q tel que (pq) est: X=sumqsump1. Donc:

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

Mais ce processus est de . Comment puis-je le faire plus efficacement?O(n2)

palatok
la source
1
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:

7

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

Fondamentalement, le problème est, étant donné n , k entiers Si , trouver i,j tels que SiSj 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 .SiO(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.SjSjjSjSj

Faites cela pour chaque , et vous trouverez la réponse en temps .jO(nk)

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
1
@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(nk)klog2n
Karolis Juodelė
1
@Aryabhata, à cause de cette limite, vous pourriez aussi bien dire que l'algorithme est . Ce n'est pas très descriptif cependant. O(1)
Karolis Juodelė
1
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 !! nk
JeffE
1
@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
5

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

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

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

Yuval Filmus
la source