Finden des Maximums und Minimums aufeinanderfolgender XOR-Werte

Bei einem ganzzahligen Array (maximale Größe 50000) muss ich das minimale und maximale $X$ so finden, dass für einige , mit . $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ $p$ $q$ $p \leq q$

Ich habe diesen Prozess ausprobiert: für alle . Ich habe es in vorberechnet und dann den Wert von für einige , so, dass ist: . Somit: $\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}} \\$

Aber dieser Prozess ist von $O(n^2)$ . Wie kann ich das effizienter machen?

algorithms algorithm-analysis performance binary-arithmetic arithmetic Palatok
quelle

Haben Sie darüber nachgedacht, Ihre Summenliste zu sortieren? Es scheint, als würden benachbarte Werte mit größerer Wahrscheinlichkeit viele Bits aufheben und nahe 0 enden.

Craig Gidney

Antworten:

Wenn die Bitgröße der ganzen Zahlen ist, können Sie das Maximum in berechnen . $k$ $O(n k)$

Grundsätzlich besteht das Problem darin, bei , Bit-Ganzzahlen so zu finden dass maximal ist. $n$ $k$ $S_i$ $i,j$ $S_i \oplus S_j$

Sie behandeln jedes als eine binäre Zeichenfolge (mit Blick auf die binäre Darstellung) und erstellen aus diesen Zeichenfolgen einen Versuch. Dies dauert Zeit. $S_i$ $O(nk)$

Nun versuchen Sie für jedes , das Komplement von in dem von Ihnen erstellten Versuch zu (wobei Sie bei jedem Schritt im Grunde genommen den besten Zweig nehmen) und finden ein so dass maximal ist. $S_j$ $S_j$ $j'$ $S_j \oplus S_{j'}$

Tun Sie dies für jedes , und Sie finden die Antwort in Zeit. $j$ $O(n k)$

Da Ihre ganzen Zahlen begrenzt sind, ist dieser Algorithmus für max grundsätzlich linear, ebenso wie der Algorithmus für min, der durch Sortieren erhalten wird (da das Sortieren in linearer Zeit erfolgen kann).

Übrigens, wenn es keine Grenzen gab, können Sie die Elementunterscheidbarkeit auf die Min-Version reduzieren.

Aryabhata
quelle

"Grundsätzlich besteht das Problem darin, bei n, k-Bit-Ganzzahlen Si i, j so zu finden, dass Si⊕Sj maximal ist." Ich verstehe diese Zeile nicht. Ich möchte, dass Si⊕Si + 1⊕ ... ⊕ Sj maximal ist? Korrigieren Sie mich, wenn ich etwas vermisse

Palatok

@Aryabhata, es ist unfair,

linear zu betrachten. Immerhin ist

(es sei denn, die Liste kann Duplikate enthalten). Es ist trotzdem eine schöne Lösung.

O (n k)

$O(nk)$

k \geq \log_{2} n

$k \geq \log_2 n$

Karolis Juodelė

@Aryabhata, aufgrund dieser Grenze könnte man genauso gut sagen, dass der Algorithmus

. Das ist allerdings nicht sehr beschreibend.

O (1)

$O(1)$

Karolis Juodelė

Die Frage besagt nicht , dass die ganzen Zahlen begrenzt sind; es heißt, dass das Array eine Größe von höchstens 50000 hat. Tatsächlich ist

also konstant, nicht

n

$n$

k

$k$

JeffE

@ JeffE: Oh! Und jetzt, wo Sie darauf hinweisen (und ich stimme dieser Interpretation zu), sind Karolis 'Kommentare für mich jetzt alle sinnvoll. Vielen Dank!

Aryabhata

Sortieren hilft auch bei . Zumindest ein bisschen. Es ist klar, dass das Maximum durch erreicht werden würde . Also mache für jede eine binäre Suche nach . Das ist Zeit, genau wie beim Sortieren, so dass die Komplexität des gesamten Verfahrens erhalten bleibt. $\max$ $x \oplus \neg x$ $x = \text{sum}_i$ $\neg x$ $O(n \log n)$

Karolis Juodelė
quelle

Was ist mit dem Mindestwert?

Palatok

Was ist, wenn ich ¬x nicht finde?

Palatok

@palatok, min Wert wurde bereits erklärt. Wenn Sie

nicht finden , überprüfen Sie die beiden Summen, die der Position am nächsten liegen.

\neg x

$\neg x$

Karolis Juodelė

sollte 0 oder 1 sein. Eine Hash-Tabelle wird ausreichen.

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

$sum_i, sum_j$

Strin

@ Strin, ich verstehe nicht was du meinst.

ist

Bits lang. Wie wäre eine Hash-Tabelle nützlich? Es werden enge, nicht genaue Werte benötigt.

{sum}_{i}

$\text{sum}_i$

k

$k$

Karolis Juodelė

Hier ist, warum Strilancs Vorschlag für funktioniert . Betrachten Sie Ihr Array und nehmen Sie an, dass das Minimum durch , wobei . Entweder (in diesem Fall ) oder , für einige $\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$ . Angenommen, , und lassen Sie . Wenn dann ist , während wenn dann ist . Daher ist $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
quelle