SRM 527

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

Os comentários estão fechados.

%d bloggers like this: