Menemukan nilai XOR maksimum dan minimum berturut-turut

Diberikan array integer (ukuran maksimum 50000), saya harus menemukan minimum dan maksimum sehingga untuk beberapa , dengan . $X$ $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ $p$ $q$ $p \leq q$

Saya telah mencoba proses ini: untuk semua . Saya pra-menghitungnya dalam dan kemudian nilai untuk beberapa , sedemikian rupa sehingga adalah: . Jadi: $\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}} \\$

Tetapi proses ini dari . Bagaimana saya bisa melakukannya dengan lebih efisien? $O(n^2)$

algorithms algorithm-analysis performance binary-arithmetic arithmetic palatok
sumber

Sudahkah Anda mempertimbangkan untuk mengurutkan daftar 'jumlah' Anda? Sepertinya nilai yang berdekatan akan lebih cenderung membatalkan banyak bit dan berakhir di dekat 0.

Craig Gidney

Jawaban:

Jika adalah bitsize dari bilangan bulat, maka Anda dapat menghitung waktu Maks dalam . $k$ $O(n k)$

Pada dasarnya, masalahnya adalah, mengingat , bit integer , temukan sehingga maksimum. $n$ $k$ $S_i$ $i,j$ $S_i \oplus S_j$

Anda memperlakukan setiap sebagai string biner (melihat representasi biner), dan membuat trie dari string tersebut. Ini membutuhkan waktu . $S_i$ $O(nk)$

Sekarang untuk setiap , Anda mencoba menjalankan pelengkap dalam trie yang Anda buat (mengambil cabang terbaik pada setiap langkah pada dasarnya), menemukan sedemikian rupa sehingga maksimum. $S_j$ $S_j$ $j'$ $S_j \oplus S_{j'}$

Lakukan ini untuk setiap , dan Anda menemukan jawabannya dalam waktu . $j$ $O(n k)$

Karena bilangan bulat Anda dibatasi, algoritma ini untuk max pada dasarnya linier, dan begitu pula algoritma untuk min didapat dengan menyortir (karena penyortiran dapat dilakukan dalam waktu linier).

Kebetulan, jika tidak ada batasan, maka Anda dapat mengurangi perbedaan elemen ke versi min.

Aryabhata
sumber

"Pada dasarnya, masalahnya adalah, mengingat n, bilangan bulat k-bit Si, temukan i, j sedemikian rupa sehingga Si⊕Sj maksimum." Saya tidak mengerti baris ini. saya ingin Si⊕Si + 1⊕ ... ⊕ Sj menjadi maksimum? koreksi saya jika saya kehilangan sesuatu

palatok

@Aryabhata, tidak adil untuk mempertimbangkan linear. Lagi pula, , (kecuali daftar dapat memiliki duplikat). Ini masih merupakan solusi yang bagus.

O (n k)

$O(nk)$

k \geq \log_{2} n

$k \geq \log_2 n$

Karolis Juodelė

@ Aryabhata, karena itu Anda mungkin mengatakan algoritma adalah . Itu tidak terlalu deskriptif.

O (1)

$O(1)$

Karolis Juodelė

Pertanyaannya tidak mengatakan bahwa bilangan bulat dibatasi; ia mengatakan bahwa array memiliki ukuran paling banyak 50.000. Jadi sebenarnya adalah konstan, bukan !!

n

$n$

k

$k$

JeffE

@ Jeff: Oh! Dan sekarang setelah Anda tunjukkan (dan saya setuju dengan interpretasi itu), komentar Karolis semuanya masuk akal bagi saya sekarang. Terima kasih!

Aryabhata

Penyortiran juga membantu dengan . Sedikit, setidaknya. Jelas, maksimum akan dicapai oleh . Jadi untuk setiap lakukan pencarian biner untuk . Itu waktu, sama dengan penyortiran, sehingga tetap menjadi kerumitan seluruh prosedur. $\max$ $x \oplus \neg x$ $x = \text{sum}_i$ $\neg x$ $O(n \log n)$

Karolis Juodelė
sumber

bagaimana dengan nilai min?

palatok

bagaimana jika saya tidak menemukan ¬x?

palatok

@palatok, nilai min sudah dijelaskan. Jika Anda tidak menemukan , periksa dua jumlah yang paling dekat dengan tempat itu.

\neg x

$\neg x$

Karolis Juodelė

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

$sum_i, sum_j$ harus 0 atau 1. Tabel hash sudah cukup.

Strin

@ Strin, saya tidak mengerti maksud Anda. adalah bit panjang. Bagaimana tabel hash berguna - tutup, bukan nilai yang tepat diperlukan.

{sum}_{i}

$\text{sum}_i$

k

$k$

Karolis Juodelė

Inilah mengapa saran Strilanc bekerja untuk $\min$ . Pertimbangkan susunan Anda $\mathrm{sum}$ , dan anggap minimum dicapai oleh $a_p,a_q$ dimana $p<q$ . Antara $a_p = a_q$ (dalam hal ini $a_p = a_{p+1}$ ), atau $a_p = x0y$ , $a_q = x1z$ untuk beberapa $x,y,z$ . Seharusnya $q > p+1$ , dan biarkan $a_{p+1} = xbw$ . Jika $b = 0$ kemudian $a_p \oplus a_{p+1} < a_p \oplus a_q$ , sedangkan jika $b = 1$ kemudian $a_{p+1} \oplus a_q < a_p \oplus a_q$ . Karena itu $q = p+1$ .

Yuval Filmus
sumber