Facebook Hacker Cup – Round 2

Recentemente teve uma competição promovida pelo Facebook, chamada Facebook Hacker Cup. Por mais que o nome sugira outra coisa, essa competição é nos moldes da Maratona de Programação e muito similar ao Google Code Jam.

Teve uma fase de qualificação, onde bastava fazer pelo menos um problema. Depois teve o Round 1 que era dividido em três partes: A, B e C. Você podia tentar qualificar para o Round 2 em qualquer uma delas desde que não tivesse conseguido em uma anterior.

Essas duas primeiras fases foram relativamente tranquilas, mas o Round 2 foi muito difícil! Os 300 primeiros dos ~3000 classificados iriam ganhar uma camiseta, mas só 150 pessoas fizeram pelo menos um problema e eu não estava entre elas :/

Os 25 primeiros colocados vão competir na final onsite lá em Palo Alto. Até onde eu sei não há brasileiros.

Vou apresentar apenas o problema mais fácil dessa etapa. Os outros eu ainda não sei como fazer :P Se eu descobrir faço um novo post.

Bonus Assignments

O descrição do problema se encontra aqui. No problema você deve distribuir uma certa quantidade de dinheiro para N trabalhadores para eles comprarem refrigerante, com a restrição de que o trabalhador que ganhar menos não deve ganhar menos do que A ou mais do que B. O trabalhador que ganhar mais não deve ganhar menos do que C ou mais do que D. Uma restrição adicional é que pelo menos um trabalhador não vai conseguir torrar todo o seu dinheiro em refrigerante. Você não sabe o preço exato do refri, só que é mais do que $1. Queremos saber quantos jeitos temos de distribuir dinheiro, satisfazendo essas restrições. A resposta deve ser módulo 1,000,000,007.

A primeira observação é que, para que sempre sobre algum trabalhador que não consiga torrar todo o seu dinheiro com refri, independente do custo desse, deve existir pelo menos dois trabalhadores que recebam montantes x e y primos entre si. Caso contrário, se todo par tivesse montante com algum divisor comum mdc > 1, então para um refri com esse valor todos conseguiriam torrar seu dinheiro.

O problema se reduziu a contar quantas combinações existem para N elementos, de modo que o valor do menor elemento esteja entre [A, B] e do maior entre [C, D] e exista pelo menos um par de elementos com valores primos entre si.

Solução:

Vamos por partes. Primeiro, como contar quantas combinações existem de N elementos, sendo que o valor deles deve estar entre [A, D]? Por exemplo, N = 3, A = 1, D = 5. Cada elemento pode assumir o valor {1, 2, 3, 4, 5}. Como eles são independentes, há 5^3 combinações. De maneira mais geral, temos (D-A+1)^N.

Porém, queremos que o menor elemento tenha valor de no máximo B. Por exemplo se B = 2, na conta acima estamos contando o vetor [3, 3, 5], cujo menor elemento é 3. Então queremos jogar fora os vetores cujo menor elemento sejam maior do que B. Esse número é justamente quantas combinações de N elementos temos com valor entre [B+1, D]. Ou seja, devemos descontar (D – B)^N.

De igual maneira, ainda estamos contando vetores cujo maior elemento seja menor do que C. Por exemplo, se C=4, temos [1, 1, 1] na conta acima. Vamos jogar fora aqueles vetores cujo maior elemento seja menor do que C, ou seja, aqueles com N elementos de valores entre [A, C-1], dado por (C – A)^N.

Ficamos com um problema. Observe que o vetor [3, 3, 3] é um vetor com valores entre [A=1, C-1=3] e [B+1=3, D=5]. Ou seja, removemos ele duas vezes! De modo geral, removemos todos os vetores que têm valores entre [B+1, C-1] duas vezes. Devemos repô-lo com (C – B – 1)^N. Observe que essa interseção só ocorre se C > B+1.

Bom, sem a restrição de ter pelo menos dois valores primos relativos a conta é basicamente:

(D-A+1)^N – (D – B)^N – (C – A)^N + (C – B – 1)^N,

onde o último termo é zero se C <= B+1.

Nessa contagem estamos contando tanto os vetores com pelo menos dois primos relativos, quanto aqueles em que nenhum par é primo relativo, ou seja, os vetores para os quais todos os valores tem um divisor comum maior do que 1. Vamos tentar encontrar aqueles com mdc=2. Por exemplo, para N = 3, A = 3, B = 4, C = 4, D = 7. Um exemplo é [4, 6, 4]. Claramente podemos dividir esse vetor por 2, resultando em [2, 4, 2]. Fica claro que podemos dividir todos os limites por 2 e obter um subproblema que é justamente a quantidade de combinações onde todos os valores são pares.

Assim, dividimos A, B, C e D por 2 para obter A’=2, B’=2, C’=2, D’=3. Note que usamos teto para os limites inferiores A e C, mas chão para os superiores B e D, pois não queremos considerar um intervalo maior do que o original. Note também que ao dividir por 2 e contar, estamos considerando os casos com mdc=4, mdc=8, etc. Ou seja, só precisamos remover as divisões por primos!

Bom, basta então dividir por todos os primos para os quais os intervalos resultantes tenham algum vetor válido. Um limite suficiente é tentar dividir por todos os primos menores ou iguais que D. Porém, temos novamente um problema de remoção repetida. Ao contar os que têm 2 como mdc e os que têm 3 como mdc, estamos contando duas vezes aqueles que têm 6 como mdc! Por isso precisamos usar o princípio da inclusão-exclusão. Dá para fazer isso recursivamente.

Acho que essa teoria é suficiente para resolver o problema. Tem o detalhe de achar primos de forma eficiente, que pode ser feita com o crivo de Eratóstenes e fazer a exponenciação modular de forma rápida.

Tem uma pegadinha adicional, que eu só descobri depois que implementei: nada impede que B > D ou C < A. Algumas das contas podem dar errado por causa disso, mas note que o resultado não muda se fizermos B = min(B, D) e C = max(C, A) nesse caso.

Minha implementação em C++ está aqui. Baseei minha análise e código na solução do kalinov.

Os comentários estão fechados.

%d bloggers like this: