Localizando valores XOR máximos e mínimos consecutivos

Dada uma matriz inteira (tamanho máximo 50000), tenho que encontrar o mínimo e o máximo $X$ de tal modo que $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ para alguns $p$ , $q$ com $p \leq q$ .

Eu tentei este processo: $\text{sum}_i = a_0 \oplus a_1 \oplus \dots \oplus a_i$ para todos $i$ . Eu pré-calculei em $O(n)$ e então o valor de $X$ para alguns $p$ , $q$ de tal modo que $(p\leq q)$ é: $X = \text{sum}_q \oplus \text{sum}_{p-1}$ . Portanto:

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

Mas esse processo é de . Como posso fazer isso de forma mais eficiente? $O(n^2)$

algorithms algorithm-analysis performance binary-arithmetic arithmetic palatok
fonte

Você já pensou em classificar sua lista de 'soma'? Parece que valores adjacentes seriam mais propensos a cancelar uma série de bits e acabam quase a 0.

Craig Gidney

Respostas:

Se é o tamanho de bits dos números inteiros, é possível calcular o tempo máximo em . $k$ $O(n k)$

Basicamente, o problema é que, dados , bits inteiros , localizem modo que seja máximo. $n$ $k$ $S_i$ $i,j$ $S_i \oplus S_j$

Você trata cada como uma sequência binária (observando a representação binária) e cria um teste com essas seqüências. Isso leva tempo . $S_i$ $O(nk)$

Agora, para cada , você está tentando percorrer o complemento de na você criou (tomando basicamente a melhor ramificação em cada etapa), encontrando um tal que seja o máximo. $S_j$ $S_j$ $j'$ $S_j \oplus S_{j'}$

Faça isso para cada , e você encontrará a resposta no tempo . $j$ $O(n k)$

Como seus números inteiros são limitados, esse algoritmo para max é basicamente linear, assim como o algoritmo para min obtido pela classificação (como a classificação pode ser feita em tempo linear).

Aliás, se não houvesse limites, você poderá reduzir a distinção do elemento para a versão mínima.

Aryabhata
fonte

"Basicamente, o problema é que, dados n, inteiros de k bits Si, encontre i, j de modo que Si⊕Sj seja o máximo." Eu não entendo essa linha. Eu quero que Si⊕Si + 1⊕ ... ⊕ Sj seja o máximo? me corrija se eu estou faltando alguma coisa

palatok

@Aryabhata, é injusto considerar linear. Afinal, (a menos que a lista possa ter duplicatas). Ainda é uma boa solução.

O (n k)

$O(nk)$

k \geq \log_{2} n

$k \geq \log_2 n$

Karolis Juodelė

@Aryabhata, por causa desse limite, você também pode dizer que o algoritmo é . Isso não é muito descritivo.

O (1)

$O(1)$

Karolis Juodelė

A questão não diz que os números inteiros são limitados; diz que a matriz tem tamanho no máximo 50000. Então, de fato, é constante, não !!

n

$n$

k

$k$

Jeffe

@ Jeff: Oh! E agora que você aponta (e eu concordo com essa interpretação), os comentários de Karolis fazem sentido para mim agora. Obrigado!

Aryabhata

A classificação também ajuda com . Um pouco, pelo menos. Claramente, o máximo seria alcançado por . Portanto, para cada faça uma pesquisa binária por . Esse é o tempo , o mesmo que a classificação, de modo que permanece a complexidade de todo o procedimento. $\max$ $x \oplus \neg x$ $x = \text{sum}_i$ $\neg x$ $O(n \log n)$

Karolis Juodelė
fonte

e o valor mínimo?

palatok

e se eu não encontrar ¬x?

Palatok 29/12/12

@palatok, o valor mínimo já foi explicado. Se você não encontrar , verifique as duas somas mais próximas de onde estaria.

\neg x

$\neg x$

Karolis Juodelė

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

$sum_i, sum_j$ deve ser 0 ou 1. A tabela de hash será suficiente.

Strin

@ Strin, não vejo o que você quer dizer. tem bits. Como uma tabela de hash seria útil - perto, não são necessários valores exatos.

{sum}_{i}

$\text{sum}_i$

k

$k$

Karolis Juodelė

Eis por que a sugestão da Strilanc funciona por . Considere sua matriz e suponha que o mínimo seja alcançado por , onde . De qualquer (caso em que ), ou , para alguns . Suponha e deixe . Se então , enquanto que se então . Portanto . $\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
fonte