Problema C - Entrega de Pizzas

Tipo de problema: Programação Dinâmica
Autor do Problema: Miguel Araújo (CMU - DCC/FCUP) e Pedro Ribeiro (DCC/FCUP)

O Problema
Dado um conjunto de N casas dispostas numa linha e identificadas por coordenadas inteiras, a tua tarefa é calcular qual o percurso que minimiza a soma dos tempo de entrega, isto é, qual a ordem em que as casas devem ser visitadas de modo a que a soma do tempo que a lambreta demora a chegar a cada uma delas é a menor 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 experimentar todas as permutações possíveis de casas. A ideia é visitá-las por essa ordem e para cada combinação ir calculando incrementalmente o tamanho do caminho a percorrer.

Notem que uma solução greedy não é correta. Greedy aqui significa procurar uma resposta ótima local, como por exemplo tentar ir sempre para a casa mais próxima (como o primeiro caso de teste de exemplo mostra). Há outras heurísticas possíveis de se fazer, mas nenhuma delas é totalmente correta pois falha em casos onde a melhor solução passa por mudar o sentido do caminho várias vezes.

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

Solução Melhorada:
Vamos ainda pensar em testar vários caminhos possíveis, mas ser um pouco mais inteligentes. Claramente não faz sentido seguir para a direita, entregar uma pizza na última casa de todas, ignorando todas as que passarmos pelo caminho, voltar para a esquerda... Se passarmos por uma casa e ainda não lhe distribuímos uma pizza, então mais vale distribuir agora do que ter que voltar lá! Assim, temos muitos casos que a solução anterior considera que podemos imediatamente ignorar.

Vamos começar por fazer um conjunto de observações. A primeira é que quando estamos numa determinada casa (ou na própria loja) temos apenas duas opções a seguir: ou vamos para a esquerda ou vamos para a direita. Isto serve para evitar exatamente a situação referida no parágrafo anterior, pois ao irmos para a esquerda ou para a direita vamos parar na casa mais próxima que ainda não visitámos, entregar uma pizza e refletir numa nova decisão: e agora, esquerda ou direita? Sendo assim temos uma solução recursiva que passa por preencher uma lista de N passos (podemos representar cada passo com um inteiro por exemplo, onde 0 significa esquerda e 1 direita) onde cada passo indica qual a decisão que tomámos. Assim algo como [0,1,0,0] (Esquerda, Direita, Esquerda, Esquerda) significa que visitámos primeiro a casa mais próxima de onde estamos à esquerda, depois a da direita, novamente esquerda e para terminar mais uma esquerda. Para cada lista que geramos, podemos facilmente simular a entrega de cada pizza e assim calcular o custo associado.

Para facilitar a implementação convém guardar as casas à esquerda e as casas à direita separadamente e contar quantas há à esquerda e à direita da loja (o input vir ordenado facilita um pouco). Assim a solução recursiva passa por fazer uma chamada como: calcula(posicao, n_esquerda, n_direita), onde 'posicao' representa a posição onde estamos, 'n_esquerda' quantas casa há à esquerda da loja que ainda não têm pizzas entregues e 'n_direita' quantas à direita, mantendo ao mesmo tempo uma lista que representa o nosso caminho. Agora calcular calcula(posicao, n_esquerda, n_direita) passa por ou calcular a resposta e verificar se é melhor que a melhor que já temos caso já tenhamos percorrido todas as casas, ou então preencher n com um 0/1 a posição 'posicao' da lista e chamar calcula(posicao + 1, n_esquerda - 1, n_direita)/calcula(posicao + 1, n_esquerda, n_direita - 1).

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

Solução Ótima:
A Solução Ótima funciona como uma pequena extensão da solução anterior, mas muito mais eficiente. Vamos usar uma técnica tão famosa nas ONI chamada Programação Dinâmica. A ideia aqui será ter um estado a partir do qual vamos calcular o seu resultado a partir de outros estados, isto incrementalmente até chegarmos a um conjunto de casos base. A diferença aqui será que guardaremos a lista de estados como uma matriz, o que significa que não será preciso recalcular para cada estado a resposta.

Seguindo só esta descrição poderá parecer que isto é apenas uma pequena modificação da solução anterior, mas vai requerer um pouco mais de esforço. A razão é simplesmente porque não podemos fazer o mesmo que fizemos na solução anterior de guardar a lista de decisões e no fim calcular a resposta. Aqui a única coisa que temos para cada estado é o resultado dos estados anteriores.

