Topcoder: SRM 523

Novembro 27, 2011

No SRM 523 demorei bastante para fazer o problema fácil (50 min!) e por isso sobrou pouco tempo para fazer o médio. Cheguei a bolar uma solução, mas descobri no final que ela estava errada.

Depois de muito tempo voltei acertar um challenge! O erro em questão era um típico caso de Off-by-one error no problema fácil.

Depois de passada a competição, consegui encontrar o erro da minha ideia original e resolvi o problema médio. Neste post vou explicar minha solução.

BricksN

Considere que temos um número infinito de blocos de tamanho 1 a k. Queremos construir uma torre sobre uma base de largura w e altura máxima h usando esses blocos, com a seguinte restrição: só podemos posicionar um bloco em uma dada posição, se todas as posições logo abaixo desse bloco estiverem preenchidas (sem buraco). A pergunta é: quantas torres diferentes podemos formar seguindo essas restrições?

Exemplo de configuração proibida

(Observação: se duas torres têm mesma “forma”, mas existem blocos em posições diferentes, elas também são consideradas diferentes)

Soluções consideradas diferentes

Descrição do problema original.

Solução

Primeiramente, notei que este era um problema de contagem e portanto havia uma grande chance da solução ser por programação dinâmica.

Para encontrar a recorrência em programação dinâmica, é interessante pensar em casos particulares. Vamos por exemplo pensar em uma torre de altura 1 (uma linha) e largura w. Além disso, vamos supor que não há buracos. De quantas maneiras podemos formar tal torre usando blocos de tamanho até k?

Seja C_k(w), o número de maneiras de construir uma linha de comprimento w, permitindo blocos de tamanho até k. Considere todas as soluções com essas características. Podemos particionar essas soluções em grupos nos baseando no tamanho do último bloco utilizado.

Considere um grupo onde o tamanho do último bloco é i. Se removermos esse bloco, teremos linhas de comprimento (w-i). Todas as possíveis soluções diferentes com comprimento (w-i) continuarão diferentes ao adicionarmos o bloco de tamanho i de volta.

Fazendo isso para todos os blocos de tamanho 1 a k, obteremos todas as possíveis soluções contadas em C_k(w). Note que não estamos contando soluções repetidas pois duas soluções com o último bloco diferente, serão diferentes independentemente do que tem anteriormente. Note também que não estamos deixando de contar nenhuma solução, já que qualquer solução deverá conter como último bloco algum entre 1 e k.

Logo, temos a seguinte recorrência:

C_k(w) =  \sum_{i=1}^k C_k(w-i)

Para i \ge  w e com C_k(0) = 1.

Agora vamos generalizar um pouco mais e considerar linhas que podem ter buracos. A receita para encontrar uma recorrência é a mesma: precisamos particionar todas as possíveis soluções e para cada grupo, tentar reduzir para um subproblema.

Seja B_k(w) o número de maneiras de se formar uma linha de comprimento w, permitindo buracos.

Nesse caso, podemos particionar as soluções pela posição onde um buraco primeiro aparece, ou seja, temos um pedaço contíguo de blocos de tamanho i, seguido de pelo menos um buraco. Uma vez que estamos considerando um grupo de soluções para um dado i, qualquer solução diferente formada depois do buraco (posição i+2 em diante), continua sendo diferente ao adicionarmos o pedaço contínuo de comprimento i mais o buraco.

Também temos que contar os casos em que não há buracos. Dessa forma teremos a recorrência

B_k(w) = C_k(w) + \sum_{i=0}^{w-1} C_k(i) \cdot B_k(w-i-1)

Aqui também temos B_k(0) = 1 e podemos argumentar que soluções para i’s diferentes são diferentes (não estamos contando repetições) e também que todas as soluções estão sendo contempladas (inclusive a vazia).

Finalmente, vamos generalizar para torres de altura h. Seja A_k(w,h) o número de soluções respeitando as condições do problema original, sobre uma base w e altura h.

Observamos que devido às restrições do problema, não podemos fazer “pontes” com buracos em baixo. Assim, se tivermos um pedaço contínuo de comprimento w’ no primeiro nível de uma torre com altura máxima h, a construção que pode estar sobre ele são todas as torres sobre uma base w’, com altura máxima h-1.

Com essa observação, podemos continuar com nossa recorrência de B, mas agora temos que considerar todas as possíveis torres que vão sobre o primeiro bloco contínuo. Note que não precisamos nos preocupar com o restante dos blocos depois do buraco, pois qualquer diferente solução obtida continuará diferente após juntarmos com a nossa primeira torre.

Assim, ficamos com a recorrência:

A_k(w, h) = C_k(w) \cdot A_k(w, h-1) +
\; \sum_{i=0}^{w-1} C_k(i) \cdot A_k(i, h-1) \cdot A_k(w-i-1, h)

A implementação dessa ideia é direta. Coloquei no gitbhub essa solução.

Anúncios

Topcoder: SRM 517

Outubro 30, 2011

