Facebook Hacker Cup – Round 2 (Continuação…)

A final do facebook hackercup aconteceu dia 11 de Março em Palo Alto. O campeão foi o Petr Mitrichev.

Eu, como mero mortal (:P), ainda estou tentando entender as soluções dos problemas do round 2. Nesse post vou comentar a solução do problema Scott’s New Trick.

A descrição do problema é bem simples: dados dois vetores A e B de inteiros aleatórios, com tamanhos N e M, respectivamente, um primo P e um inteiro 1 ≤ L ≤ P contar quantos índices 1 ≤ i ≤ N e 1 ≤ j ≤ M satisfazem (A[i] * B[j]) mod P < L.

Solução:

Bom, é trivial resolver esse problema em O(NM), enumerando todos os índices. O problema é que 2 ≤ N, M ≤ 10.000.000, então temos que pensar em uma solução melhor.

Uma segunda ideia é criar vetores de frequências fA e fB, ambos de tamanho P. A entrada fA[i] guarda quantos elementos v de A existem tal que v % P = i. O vetor fB é definido analogamente para B. Em O(P^2) percorremos todos os i e j. Se i * j % P < L, somamos fA[i]*fB[j] na conta final. Temos que P < 250.000, mas ainda é inviável rodar 20 testes em menos 5 minutos (que era o tempo para submeter as respostas).

Minha ideia durante a competição foi tentar paralelizar esse programa usando OpenMP em uma máquina com 4 cores. Consegui reduzir o tempo de execução para 1 minuto no pior caso. Porém, eu ia precisar de umas 5 ou mais máquinas dessas para conseguir submeter a tempo :( Ouvi dizer que alguém passou esse problema com esse algoritmo paralelizando em um cluster!

Parece que a maior parte das pessoas que passaram o problema, implementou o algoritmo de Karatsuba (o autor do algoritmo é russo e não japonês como o nome sugere, hehe). Vou estudar essa solução posteriormente, mas agora quero apresentar a solução bastante inteligente do meret, que melhora o desempenho do código usando teoria dos números e programação dinâmica.

Vamos continuar com os vetores fA e fB. Notamos que a soma que estamos buscando é dada por

(1)

O primeiro somatório conta os elementos onde os elementos de A são 0 (% P). Logo a multiplicação deles por quaisquer elementos de B vai ser sempre 0, e menor do que L, já que L ≥ 1.

Para entender o segundo somatório, considere um dado j. O valor inv(j) é o inverso modular de j, ou seja, é um número x tal que j * x ≡ 1 (mod P). Ele conta os números com produto igual a j*(k*inv(j)) % P, como multiplicação modular é comutativa e associativa, esse produto é simplesmente k. Por isso k vai até L-1.

Note que a restrição de P a primo é importante para que haja exatamente um único inverso modular para todo j de 0 a P-1. Além disso, todas as contas de índice são módulo P.

Agora, considere inteiros ‘c’ e ‘i’ tais que c ≡ i*j (mod P), equivalentemente, c * inv(j) ≡ i (mod P). Dados dois inteiros x e y, podemos escrever x como

(2)

Pois é o quociente e x % y é o resto da divisão. Sendo o índice k (da equação (1)) e c ambos inteiros, podemos escrevê-los na forma da equação (2). Além disso, multiplicando ela por inv(j) ficamos com

Fazendo módulo P e substituindo c * inv(j), temos

(3)

Na equação (1) podemos colocar para fora do somatório de k o termo fA[j]. Fixando um dado j, temos

Agora vamos substituir cada fB[k * inv(j)] pelo equivalente em (3). Para k = 0 até c-1, , então os índices serão

.

Para k = c até 2c-1,

e assim por diante, até que , onde os índices serão


Vamos reorganizar esse somatório agrupando os índices de forma que (k % c) sejam iguais, ou seja, soma os termos da primeira coluna, depois os termos da segunda coluna e por aí vai. O primeiro grupo fica,

(4)

O segundo grupo fica (5)

O k-ésimo grupo fica (6)


Note que são c grupos dessa forma. Introduzimos diversas variáveis, rearranjamos os termos, mas o somatório continua o mesmo. O intuito dessas complicações é permitir o cálculo rápido dos grupos acima. Para isso, dado um i, considere o vetor V, onde V[k] = i*k % P para k = 0, …, P-1.

A sacada da solução é notar que todo grupo de índices definido acima, corresponde a um intervalo de V. É fácil ver que o primeiro grupo de índices (eq. (4)), corresponde ao intervalo 0 a de V.

O segundo grupo é mais difícil de enxergar. Será que existe um intervalo de V correspondente a (5)? O primeiro termo é inv(j). Queremos encontrar um k’ tal que k’i ≡ inv(j) (mod P). Para tal, multiplique essa igualdade por j, ficando com k’*i*j ≡ 1 (mod P). Substituindo i*j por c, temos que k’c ≡ 1 (mod P) ou seja, k’ é o inverso modular de c!

Agora os índices do segundo grupo aumentam de i em i, então é fácil ver que eles formam um intervalo em V (possivelmente dando a “volta” no vetor). Como são termos, dá pra descobrir o intervalo de V, que será de inv(c) a inv(c) + .

Para um k genérico, é possível mostrar que k’ = k * inv(c). O intervalo fica de k*inv(c) a k*inv(c) + .

Vamos pré-computar um vetor com a soma acumulada dos elementos de fB indexados por V, denotado S, ou seja

Para todo n de 0 a P-1. Esse vetor pode ser calculado em O(P). Para cada grupo de índices, correspondente ao intervalo (lb, ub) em V, calculamos a soma

Dado um j, a complexidade fica O(P) para construir S e O(c) para computar as somas dos grupos de índices.

A primeira abordagem é, para cada j, escolher um i que minimize c. Claramente o i que estamos procurando é inv(j), pois nesse caso c=1. Aí podemos calcular as somas dos grupos em O(1), mas a complexidade de calcular S é O(P). Isso torna o algoritmo O(P^2), o que é tão ruim quanto o algoritmo mais simples.

No outro extremo, como S só depende de i, podemos escolher um i fixo para todo j e calcular c em função de i e j. Aí calculamos S apenas uma vez em O(P) e aí para cada j calculamos a soma em O(c). A complexidade fica O(P + P*C), onde C é o maior valor de c considerando todos os j’s. O problema é que C pode ser da ordem de P.

A ideia é usar uma abordagem híbrida. Escolhemos um i que minimize c, mas limitamos o valor de i a √P. Calculamos então o vetor imin, onde para cada j, imin[j] contém i (1 a √P) que minimize c. Aí então calculamos S apenas √P vezes. A complexidade fica O(P√P + P*C). Porém C ainda pode ser da ordem de P. Podemos apertar a análise da complexidade como O(P√P + ∑(c)), onde ∑(c) é a soma dos c’s para cada j.

Aí entra uma conjectura/teorema de que ∑(c) é O(P√P). (No final das contas isso estraga a beleza da solução. Seria legal ver a prova disso…). Com tudo isso, temos a complexidade O(P√P), que é suficiente para passar no tempo.

Conclusão

Apesar da conjectura, a solução do meret tem várias ideias interessantes. Vale a pena ver a implementação dele (dá pra baixar no site do Facebook). Não fiquei muito empolgado para implementar essa solução, mas quero ainda estudar as soluções usando o algoritmo de Karatsuba. Fica para um próximo post.

Os comentários estão fechados.

%d bloggers like this: