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.


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.


Topcoder: SRM 492

Janeiro 14, 2011

Topcoder é uma empresa que realiza diversos tipos de competições de programação. A mais famosa, de longe, é o SRM (Single Round Match), uma competição rápida de algoritmos. Além dessa, há competições de design e desenvolvimento de software, além das competições longas de algoritmos (Marathon Matches). Veja o site para mais informações.

O SRM é dividido em 3 fases: código, desafio e testes do sistema. A fase de código dura 75 minutos e consiste em resolver 3 problemas estilo maratona de programação. A diferença é que você submete no escuro, ou seja, sem saber se seu programa passou nos casos de testes do sistema. A fase de desafio te dá uma oportunidade de ganhar uns pontos extras fornecendo casos de teste que possivelmente quebre o código do oponente e dura 10 minutos. Depois disso, os programas de cada competidor são submetidos aos testes do sistema. Tem vários detalhes sobre pontuação que podem ser encontrados aqui .

Eu participo dos SRM’s desde 2007, mas sempre de maneira esporádica. Agora que me aposentei da maratona, decidi continuar praticando para não enferrujar (embora eu ainda programe bastante no meu mestrado). Uma coisa que eu deveria fazer mas nunca tive disciplina suficiente, é o post mortem da competição, ou seja, estudar os editoriais e aprender a fazer os problemas que não consegui durante a competição.

Minha ideia é tentar usar o blog para escrever sobre tais problemas. Sem mais delongas, vou apresentar uma breve descrição e a solução dos problemas que não consegui resolver.

Time Traveling Tour

Dado um grafo ponderado e não-orientado G e uma lista de cidades L, deseja-se encontrar um passeio iniciado no vértice 0, que visite as cidades na ordem em que aparecem em L (o passeio pode conter cidades intermediárias que não necessariamente são visitadas). Há um diferencial porém: nesse passeio você pode viajar no tempo e voltar a uma cidade pela qual já passou, com custo zero. Queremos o passeio de menor custo. Link para o problema.

Se não houvesse essa viagem do tempo o problema seria fácil: ache o menor caminho entre todos os pares de vértices e some a distância entre cidades consecutivas de L.

A solução do editorial, descreve um algoritmo de programação dinâmica. O estado é definido por uma tripla (C, i, j), que representa o menor custo de se sair da cidade C e visitar as cidades L[i], …, L[j]. A resposta do problema é dada por (0, 0, |L|-1).

A sacada dessa abordagem é que não importa qual o caminho feito até chegarmos em C. Vamos inverter o pensamento: podemos ir a uma cidade D e então voltar para a cidade C com custo zero. Logo, a partir de uma dada cidade C, iremos usar outras cidades para visitar trechos de i, … j.

Considere o exemplo abaixo, onde as cidades são identificadas por letras e os números indicam a ordem em que devem ser visitadas. A cidade de partida é ‘A’.

Exemplo: letras são rótulos do vértices; números sobre os vértices representam a ordem em que devem ser visitados; os números em azul sobre as arestas representam os custos.

Podemos ver que uma solução ótima é a seguinte: vai de A a B com custo 3 e visita B, vai então até D com custo 2. Volta no tempo para A e visita C com custo 3. Volta no tempo para A e vai até E com custo 8. O total fica 16.

Em termos da tripla, poderíamos representar (A, 0, 3) como {dist(A, B) + (B, 0, 1)} + {dist(A, C) + (C, 2, 2)} + {dist(A, B) + (B, 3, 3)}. Por sua vez, (B, 0, 1) = (B, 0, 0) + {dist(B, D) + (D, 1, 1)}. A base da recursão é quando i = j ou i > j. No primeiro caso, (C, i, j) = dist(C, L[i]). No segundo significa que já visitamos todas as cidades então (C, i, j) = 0.

Uma observação importante é que {dist(A, B) + (B, 0, 1)} + {dist(A, C) + (C, 2, 2)} + {dist(A, B) + (B, 3, 3)} pode ser reescrita como

(1) {dist(A, B) + (B, 0, 1)} + (A, 2, 3),

pois (A, 2, 3) será recursivamente decomposto até que eventualmente a primeira forma apareça.

Isso reduz nosso trabalho a encontrar uma cidade (no exemplo é B) e um índice k, tal que essa cidade vai visitar as cidades i, …, k. A recorrência então fica:

(C, i, j) = INF
Para cada cidade D :
  Para cada índice k = i ... j :
      (C, i, j) = min {(C, i, j), 
                    dist(C, D) + (D, i, k) + (C, k+1, j)

Há dois problemas: essa recorrência pode ser muito ineficiente para os limites do problema, já que o número de operações fica O(50^5). Outro problema é quando k = j. Nesse caso teremos uma recorrência cíclica, pois chamaremos (D, i, j) que por sua vez pode chamar (C, i, j) novamente.

A solução do competidor those trata esses dois problemas. Note que só precisamos considerar o caso k = j porque pode existir uma cidade para a qual não se volta com a máquina do tempo. Então definimos uma segunda tripla {C, i, j} que corresponde ao menor custo de se visitar as cidades i e j, só que necessariamente voltando no tempo para C pelo menos uma vez.

Como sabemos que {C, i, j} voltará ao menos uma vez usando a máquina do tempo, podemos quebrá-lo em duas partes (antes e depois dessa volta):

(2) {C, i, j} = min{(C, i, k) + (C, k + 1, j)} para algum k = i … j – 1

Agora (C, i, k) e (C, k + 1, j) podem ou “delegar” a tarefa de visitar as cidades i a j para outras cidades ou ele mesmo quebrar em mais pedaços (que seria o equivalente a delegar a tarefa para a própria cidade C).

A recorrência de (C, i, j) fica assim:

(3) (C, i, j) = min{ {D, i, j} + dist(C, D)} para alguma cidade D

Observe que essa abordagem elimina a recorrência cíclica e de quebra reduz a complexidade para O(50^4). O trecho que calcula essa recorrência é o seguinte:

i64 eval2(int C, int i, int j){ 
  if (pd2[C][i][j] != -1) return pd2[C][i][j]; 
  pd2[C][i][j] = INFLL; 
  for(int k=i; k<j; k++)
    pd2[C][i][j] = min(pd2[C][i][j], eval(C, i, k)+ 
                        eval(C,k+1, j));
  return pd2[C][i][j]; 
} 
i64 eval(int C, int i, int j){ 
  if (pd[C][i][j]!=-1) return pd[C][i][j]; 
  if (i == j) return dist[C][L[i]]; 
  pd[C][i][j] = INFINITY; 
  for(int D=0; D<n; D++) 
    pd[C][i][j] = min(pd[C][i][j], dist[C][D]+
                      eval2(D, i, j)); 
  return pd[C][i][j]; 
} 

Sendo que a resposta do problema é dada por eval(0, 0, |L|-1).

A minha ideia era postar uma explicação para o problema mais difícil também, o TimeTravellingGogo. Porém, achei tão difícil e levei tanto tempo para pegar a ideia do problema TimeTravellingTour que desanimei. O próprio autor dos problemas disse que eles estavam bem difíceis. Tanto que somente uma pessoa acertou o problema de 1000 pontos.

É incrível que 31 pessoas tenham acertado o problema TimeTravellingTour! Isso quer dizer que eles tiveram a ideia e implementaram corretamente em 75 minutos! Eu lendo o editorial levei umas 2 semanas só para entender a ideia :/