Jogo da Ponte (SPOJ - WAYHOME)

Na semana passada, vi um problema engraçado no SPOJ chamado WAYHOME e decidi resolvê-lo, sendo o meu problema #698 para o ranking (759 resolvidos no total).
O problema baseia-se num puzzle que já tinha ouvido falar e que dá para fazer aos amigos:

Um grupo de pessoas pretende atravessar uma ponte usando uma lamparina. A ponte é perigosa e só 2 pessoas podem atravessá-la ao mesmo tempo. As pessoas caminham a velocidades diferentes, por isso, se 2 pessoas estão a atravessar a ponte, deslocam-se à velocidade da mais lenta. Além disso, está escuro, por isso uma das pessoas tem de levar a lamparina enquanto atravessam a ponte. 

Dadas as velocidades das pessoas, qual é o tempo mínimo para passar todas as pessoas de um lado para o outro? E.g. 3 pessoas com velocidades 1, 1 e 2, demoram 4min a atravessar (ver figura seguinte). Se forem 4 pessoas com velocidades 1, 2, 4, 8, demoram 15min. Porquê? E se forem N pessoas, que abordagem garante o menor tempo possível?

A ideia mais óbvia é usar a pessoa mais rápida para acompanhar as outras para o outro lado da ponte e depois trazer a lamparina para a esquerda com essa pessoa. No entanto, esta estratégia não resulta no exemplo dado com 4 pessoas: dá 16 em vez de 15. Uma estratégia melhor neste caso é:

1. Enviar as pessoas com tempos 1 e 2 para a direita (custo 2)
2. Trazer a lamparina para a esquerda com a pessoa 1 (custo 1)
3. Enviar as pessoas 4 e 8 para a direita (custo 8)
4. Trazer a lamparina para a esquerda com a pessoa 2 (custo 2)
5. Enviar as pessoas e 1 2 para a direita (custo 2), ficando todos à direita

O custo total é 15. Repetir esta estratégia de levar os 2 mais rápidos primeiro para a direita compensa enquanto os 2 mais lentos à esquerda forem suficientemente lentos para que a estratégia normal seja pior.

Voltando ao problema do SPOJ, existem no máximo 1000 pessoas e os tempos já vêm ordenados.
Para resolver isto com código, podemos ir passando as pessoas mais lentas para a direita, verificando qual é a melhor estratégia. Se tivermos 1 ou 2 pessoas, o custo é o tempo da pessoa mais lenta. Se tivermos 3 pessoas, o custo é o somatório dos 3 tempos como se pôde ver na figura anterior.

1 2 3 4 5 6 7 8 9

int JogoPonte(int* tempos, int n) { if (n <= 2) return tempos[n-1]; if (n == 3) return tempos[0] + tempos[1] + tempos[2]; int normal = tempos[0] + tempos[n-1] + JogoPonte(tempos, n-1); int outra = tempos[0] + 2*tempos[1] + tempos[n-1] + JogoPonte(tempos, n-2); return min(normal, outra); }

Na estratégia normal estamos a levar a pessoa mais lenta e voltar com a mais rápida. Na estratégia alternativa determinamos o custo dos passos 1 a 4 até voltamos a ter as duas pessoas mais rápidas novamente à esquerda.
O problema desta implementação é que faz 2 chamadas recursivas para n-1 e para n-2. Assim, o tempo de execução é O(2^N), o que é extremamente lento.

Para contornar este problema, podemos usar uma cache. Visto que cada chamada recursiva só depende dos valores de n-1 e n-2, podemos guardar os custos já calculados numa tabela e reutilizá-los. A cache requer O(N) de memória adicional, mas permite que o algoritmo corra em O(N). Esta técnica chama-se Memoization.

1 2 3 4 5 6 7 8 9 10 11 12

int cache[1001]; // inicializar a -1 int JogoPonte(int* tempos, int n) { if (cache[n] != -1) // se já foi calculado, retorna o custo directamente return cache[n]; if (n <= 2) return tempos[n-1]; if (n == 3) return tempos[0] + tempos[1] + tempos[2]; int normal = tempos[0] + tempos[n-1] + JogoPonte(tempos, n-1); int outra = tempos[0] + 2*tempos[1] + tempos[n-1] + JogoPonte(tempos, n-2); return cache[n] = min(normal, outra); }

Como disse anteriormente, a estratégia alternativa será usada enquanto as pessoas mais lentas forem lentas o suficiente. Quando passarmos à estratégia normal não voltamos a usar a alternativa. Assim, o código pode ser re-escrito sem a cache:

1 2 3 4 5 6 7 8 9

int JogoPonte(int* tempos, int n) { if (n <= 2) return tempos[n-1]; if (n == 3) return tempos[0] + tempos[1] + tempos[2]; int normal = 2*tempos[0] + tempos [n-2] + tempos[n-1]; int alternativa = tempos[0] + 2*tempos[1] + tempos[n-1]; return min(normal, alternativa) + JogoPonte(tempos, n-2); }

Neste caso, estamos a aplicar a estratégia normal 2 vezes seguidas para descartar as 2 pessoas mais lentas e fazer apenas uma chamada recursiva. Alternativamente, podemos escrever uma solução iterativa facilmente:

1 2 3 4 5 6 7 8 9 10 11

int JogoPonte(int* tempos, int n) { int custo = 0; for (; n > 3; n -= 2) { int normal = 2*tempos[0] + tempos [n-2] + tempos[n-1]; int outra = tempos[0] + 2*tempos[1] + tempos[n-1]; custo += min(normal, outra); } if (n <= 2) return custo + tempos[n-1]; return custo + tempos[0] + tempos[1] + tempos[2]; }

Como disse antes, quando deixarmos de usar a estratégia alternativa, vamos usar a normal até ao fim. Assim, o código poderia ser modificado para tirar partido deste facto. No entanto, apenas estaríamos a poupar umas somas e um if por iteração do ciclo. Neste caso, não compensa e assim o código fica mais compacto.