Problema A - Conveyor Belts

Autor: João Pedro Neto (Universidade de Lisboa)
Tipo de problema: Programação Dinâmica

-------------------------
A B B C D A B D A E F D A
-------------------------   (exemplo de input)
B B C E D A E F A D D A E
-------------------------

Testar todas as combinações possíveis está fora de hipótese (não passa no tempo).

Uma solução "greedy" também não passa, porque não temos informação suficiente para decidir sem saber o que está no resto dos tapetes.

Problemas onde é necessário optimizar algo (máximos/mínimos) ou contar algo, e onde a solução "bruta" é exponencial, podem muitas vezes ser resolvidos com programação dinâmica (PD).

Vamos aplicar então PD a este problema. O "complicado" é arranjar uma formulação do problema que caiba no âmbito de PD. Consideremos o seguinte:

best[i][j] = melhor possível a partir da posição (i,j)
             [ou seja, tapete 1 na posição i, e tapete 2 na posição j]

Assim, quando estamos em (i,j), o que podemos fazer?

Se os produtos no início forem do mesmo tipo, podemos combiná-los e avançar para (i+1,j+1)
Podemos avançar para a posição (i+1,j), fazendo cair o 1º produto do tapete 1
Podemos avançar para a posição (i,j+1), fazendo cair o 1º produto do tapete 2

Destas hipóteses, queremos seleccionar a melhor. Em termos mais formais:

best[i][j] = máximo entre:
         - valor[tipo[tapete1[i]]] + best[i+1][j+1] (se tipo[tapete1[i]] == tipo[tapete2[j]])
         - best[i+1][j]
         - best[i][j+1]

No caso de existirem várias hipóteses que dão o máximo valor, é pedido que seja devolvido o mínimo número de pares de produtos para atingir esse valor. Para obedecer a essa restrição, podemos por exemplo guardar também uma matriz pairs[i][j] que guarde o mínimo número de pares para atingir o valor guardado em best[i][j], e ter isso em conta quando seleccionamos a melhor das 3 hipóteses dadas anteriormente.

Finalmente, para implementar a solução para este problemas, podemos escolher uma de duas técnicas para escolher a ordem de preenchimento das matrizes best[][] e pairs[][]:

Bottom-up: uma vez que para um dado par (i,j) apenas precisamos dos valores com índices maiores (de i e/ou j), podemos preencher no sentido "inverso" ao dos tapetes, e começar a preencher a partir dos maiores índices, continuando até aos menores e ao início dos tapetes.
Memoization: resolver pela ordem "normal" e quando um valor for necessário, verificar se já foi calculado. Caso já tenha sido computado, é só devolver; caso contrário, calcula-se e armazena-se, para que se o valor esteja disponível para computações futuras que dele necessitem.

Estas duas técnicas são "gerais" para problemas de PD e uma ou outra pode ser mais indicada, dependendo do problema em questão, pelo que se aconselha que um participante de concursos de programação esteja confortável com o uso de uma ou de outra.

Ligações interessantes: