Localizando valores XOR máximos e mínimos consecutivos

8

Dada uma matriz inteira (tamanho máximo 50000), tenho que encontrar o mínimo e o máximo X de tal modo que X=apap+1aq para alguns p, q com pq.

Eu tentei este processo: sumi=a0a1ai para todos i. Eu pré-calculei emO(n) e então o valor de X para alguns p, q de tal modo que (pq) é: X=sumqsump1. Portanto:

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

Mas esse processo é de . Como posso fazer isso de forma mais eficiente?O(n2)

palatok
fonte
1
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:

7

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

Basicamente, o problema é que, dados , bits inteiros , localizem modo que seja máximo.nkSii,jSiSj

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 .SiO(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.SjSjjSjSj

Faça isso para cada , e você encontrará a resposta no tempo .jO(nk)

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
1
@Aryabhata, é injusto considerar linear. Afinal, (a menos que a lista possa ter duplicatas). Ainda é uma boa solução. O(nk)klog2n
Karolis Juodelė
1
@Aryabhata, por causa desse limite, você também pode dizer que o algoritmo é . Isso não é muito descritivo. O(1)
Karolis Juodelė
1
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 !! nk
Jeffe
1
@ 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
5

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

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

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

Yuval Filmus
fonte