Problema C - Contrabando de Mel

Tipo de problema: Programação Dinâmica
Autor do Problema: Pedro Paredes (DCC/FCUP)

O Problema
Dado um conjunto de N malas e os respetivos alcances A_i, a tua tarefa é determinar o número máximo de mini-potes de mel que o Darth Vader consegue levar para a Austrália sem ser preso por contrabando. Podes assumir que o número de mini-potes de mel disponíveis era suficiente para encher todas as malas, se tal fosse possível.

Restrições
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Solução Base:
A solução mais simples de todas seria tentar todas as combinações de malas e ver a melhor. Esta solução teria uma complexidade fatorial.

Notem que uma solução greedy não é correta. Greedy aqui significa procurar uma resposta ótima local, como por exemplo tentar usar sempre as malas com menores alcances ou escolher sempre a primeira.

Esta seria uma solução fatorial que daria aproximadamente 30 pontos.

Solução Melhorada:
Uma solução melhor seria considerar todas as soluções que acabam na k-ésima mala. Chamemos à função F(k) a função que representa o maior número de mini-potes de mel que se podem distribuir por malas a acabar na mala k. F(k) é então igual a 1 + max{0; F(k - A_k), se A_{k - Ak} ≤ A_k; F(k - A_k - 1), se A_{k - Ak - 1} ≤ A_k + 1; ... ; F(1), se A₁ ≤ k - 1}. Esta fórmula aparentemente estranha apenas significa que a solução é igual a pôr um mini-pote de mel na mala k e considerar todas as malas atrás da mala k onde se podem por novos mini-potes (ou seja, cujos alcance e alcance de k sejam menores ou iguais à distância entre as malas) e considerar a melhor solução a acabar nessa mala (que equivale a chamar a função F em cada mala). O valor da função F(k) é o 1 + F da posição que maximiza o valor de F(k).

Define-se assim uma função recursiva para F. A resposta será max{F(1), F(2), ..., F(N)}.

Esta seria uma solução O(N ^ 3) que daria aproximadamente 60 pontos.

Solução Ótima:
A solução final passaria por recorrer a Programação Dinâmica. Em vez de recalcular todos os valores de F(x) guardar estes valores numa tabela e assim só os calculamos uma única vez. Assim, é possível uma solução Bottom-up que calcula o F(1) e depois F(2)... até N e vai guardando os valores.

Também era possível extender a solução melhorada apresentada acima e utilizar Memoization, que consiste em calcular e guardar o valor de F(x) caso ainda não tenha sido calculado e devolver o valor caso já tenha sido calculado.

Esta seria uma solução O(N ^ 2) que daria aproximadamente 100 pontos.

Nota sobre soluções:
Seria possível obter uma complexidade melhor ao guardar os valores de F numa estrutura de dados bidimensional (como uma quadtree, bidimensional porque é necessário ter atenção aos alcances) e fazer a pesquisa do valor em tempo logaritmico e o update do valor também em tempo logaritmico. Para simplificar a resolução do problema não era pedida esta solução.

Ligações interessantes:

• Programação Dinâmica na Wikipedia e no TopCoder.