Vamos começar por definir o nosso estado. Continuando o raciocínio da solução anterior, temos que cada estado terá de considerar quantas casas há por visitar à esquerda e à direita da loja. Podemos agora observar que sabendo isto, só podemos estar numa de duas posições: após cada movimento vamos estar na última casa em que entregámos uma pizza e esta casa apenas pode ser uma de duas. Seja 'n_esquerda' o número de casas a quem já entregamos pizzas à esquerda da loja para o estado atual e 'n_direita' o mesmo mas para a direita da loja, então apenas podemos estar na casa de ordem 'n_esquerda' ou na casa de ordem 'n_direita', sendo esta ordem crescente segundo a distância à loja. A razão pela qual só pode ser uma destas é porque como só faltam 'n_total_esquerda' - 'n_esquerda'/'n_total_direita' - 'n_direita' (número total de casas à esquerda e à direita da loja) casas a entregar, já entregámos pizzas a 'n_esquerda'/'n_direita' casas e se tivéssemos entregue a uma casa mais afastada ou mais próxima que esta então teríamos de ter passado por uma casa sem entregar uma pizza no processo. Sendo assim, se além de 'n_esquerda' e 'n_direita' soubermos qual foi a última ação que fizemos (se foi andar para a esquerda ou direita) sabemos exatamente onde estamos. Assim o nosso estado será: [sentido, n_esquerda, n_direita], onde 'sentido' será apenas ou 0 ou 1 representando esquerda e direita respetivamente.

Excluindo casos base, a solução será simétrica quer o nosso passo anterior tenha sido esquerda ou direita. Por isso para simplificar a discussão vamos considerar que 'sentido' = 0 neste estado em particular. Agora, o valor para [sentido = 0, n_esquerda, n_direita] será o mínimo entre: abs(seq_esq[n_esquerda] - seq_esq[n_esquerda - 1])*(n_total_esquerda - n_esquerda + n_total_direita - n_direita) + DP(0, n_esquerda + 1, n_direita) e entre: abs(seq_dir[n_direita] - seq_esq[n_esquerda - 1])*(n_total_esquerda - n_esquerda + n_total_direita - n_direita) + DP(1, n_esquerda, n_direita + 1), onde seq_esq[] e seq_dir[] são duas listas ordenadas (por ordem de afastamento à loja) das posições das casas a entregar pizzas respetivamente à esquerda e à direita da loja e abs() é a função valor absoluto. Os dois casos correspondem a escolhermos ir para a esquerda ou irmos para a direita. Para entender melhor a razão por detrás destas contas basta pensar que quando nos movemos para uma casa perdemos um certo tempo. Esse tempo será acumulado por todas as casas que visitarmos no futuro. Assim o que estamos a fazer com abs(seq_dir[n_direita] - seq_esq[n_esquerda - 1])*(n_total_esquerda - n_esquerda + n_total_direita - n_direita) é calcular o tempo que gastamos a ir da casa onde estamos à casa seguinte à direita (o mesmo se aplica à fórmula para movimento para a esquerda) e multiplicá-lo pelo número de casas que ainda nos restam visitar, pois todas estas casas acumularão este custo no seu tempo de espera. Finalmente somamos o valor do estado seguinte correspondente a fazer essa operação, que aqui chamamos de DP() (cujo valor estará na nossa matriz de programação dinâmica).

O caso base nesta solução será quando 'n_esquerda' for igual a 'n_total_esquerda' e 'n_direita' for igual a 'n_total_direita', significando isto que já entregámos todas as pizzas. O seu valor é trivialmente de 0, pois não precisamos de nos movimentar mais para sítio nenhum.

Sendo esta solução de Programação Dinâmica, cada estado só é calculado uma única vez, havendo O(N^2) estados e demorando cada um O(1) de tempo a calcular (dados os anteriores).

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

Notas de implementação:
Nas duas últimas soluções é preciso ter atenção aos casos base e ao caso inicial (pois começamos a contar da loja). Adicionalmente, termos de ter atenção a quando já não vale a pena andar mais num certo sentido. Se 'n_esquerda' for igual a 'n_total_esquerda' mas 'n_direita' não for igual a 'n_total_direita' não podemos efetuar movimentos para a esquerda, apenas para a direita.

Notem também que denotei a matriz de Programação Dinâmica como DP(). Usei '()' para generalizar, pois esta solução pode ser implementada tanto por uma estratégia Bottom-Up como Top-Down (memoization). Caso não conheçam alguma usem os links em baixo.

Ligações interessantes:

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