Já faz um tempo que ocorreu o SRM 517, mas só agora resolvi estudar a solução. No dia resolvi só problema mais fácil (250) e ainda errei um challenge :(

Neste post vou apresentar apenas a solução do problema médio, que estava mais difícil do que o normal, o que estava sugerido por sua pontuação (600 ao invés de 500).

Adjacent swaps

Descrição

Seja um vetor de N elementos v = {0, 1, 2, …, N-1} e uma permutação de p = {p[0], p[1], …, p[N-1]} de v. Definimos como troca-completa o conjunto das N-1 possíveis trocas entre elementos nas posições i e e i+1 (i variando de 0 a N-2) executadas exatamente uma vez, em uma ordem arbitrária.

O problema pede para encontrar quantas trocas-completas levam a v a p.

Solução

A primeira observação é que ao invés de considerar trocas-completas que levem v a p, consideramos aquelas que levam p a v. Existe uma bijeção entre uma troca-completa do problema original e do novo problema, que é simplesmente inverter a ordem das trocas e portanto a resposta é a mesma para os dois problemas.

A solução proposta no editorial é resolver esse problema através de programação dinâmica. Para tanto, definimos

u(i,j, k) — como o número de trocas-completas que ordenam o subvetor p[i…j] = {p[i], p[i+1] …, p[j]}, usando apenas as trocas entre elementos consecutivos entre i e j-1, com a restrição adicional de que a última troca efetuada seja entre k e k+1. (0 <= i <= k < j <= N-1).

Seja t(i,j) = \sum_{k = i}^{j-1} u(i,j,k). A solução que estamos procurando é então t(0, N-1). Além do mais, para o caso base i=j, temos um vetor de um único elemento ordenado e já não resta movimentos, portanto, t(i,i) = 1 para i=0, N-1.

Vamos ver como podemos calcular u(i,j,k).

Seja q[i…j] o subvetor p[i…j] ordenado e q'[i..j] o subvetor q[i..j] antes de fazer a troca entre k e k+1. Assim, q'[k] = q[k+1] e q'[k+1] = q[k], ou seja q'[i…j] = {q[i], q[i+1], …, q[k-1], q[k+1], q[k], q[k+2], …, q[j]}.

Observação 1: (q[i] < q[i+1] < … q[k-1] < q[k+1]) e (q[k] < q[k+2] < … < q[j]).

Por definição, q[i…j] e q'[i…j] são permutações de p[i..j]. Isso implica que todo elemento de q'[i…k] pertence a p[i…k] ou p[k+1…j]. Porém, como por hipótese a troca k,k+1 não foi feita ainda, um elemento de q'[i…k] não pode ter vindo de p[k+1…j]. Logo, concluímos que q'[i…k] deve ser uma permutação de p[i…k]. Temos assim duas condições a serem satisfeitas:

Condição 1: O subvetor p[i…k] deve ser uma permutação de q'[i…k].

Condição 2: O subvetor p[k+1…j] deve ser uma permutação de q'[k+1…j].

Na verdade podemos mostrar que as condições 1 e 2 são equivalentes. Supondo que as condições são satisfeitas, pela Observação 1, temos que q'[i…k] está ordenado, logo q'[i…k] = q[i…k], que é uma ordenação de p[i…k]. É possível argumentar o mesmo para q'[k+1…j] e p[k+1…j].

Por definição, t(i,k) conta o número de trocas-completas que leva p[i…k] em q[i…k] (o mesmo para t(k+1,j)). Assim, a princípio poderíamos combinar cada troca-completa em t(i,k) com cada troca-completa em t(k+1,j), levando à recorrência u(i, j, k) = t(i, k)*t(k+1, j).

Entretanto, há um número bem maior de combinações. Considere uma dada troca-completa A de t(i,k) e outra B de t(k+1, j). Embora a ordem das trocas em A e em B sejam fixas, não há restrição de ordem entre uma troca feita em A e outra feita em B. Por exemplo, poderíamos fazer todas as trocas de A primeiro e depois todas as de B ou qualquer combinação de intercalação entre os elementos de A e B.

Podemos mostrar que o número total de intercalações possíveis é dada por um coeficiente binomial C(n,r). No nosso caso em particular, n é o número total de trocas disponíveis, ou seja, j-i-1 (k-i de A e j-(k+1) de B) e r é o número de trocas em A (ou em B), ou seja, C(j-i-1, k-i). Para ver o porquê, considere que temos posições de 1 a j-i-1. Queremos escolher k-i dessas posições para atribuir a elementos de A e o restante das posições fica para B. Agora basta pensarmos nessas posições como a ordem em que as trocas são efetuadas.

Isso dá a recorrência

u(i, j, k) = t(i, k)*t(k+1, j)*C(j-i-1, k-i)

No caso de as condições 1 e 2 não serem satisfeitas, u(i, j, k) = 0.

Podemos usar a recorrência C(n,r) = C(n-1, r-1) + C(n-1, r) para pré-computar os valores dos coeficiente binomiais em O(N^2). Também podemos pré-computar se para uma dada tripla i, j, k, as condições 1 e 2 serão satisfeitas, em O(N^3) (usando ordenação linear para encontrar q).

Dado isso, podemos computar cada u(i, j, k) em O(1) e cada t(i, j) m O(N). A complexidade total das recorrências fica O(N^3), que também é a complexidade total do algoritmo.

Decidi colocar minhas implementações de SRM’s também no github.

Conclusão

Achei a solução desse problema bastante complicada e como de costume fiquei surpreso de tanta gente ter conseguido resolvê-lo durante os 75 minutos de competição.

Programação dinâmica é uma técnica que eu acho difícil aprender, porque em geral não consigo encontrar uma estrutura no problema que me indique a forma de atacá-lo. Minha esperança é continuar estudando suas aplicações e quem sabe aprender por “osmose” :P

O uso do coeficiente binomial para contar intercalações é bem engenhoso! Lembro que alguma outra vez estudei um problema em que a contagem por coeficiente binomial também não era trivial de ver.


Facebook Hacker Cup – Round 2

Março 11, 2011

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.