SRM 533, 535 e Codeforces #108

Junho 10, 2012

Desde o último post-mortem, participei de várias competições de programação. No SRM 533 falhei nos dois problemas que submeti (Casket of Star e Magic Board) e por causa disso voltei a virar azul :(

No Codeforces #108, passei um bom tempo pensando no problema Garden, mas não consegui resolver.

No SRM 535 achei um bug na minha solução e tive que re-submeter o problema fácil por 75 pontos. Além disso errei um challenge (-25 pontos). Finalmente, pensei bastante no problema Fox and Business, mas a complexidade da minha solução estava muito alta dado os limites do problema.

Neste post vou apresentar um resumo das soluções para os quatro problemas mencionados.


Casket of Star

A descrição do problema se encontra aqui. Estou supondo que o vetor de entrada é chamado w e possui tamanho n.

Minha abordagem durante a prova foi gulosa: remover sempre o elemento i tal que w[i-1]*w[i+1] seja máximo. Na hora me pareceu correto e todos os casos de teste passaram, mas eis um contra-exemplo: (2, 5, 10, 5, 2). O algoritmo irá remover o 10, gerando um produto de 5*5=25, deixando (2, 5, 5, 2). Aí não tem muito o que fazer: vamos tirar os dois 5, gerando os produtos 10 e depois 4, para um total de 39. Entretanto, se retirarmos os 5’s antes do 10, teremos 20 + 20 + 4, para um total de 44.

Programação dinâmica

Durante a prova cheguei a pensar em uma abordagem por programação dinâmica, mas encontrei dificuldades em definir os subproblemas independentes. Minha única ideia foi a de remover um dado elemento i (adicionando um valor w[i-1]*w[i+1]) e então pensar em alguma coisa com os subproblemas [0,i-1] e [i+1, n-1], mas eles não são independentes, pois poderíamos remover o elemento i+1 e o valor obtido dependeria do valor no outro subvetor.

Depois da prova pensei em outras alternativas. Uma delas foi: e se ao invés de tentar separar em subproblemas a partir do primeiro elemento removido, tentar separar a partir do último? Essa ideia aleatória matou o problema porque se eu sei que o elemento i será o último a ser removido, então os intervalos [0,i] e [i, n-1] são independentes! Isso porque o valor obtido da remoção de um elemento de 0 a i-1 não dependerá do valor de i+1 a n-1 e vice-versa.

Se chamarmos de f(i, j) o melhor valor obtido para a subsequência [i, j], podemos derivar a seguinte recorrência:

f(i, j) = \max_{i +1 \le k \le j-1} \left\{ f(i, k) + f(k, j) + w(i)w(j) \right\}

No caso estamos tentando com todos os possíveis valores de k entre i+1 e j-1 e supondo que k será o último elemento a ser removido. O resultado das remoções feitas em f(i, k) será o vetor {i,k} e o de f(k, j) será o vetor {k, j}, ou seja, {i, k, j}. Agora a única possibilidade é remover k e somamos w(i)w(j) no valor. O caso base é quando temos menos de 2 elementos, o qual devemos retornar 0.

Resumo

Achei a dificuldade do problema elevada, além do fato de ele ser bem tricky. A taxa de acerto foi de 31%.

A técnica de “pensar ao contrário” (nesse caso, olha para o último elemento a ser removido ao invés do primeiro), que eu já havia usado em problemas passados, foi essencial.


Magic Board

Neste problema, devemos encontrar um caminho que passe exatamente por todas as células marcadas de um grid, com a seguinte restrição: só podemos ir de uma célula para outra usando linhas verticais ou horizontais, sendo que no caminho devemos alternar entre linhas verticais e horizontais, começando por uma linha horizontal.

Minha abordagem foi a seguinte. Seja s o vértice inicial e t o vértice final do caminho. Nesse caso, somamos 1 na contagem da coluna de s. Se o número de vértices for par, então a última aresta é horizontal e nesse caso também somamos 1 na contagem da coluna de t. Por outro lado, se o número de vértices for ímpar, a última aresta é vertical e então somamos 1 na linha de t. Agora, verificamos se todas as colunas e linhas possuem uma contagem par.

Temos que chutar todos os possíveis pares s e t para ver se algum satisfaz a condição acima, ou seja, o algoritmo é O(N^4), para N = 50.

Essa abordagem parecia correta, mas eu tomei um challenge. O motivo: essa contagem não faz a verificação da conexidade. Pode existir um caminho válido mas com “ciclos” disjuntos, como no seguinte exemplo:


##...
.#...
...##
...##

Figura 1: Ciclo disjunto

A componente no alto à esquerda é válida, assim como o ciclo abaixo à direita, mas eles são disjuntos. É possível eliminar esse caso fazendo uma simples busca em profundidade e verificar se todo vértice é alcançável a partir do outro usando apenas arestas ortogonais.

No editorial, a solução é modelar o tabuleiro como grafo bipartido. Cada coluna representa um vértice da primeira partição, enquanto cada linha representa um vértice da segunda partição. O problema consiste em decidir se existe um caminho euleriano, com a restrição de que a primeira aresta usada no tabuleiro seja horizontal.

Resumo

Esse foi outro problema tricky, pelo fato de não haver casos de testes com o problema da conexidade.

A modelagem de um tabuleiro usando um grafo bipartido é uma técnica que eu já havia utilizado anteriormente. Tentar trocar arestas com vértices (dualidade) no grafo pode ser útil para conseguir resolver o problema. Nesse caso, um problema que parecia um caminho hamiltoniano (NP-difícil) acabou ficando parecido com um caminho euleriano (para o qual existe um algoritmo polinomial)

Dois problemas relacionados que me veem à mente são o Rectilinear Polygon [4] e o The Necklace [5].


Fox and Business

Podemos modelar este problema matematicamente da seguinte maneira:

\min (\sum_{i \in S} p_i a_i t) + tK

Onde, S é representa os empregados que serão escolhidos na solução, p_i é o custo por unidade de trabalho do empregado i e a_i é a quantidade de unidades de trabalho dele em uma hora. A variável t é o tempo de cada trabalhador e K é o número de trabalhador que deverá ser usado.

Essa função objetivo está sujeita a

\sum_{i \in S} a_i t = T

onde T é o total de trabalho que deve ser feito. Durante a prova só consegui pensar em uma abordagem de programação dinâmica, mas minha ideia tinha uma complexidade que não passaria no tempo.

A abordagem usada no editorial é muito engenhosa e não utiliza PD. A ideia se você dividir a função objetivo por uma constante positiva, a solução ótima não muda. Como T é uma constante, podemos dividir a função objetivo por ela, obtendo

(\sum_{i \in S} p_i a_i t) + tK = \dfrac{(\sum_{i \in S} p_i a_i t) + tK}{T}

Substituindo o valor de T, podemos nos livrar da variável t,

= \dfrac{(\sum_{i \in S} p_i a_i) + K}{\sum_{i \in S} a_i}

Bom, isso não pareceu ajudar muito, mas a segunda sacada é transformar esse problema de otimização em um problema de decisão, ou seja, dado um valor C, existe uma solução S tal que

C \ge \dfrac{(\sum_{i \in S} p_i a_i) + K}{\sum_{i \in S} a_i}?

Com um pouco de álgebra podemos reescrever essa desigualdade como

C \sum_{i \in S} a_i \ge (\sum_{i \in S} p_i a_i) + K \rightarrow

\sum_{i \in S} a_i(C - p_i) \ge K

O valor máximo do lado esquerdo da desigualdade pode ser calculado de maneira gulosa, escolhendo os K maiores de a_i(C - p_i)! Se esse valor máximo for menor do que K, então não existe uma solução. Assim, temos um algoritmo para resolver o problema de decisão.

Para obter o valor ótimo de C, podemos usar a técnica da busca binária. O valor esperado pelo problema será C T

Resumo

Ideias utilizadas: Manipulação algébrica e busca binária para transformar um problema de otimização em um de decisão.


Garden

Neste problema temos um tabuleiro n x m onde cada célula tem um inteiro positivo que representa um custo. Duas células são ditas adjacentes se tocam em um dos lados (não consideramos diagonal). Duas células podem ser conectadas através de um caminho de células adjacentes. O custo desse caminho é a soma dos custos das células nesse caminho. São dados então k pontos desse tabuleiro que devem ser conectados com o menor custo. Mais detalhes no enunciado do problema.

Esse problema lembra um caso particular do problema da árvore de Steiner, onde é permitido adicionar novos vértices para tentar obter uma árvore de custo menor do que a árvore geradora mínima.

Achei a solução do editorial bastante resumida e com um inglês meio difícil de compreender. De qualquer maneira, deu pra entender que se trata de programação dinâmica. No editorial é dada a recorrência, mas tive que quebrar a cabeça para entender de onde ela veio.

Programação dinâmica

A ideia básica da recorrência é: dada uma cobertura de um conjunto de pontos, quebramo-na em cobertura menores, cobrindo subconjuntos do conjunto inicial de pontos. Faremos a quebra em pontos compartilhados pelas coberturas menores o qual chamaremos de pivots.

Seja C(P, p) a cobertura de menor custo cobrindo o conjunto de pontos P e que possua o ponto p. No nosso caso, P é um subconjunto dos pontos a serem cobertos e pode ser representado com uma máscara de bits. Já o ponto p é uma célula qualquer do tabuleiro. A solução que queremos é \max_p \{C(P, p)\} com P igual ao conjunto dos pontos a serem cobertos.

Há dois tipos de recorrência que vamos considerar. Primeiro, considere um grafo que conecta os pontos desejados como o exemplo da Figura 2(a). Queremos particioná-lo em 2 subgrafos que cobrem subconjuntos desses pontos e que compartilham apenas o ponto verde (pivot). Uma possibilidade de quebra é a da Figura 2(b).

Figura 2

Agora podemos resolver recursivamente cada componente e calcular o custo da componente completa somando os custos. Porém, veja que o pivot está sendo contado duas vezes e portanto devemos subtrai-lo. Definimos C_1(P, q) como:

C_1(P, p) = \max_{P'}\{C(P',p) + C(P \setminus P', p) - custo(p)\}

Onde P' representa todos os subconjuntos próprios não vazios de P.

Porém, pode ser o caso de não conseguirmos particionar o grafo de forma que o pivot seja o único ponto compartilhado, como é o caso da segunda componente de Figura 2(b). Neste caso queremos modificar o nosso pivot, mas para isso devemos considerar a distância entre o pivot antigo e o novo, representados por p e q em nosso exemplo:

Figura 3

Nesse caso definimos C_2(P, p) como:

C_2(P, p) = \max_{q}\{C(P \setminus \{p\}, q) + dist(p, q) - custo(q)\}

Onde q é um ponto qualquer do tabuleiro. Um cuidado que devemos ter aqui é que se p pertence a P, devemos removê-lo antes de chamar a recursão. Novamente, veja que o custo da célula q está sendo considerado duas vezes e portanto precisamos descontar um delas.

Finalmente, temos que C(P, p) = \max\{C_1(P, p), C_2(P, p)\}

Não bastasse isso, o problema ainda pede para mostrar o grafo que conecta os pontos (se houver mais de um com custo ótimo, pode ser qualquer um). Para isso devemos guardar as decisões tomadas durante as recorrências para recuperar a solução.

Complexidade

A distância entre pares de pontos pode ser pré-computada usando o algoritmo de Floyd-Warshall. Denotando nm por N, temos O(N^3).

Para calcular a complexidade da recursão vemos que são O(2^k N) estados. Na primeira recorrência devemos analisar outros O(2^k) estados, enquanto na segunda são O(N), levando a uma complexidade total O(2^kN(2^k + N)). Os limites do problema são k \le 7 e N \le 200, o que dá na ordem de O(8\cdot10^6) operações.

Resumo

Ideias utilizadas: Observar os limites dos problemas, particularmente o valor de k, que sugerem que no estado da programação dinâmica podem ser usadas máscara de bits.

Além disso, notar que se quebrarmos em subproblemas particionando o conjunto inicial de pontos, as soluções parciais não podem ser utilizadas imediatamente para compor a solução do problema original por que há células que seriam compartilhadas entre ambas as soluções e portanto devemos remover a contagem repetida.

A grande sacada é ver que podemos supor que as sub-soluções compartilham exatamente uma célula se permitirmos a troca de pivot.

Códigos-fontes

Disponibilizei os códigos-fontes de todos os problemas discutidos no post, no github (SRM 533, SRM 535 e Codeforces #108).

Referências

[1] Editorial SRM 533
[2] Editorial Codeforces #108
[3] Editorial SRM 535
[4] UVa 11106 – Rectilinear Polygon
[5] UVa 10054 – The Necklace

Anúncios

SRM 527

Dezembro 25, 2011

Depois de quase 5 anos competindo no Topcoder, finalmente meu rating ficou amarelo (+1500) \o/. Entretanto, não acredito que eu vá sustentar essa cor por muito tempo.

Como de costume comecei pelo problema fácil (275). Como não consegui pensar em nenhuma solução além de uma força-bruta complicada e como a pontuação do problema médio estava menor do que o de costume (450 contra 500), resolvi lê-lo. Então vamos começar por ele.

P8XMatrixRecovery

(Enunciado do problema)

Minha primeira ideia foi modelar como emparelhamento bipartido máximo de custo mínimo, mas não estava conseguindo modelar a função objetivo.

Depois de pensar mais, acabei lembrando de uma técnica que consiste em fixar um parâmetro do problema visando simplificá-lo. Um caso especial dessa técnica é o uso de busca binária num problema de otimização para transformá-lo em um problema de decisão.

Um problema que me lembro que pode ser resolvido com a técnica mais geral é o seguinte: encontrar o emparelhamento máximo de um grafo bipartido de forma que se minimize o custo da aresta de maior custo (a versão clássica do emparelhamento máximo de custo mínimo seria minimizar a soma dos custos das arestas).

A solução é, para cada possível custo de aresta C, criar um subgrafo G' contendo apenas as arestas de custo menores ou iguais a C. A resposta será o menor C para o qual existe um emparelhamento máximo em G'.

No problema em questão, podemos ter várias permutações de colunas que mapeiam uma matriz na outra, por causa dos caracteres coringas (‘?’). Entretanto, o problema pede a lexicograficamente menor. A ideia é fixar o primeiro caractere ‘?’ em ‘0’ e verificar se ainda existe um mapeamento.

Se sim, então podemos manter o caractere em ‘0’ e proceder para o próximo caractere ‘?’. Caso contrário, não existe nenhum mapeamento com ‘0’ e como o enunciado diz que sempre existe uma solução, então tem que existir alguma com ‘1’ e portanto podemos trocar para esse valor. Fazendo isso para todo caractere ‘?’ encontraremos a matriz lexicograficamente menor.

Para decidir se existe um mapeamento podemos resolver o problema do emparelhamento máximo bipartido. Criamos duas partições com vértices correspondendo a cada coluna de cada matriz. Adicionamos uma aresta entre dois vértices se as colunas correspondentes são iguais. Note que o “igual” nesse caso deve levar em conta que ‘?’ é igual a ‘?’, ‘0’ ou ‘1’. Se houver um emparelhamento perfeito, significa que existe uma bijeção entre as colunas das duas matrizes.

O emparelhamento máximo bipartido pode ser resolvido através do algoritmo de caminhos de aumento (augmenting paths) com complexidade O(NM) onde N é o número de vértices e M é o número de arestas.

Note que devemos resolver o problema do emparelhamento para cada ‘?’. No pior caso podemos ter matrizes só com ‘?’ (N^2) e nesse caso o grafo bipartido teria O(N^2) arestas, levando a uma complexidade total O(N^5). No problema o valor de N era igual a 30. Eu achei que ia estourar, mas minha solução acabou passando (código no github).

P8XGraphBuilder

(Enunciado do problema)

Depois que resolvi o problema médio, voltei a pensar na solução para esse problema. Cheguei a pensar na seguinte proposição:

Proposição: Dado um vetor de N elementos com valores maiores ou iguais a 1 e de tal forma que a soma desses elementos seja 2(N-1), é possível construir uma árvore de N vértices, de forma que exista uma correspondência entre os graus dos vértices e os elementos desse vetor.

Por exemplo, se N = 4, temos os vetores [3, 1, 1, 1] e [2, 2, 1, 1] e suas permutações. Dado um vetor, seu custo é dado pela soma dos pesos de seus elementos. O problema original então se reduz a encontrar o maior custo de um vetor satisfazendo as restrições da proposição.

É possível resolver esse novo problema através de programação dinâmica. Podemos definir C(n, s) como a melhor solução de um vetor de n elementos e somando exatamente s. A recorrência fica:

C(n, s) = \max_{d=1}^{N-1} C(n - 1, s - d) + b(d)

Onde b(d) é o valor do elemento d (dado pelo vetor scores). A base é quando n = 0. Nesse caso, se s = 0, temos 0, caso contrário não existe solução e retornamos -\infty.

Durante a prova, não tinha cheguei a provar a proposição, mas ela me pareceu correta. Mas infelizmente não tive tempo de implementar essa solução, que agora adicionei ao github.

Pra fins de completude, vou apresentar agora a prova da proposição.

Prova: Primeiro, sem perda de generalidade, vamos supor que os elementos do vetor estão ordenados em ordem não-crescente. Vamos usar um argumento construtivo. Dado um vetor v = \{d_1, d_2, \cdots, d_N\}, seja k o número de elementos com valor maior ou igual a 2. Crie um nó raíz com d_1 filhos. Faça um desses filhos ter d_2 - 1 filhos, um dos “netos” ter d_3 - 1 filhos e assim sucessivamente, até um nó ter d_k - 1 filhos.

Por exemplo, dado o vetor v = {4,4,3,1,1,1,1,1,1,1} construímos a árvore da figura abaixo.

Árvore com graus {4,4,3,1,1,1,1,1,1,1}

Temos uma árvore onde k nós têm grau igual aos primeiros k elementos de v e o resto dos nós têm grau 1. Resta provar que o número desses nós de grau 1 é exatamente N - k, ou equivalentemente, que essa árvore tem N nós. É fácil ver que o número de filhos “gerados” é a soma d_1 + (d_2 - 1) + (d_3 - 1) + \cdots + (d_k - 1) = (\sum_{i = 1}^k d_i) - k + 1.

O único vértice que não foi contado acima foi a raíz, então se N' é o número de nós da árvore gerada, temos N' = (\sum_{i = 1}^k d_i) - k + 2.

Usando a restrição de que o vetor deve somar 2(N-1), com um pouco de álgebra:

\sum_{i = 1}^k d_i + \sum_{i = k+1}^N d_i = 2N - 2

\sum_{i = 1}^k d_i + (N-k) = 2N - 2

Concluímos que N = (\sum_{i = 1}^k d_i) - k + 2 e que N' = N


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.


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.


Google Code Jam 2011

Setembro 18, 2011

O Google Code Jam é uma competição de algoritmos anual promovida pelo Google, que acontece desde 2007 se não me engano. Esse ano eu fui até o round 2, mas acabei não me classificando entre os 500 primeiros para avançar ao round 3:( Entretanto, acabei ganhando um prêmio de consolação por ter ficado entre os 1000 primeiros, que é a camiseta do evento.

Camiseta (frente)

Embora a competição tenha acabado em Julho, a camiseta só chegou a algumas semanas. O desenho na parte de trás são linhas de código em diversas linguagens de programação e tem o formato do Japão que é onde foi a final mundial, na qual o japonês Makoto Soejima (rng_58 no topcoder) sagrou-se vencedor.

Detalhe da parte de trás

Com a chegada da camiseta, lembrei que eu tinha ficado de estudar a solução dos problemas do round 2 que eu não havia conseguido resolver. Felizmente os problem setters apresentam a solução, mas também vou descrevê-las aqui do meu jeito.

C. Expensive Dinner

O enunciado desse problema está aqui. A solução está baseada em três proposições principais.

Proposição 1: Dado um grupo de amigos x_1, x_2, \dots, x_i, o valor da conta é sempre LCM(x_1, x_2, \dots, x_i) não importa a ordem em que eles cheguem. LCM representa o mínimo múltiplo comum.

Prova: Seja y o valor da conta.

Parte 1 – mostrar que y \ge LCM(x_1, x_2, \dots, x_i)
Essa parte é direta, dada a definição de mínimo múltiplo comum e que a conta tem que ser divisível por todo x_i.

Parte 2 – mostrar que y \le LCM(x_1, x_2, \dots, x_i)
Quando um amigo x_i pede alguma coisa, o valor da conta vai para o próximo múltiplo de x_i. Como LCM(x_1, x_2, \dots, x_i) é múltiplo de todos, o valor da conta não poderá “pular” esse valor e uma vez que esteja nesse valor, todos estarão satisfeitos e a conta não irá mais aumentar.

Juntando as partes 1 e 2, provamos a proposição.

Seja M o número de vezes que o garçon é chamado e M_{\max} e M_{\min} o maior e o menor valor possível de M, respectivamente. O problema pede M_{\max} - M_{\min}. Sejam p_1, p_2, \dots, p_P os P primos menores ou iguais a n (o número de amigos). Além do mais, seja e_i o maior inteiro tal que p_i^{e_i} \le n.

Proposição 2: M_{\max} = 1 + \sum_{i=1}^P{e_i}

Prova: vamos quebrar em duas partes novamente.

Parte 1 – mostrar que M_{\max} \ge 1 + \sum_{i=1}^P{e_i}
Para isso basta exibir um caso onde M = 1 + \sum_{i=1}^P{e_i}. Esse é o caso em que os amigos chegam na ordem 1, 2, \dots, n. Considere a chegada de x_i tal que x_i = p_i^k. É fácil ver que LCM(x_1, x_2, \dots, x_{i-1}) não é divisível por p_i^k e portanto o garçon terá de ser chamado. Quantos x_i existem satisfazendo x_i = p_i^k? Justamente \sum_{i=1}^P{e_i}. Além disso, quando x_1 = 1 chegar a primeira vez, o garçon também deverá ser chamado. Portanto, o número de vezes que o garçon foi chamado é pelo menos 1 + \sum_{i=1}^P{e_i}

Parte 2 – mostrar que M_{\max} \le 1 + \sum_{i=1}^{e_i}
Pela Proposição 1, o valor final da conta deverá ser LCM(x_1, x_2, \dots, x_n), que é igual a \prod_{i=1}^P p^{e_i}. Para qualquer ordem de amigos, temos LCM(x_1, x_2, \dots, x_i) = k \cdot LCM(x_1, x_2, \dots, x_{i-1}) para um inteiro k. É fácil ver que se um garçon for chamado, então k > 1, ou seja, estamos aumentando a potência que algum fator primo até chegarmos em \prod_{i=1}^P p^{e_i}, logo o garçon não pode ser chamado mais do que o número total de fatores na conta final, ou seja, \sum_{i=1}^{e_i} (+1 por causa da primeira chamada).

Juntando as partes 1 e 2, provamos a proposição.

Proposição 3: M_{\min} = P

Prova: vamos quebrar em duas partes novamente.

Parte 1 – M_{\min} \le P
Para isso basta exibir um caso onde M = P. Considere uma ordem onde os P primeiros amigos a entrarem são exatamente aqueles iguais a p_i^{e_i} para todo i = 1, \dots, P. É fácil ver que depois que eles entratem, o valor da conta será já LCM(x_1, x_2, \dots, x_n) e todo mundo que entrar depois já estará satisfeito, tendo o garçon sido chamado apenas P vezes.

Parte 2 – M_{\min} \ge P
Vamos por contradição: suponha que existe uma ordem de P-1 ou menos amigos tal que LCM(x_1, x_2, \dots, x_{P-1}) = LCM(x_1, x_2, \dots, x_n) = \prod_{i=1}^P p^{e_i}. Note que, para cada p_i, deve existir um amigo com fator p_i^{e_i} (caso contrário o LCM seria menor). Pelo princípio das casas dos pombos, como existem apenas P-1 amigos e P primos, há de haver algum amigo múltiplo de p_i^{e_i} e p_j^{e_j}. Entretanto, ambos p_i^{e_i} e p_j^{e_j} são maiores que \sqrt{n}. Isso implica que esse amigo tem valor maior que n, uma contradição.

Juntando as partes 1 e 2, provamos a proposição.

Dadas essas proposições, o problema se reduz a calcular (1 + \sum_{i=1}^P {e_i}) - P para todo primo P \le n. Considerando que podemos calcular e_i em O(\log(n)), levando a um algoritmo O(n \log(n)). Porém, como n pode ser até 10^{12}, temos que fazer melhor.

A sacada é reescrever a equação como 1 + \sum_{i=1}^P ({e_i} - 1). Isso quer dizer que só estamos interessados em fatores primos com potências maiores que 1. Logo, podemos nos restringir a primos menores ou iguais a \sqrt{n}, levando a um algoritmo O(\sqrt{n} \log(n)).

Depois dessa teoria toda, o algoritmo fica bem simples. Aqui está minha versão em C++, usando o crivo de eratóstenes para encontrar os primos.

D. A.I. War

Este problema se reduz para o seguinte problema: Dado um grafo G(V, E), encontrar o menor caminho entre s e t em um grafo não-direcionado e não-ponderado. Se houver várias soluções, escolha o caminho com maior vizinhança. Consideramos a vizinhança de um caminho como a união das vizinhanças dos vértices desse caminho, excluindo os vértices do próprio caminho. O problema pede para imprimir o comprimento desse caminho e o tamanho de sua vizinhança.

Vamos denotar por N o número de vértices nesse grafo e M o número de arestas.

Primeiramente encontramos as menores distâncias a partir de s, para todos os vértices, através de uma busca em largura. Denotamos por dist(v) a menor distância de s a v. O tamanho do menor caminho é dist(t).

Construímos então um grafo direcionado G' = (V, A), com mesmo conjunto de vértices do grafo de entrada e um arco (u, v) \in A se a dist(u) + 1 = dist(v). Podemos argumentar que todo caminho mínimo s-t no grafo original corresponde a um caminho direcionado de s a t nesse novo grafo.

Solução para o caso pequeno: podemos fazer uma força bruta a partir de s e, sempre que chegarmos em t, calculamos o tamanho da vizinhança desse caminho. Dessa forma estamos enumerando explicitamente todos os possíveis menores caminhos. Fiz uma estimativa e me pareceu que no pior caso, haverá cerca de O(\sqrt{N}^{\sqrt{N}}) caminhos. No caso fácil, P=36, o que dá uma ordem de 50k operações. No caso difícil, P=400, o que torna a abordagem inviável. De qualquer maneira, eis aqui minha solução para o caso fácil.

Solução para o caso geral: uma ideia é usar programação dinâmica para guardar o tamanho da vizinhança para um dado caminho, mas note que não basta representar um caminho por seu último vértice, pois ao adicionar um vértice a este caminho, sua contribuição para o tamanho da vizinhança pode depender de mais vértices nesse caminho.

A observação chave é que na verdade, a contribuição de um novo vértice c só depende do último e penúltimo vértice desse caminho. Para entender porque, suponha que dist(c) = D + 1 e sejam b e a o último e penúltimo vértices de um caminho, respectivamente. Então dist(b) = D e dist(a) = D-1. Se c possuísse vizinhança comum com algum vértice x tal que dist(x) \le D-2, então o menor caminho até c seria menor ou igual a D, uma contradição.

Logo, é suficiente representar um caminho por seus dois últimos vértices. Seja f(b, c) o tamanho da maior vizinhança de um caminho terminado em b \rightarrow c. Podemos definir a seguinte recorrência:

f(b, c) = \max \{ (a, b) \in A(G') | f(a, b) + g(c, a, b) \}

Aqui, g(c, a, b) é o número de vértices na vizinhança de c que não está contido nem na vizinhança de a nem na de b. O caso base é f(s, c), onde o valor é simplesmente o tamanho da união da vizinhança de s e c.

Se pré-computarmos g(c, a, b), podemos resolver a recorrência acima em O(N) e como cada par (b, c) deve pertencer a A(G'), o algoritmo tem complexidade O(NM).

Porém, calcular g(c, a, b) é a parte mais demorada. A solução mais simples seria enumerar todas as triplas de vértices e processar cada vértice v vizinhança de c, levando a um algoritmo O(N^4), o que dá na ordem de 25 \times 10^9, que é muito lento.

A sacada é usar o fato que c e v devem ser adjacentes, assim como os vértices a e b. Assim, para cada par de arestas e_1 e e_2, supomos e_1 = (c, v) e e_2 = (a, b). Usando uma matriz de adjacência, podemos verificar se v pertence à vizinhança de a e b em O(1), levando a uma complexidade total de O(M^2) ~4M operações. O editorial do Google Code Jam apresenta essa e outras 3 alternativas para pré-computar g(c, a, b). Minha implementação da solução apresentada se encontra aqui.


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

Março 27, 2011

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.


Topcoder: SRM 495

Fevereiro 13, 2011

O post era pra ter saído na Sexta, mas acabou atrasando :/ Bom, hoje vou comentar sobre os problemas não resolvidos durante o SRM 495. Consegui fazer o fácil de 300 pontos, mas demorei bastante tempo e tive que ressubmeter. Aí meu rating acabou caindo.

Carrot Boxes

Descrição. Há N caixas numeradas de 0 a N-1. Todas as caixas, exceto uma, possuem uma cenoura. Deseja-se descobrir a caixa vazia sem abri-la.

Algumas caixas possuem informações sobre o conteúdo de outras caixas e essa informações são conhecidas a priori. É dado um vetor<string> information, onde o j-ésimo caractere da i-ésima string é ‘Y’ se abrir a i-ésima vai revelar se a j-ésima caixa contém ou não uma cenoura, ou ‘N’ caso contrário.

Retornar a maior probabilidade para descobrir a caixa vazia sem ter que abri-la. (Texto original)

O autor do editorial descreveu a solução desse problema de forma tão bem detalhada e exemplificada que nem vale a pena explicar do meu jeito. Implementei a solução descrita em C++. Uma coisa que achei legal da solução é que se você pode se dar ao luxo de rodar um Floyd-Warshall O(n^3), depois fica bem simples determinar componentes fortemente conexas.

Strange Elevator

Descrição resumida. Considere um prédio de H andares e um elevador formado por N compartimentos (não necessariamente consecutivos). Quando parado, cada parte fica em um andar distinto e quando o elevador se move, todas as partes movem junto. Cada andar deve ser coberto por exatamente um compartimento do elevador. (Texto original)

Podemos representar um elevador pelos andares em que cada compartimento está, quando o compartimento mais baixo está no primeiro andar (denotado aqui por nível 0). Por exemplo, se H = 6 e N = 3, os elevadores (0, 2, 4) e (1, 3, 5) são respectivamente:

O problema pede para, dados N e H, encontrar quantos elevadores válidos podem ser formados. Para H = 6 e N = 3, há duas possibilidades, (0, 2, 4) e (0, 1, 2). Observe que (0, 2, 3) não é válido, pois o elevador, ao subir um andar, irá para os andares (1, 3, 4) e o andar 3 terá sido coberto por dois compartimentos diferentes.

Solução. Está bem detalhada no editorial, então vou tentar resumir aqui.

Proposição 1: Definimos como bloco um conjunto contínuo de compartimentos. Em um dado elevador, todos os blocos têm mesmo tamanho L.

Proposição 2: O espaço de separação entre dois blocos consecutivos é múltiplo de L.

A ideia básica das provas das duas proposições acima é que se elas não forem verdade, então necessariamente algum andar será coberto por mais de um compartimento ou algum andar não será coberto.

Problemas de contagem geralmente envolvem algum tipo de programação dinâmica (exceto quando existe uma fórmula fechada). De fato, a solução apresentada divide a matriz de PD em duas partes: C1(H, N) e Cn(H, N) a primeira corresponde ao número de elevadores válidos para um prédio de H andares e N caixas quando os blocos têm tamanho L = 1, enquanto a segunda quando os blocos têm tamanho L > 1.

A sacada do problema consiste em definir a relação de recorrência. A primeira observação é um corolário das Proposições 1 e 2: Como os blocos têm tamanho L e os espaços têm tamanho múltiplos de L, então H deve ser múltiplo de L. Dado isso, podemos “escalar” o problema dividindo todas as dimensões por L. Ou seja, o número de elevadores válidos para H andares, N caixas e blocos de tamanho L, é o mesmo para H/L andares, N/L caixas e blocos unitários. Logo, podemos definir a recorrência de Cn(H, N) da seguinte forma:

(1)

Para definir a recorrência de C1(H, N) é mais complicado. Considere o vetor offbox que representa o offset dos compartimentos (boxes), ou seja, é o andar que cada compartimento ocupa quando o compartimento mais embaixo está no primeiro andar. Esse vetor tem tamanho N. Seja offlift o offset do elevador, ou seja, é o andar ocupado pelo compartimento mais embaixo. Esse vetor tem tamanho H/N que é o número de vezes que um elevador com N caixas pára.

Observe que se o elevador é válido, então para todo andar a, existe exatamente um par (i, j) tal que a = offbox[i] + offlift[j] e que esses dois vetores caracterizam unicamente um dado elevador. É fácil ver que se offbox e offlift representam um elevador válido para H andares e N caixas, trocando os papéis deles, vai gerar um elevador, denotado por dual, válido com H andares e H/N caixas.

Considere então um elevador com blocos de tamanho 1. Temos que offbox[0] = 0 e offbox[1] > 1, já que a primeira e a segunda caixa não podem estar contíguas. Além do mais, o primeiro compartimento é o único capaz de visitar o segundo andar, ou seja o elevador deve parar também no primeiro andar e offlift[1] = 1. Trocando os papeis dos vetores, temos offbox[0] = 0 e offbox[1] = 1, ou seja, é um elevedor com L > 1. Assim, todo elevador para H andares, com N caixas e L = 1, corresponde a um elevador para H andares, H/N caixas e L > 1.

Exemplo de configurações duais. O primeiro é offbox = {0, 2, 4} e offlift = {0, 1}. O segundo é offbox = {0, 1} e offlift = {0, 2, 4}.

Por outro lado, é fácil ver que todo elevador para H andares, H/N caixas e L > 1, corresponde a um elevador para H andares, N caixas e L = 1. Lembrando que cada um desses vetores caracteriza unicamente um elevador, não é difícil de acreditar que há uma bijeção entre essas duas configurações, o que equivale a afirmar que o número de elevadores válidos em cada uma delas é exatamente o mesmo, permitindo finalmente que escrevamos a recorrência de C1(H, N)

(2)

Como H e N sempre diminuem, as recorrências em (1) e (2) são suficientes para resolver o problema que é simplesmente C1(H, N) + Cn(H, N).

Ainda está faltando o caso base. Como H começa maior do que N e nunca diminuímos H mais do que N, fica claro que H não chegará em 1 antes de N. Logo, basta tratar o caso em que N = 1. Só há um possível elevador para N = 1 com blocos de tamanho 1 e claramente não existem elevadores com N = 1 para blocos de tamanho maior do que 1.

Outro cuidado que devemos tomar é que só existe solução se N dividir H, então precisamos fazer essa verificação antes de rodar o algoritmo.

Finalmente, um detalhe sobre a implementação. A princípio a complexidade parece ser O(HN*div(N)), onde div(N) são os divisores de N, que é essencialmente O(sqrt(N)). Porém, como H e N são da ordem de 1000000000 (10^9), essa abordagem parece impraticável.

Por outro lado, note que quando chamamos Cn(H, N), apenas os O(sqrt(N)) divisores de N serão chamados e serão divididos por pelo menos um fator de 2. Sinceramente, não sei calcular uma complexidade mais justa, mas olhando por cima, parece que não serão chamadas muitas combinações de H e N.

Além do mais, podemos otimizar o algoritmo usando memoização. No caso usual usaríamos os valores de H e N para indexar uma matriz. Aqui, entretanto, não é possível devido à magnitude dos valores. Supondo um número pequeno de combinações H e N, podemos usar um mapa usando como chave o par (H, N) (map<pair<int, int> > da STL).

Minha implementação em C++ está disponível aqui.