|
|
Problema C - Nenúfares |
Tipo de problema: Grafos (Pesquisa em Largura)
Autor do Problema: Pedro Ribeiro (DCC/FCUP)
Este problema tem como base um dos problemas clássicos nestas competições: dado um grafo, determinar o caminho mais curto entre 2 vértices.
Construção do grafo:
Neste caso, estes 2 vértices representam as margens do rio e os restantes vértices estão associados aos nenúfares. Existe uma aresta (ligação) entre 2 vértices se a sua distância não excede a capacidade de salto da rã e o "peso" da ligação é se é gasta ou não energia.
Neste problema, as margens não são nós normais do grafo pois ligam-se a qualquer nenúfar que esteja a uma distância de um salto considerando apenas a sua coordenada X. Por outro lado, o número N de nenúfares pode ir até 20,000. Uma simples construção O(N^2) do grafo, considerando todos os pares de nenúfares, seria demasiado lenta. De facto, é dito no enunciado que cada nenúfar contém no máximo apenas 20 nenúfares atingíveis (ou seja, dentro da distância de salto). Assim, é possível determinar os vértices vizinhos de cada vértice de forma eficiente usando por exemplo um Sweep Line (e.g. ordenar os nenúfares por coordenada X e, em caso de empate, por Y e varrer os vizinhos em X dentro da distância de salto, verificando para cada X quais os nenúfares dentro da gama de coordenadas Y atíngiveis pela rã).
Solução base:
O enunciado garante que para um conjunto de testes valendo 60% dos pontos, N não excede 10. Assim, com um número tão reduzido de nenúfares é possível efectuar um puro brute force, ou seja, testar todos os caminhos possíveis de realizar entre uma margem e outra. Exemplo: considerando 3 nenúfares, o programa deve verificar os caminhos
Pesquisa da solução num problema mais simples:
Ignoremos para já a restrição associada à energia da rã. Como os saltos têm um custo unitário, para calcular o caminho mais curto, deve usar-se uma pesquisa em largura (BFS); se existissem "pesos" diferentes deveria usar-se o algoritmo de Dijkstra.
A pesquisa começa por visitar os nenúfares próximos da margem esquerda (para onde a rã pode saltar), depois os nenúfares atíngiveis com 2 saltos e assim sucessivamente.
 |
 |
 |
| 1º passo: nenúfares atíngiveis com um salto | 2º passo: nenúfares atíngiveis com dois saltos, visita cada um apenas uma vez! |
Assim, a resposta seria o caminho mais curto para um nenúfar próximo da margem direita + 1 (salto desse nenúfar para a margem) ou simplesmente 1 se fosse possível saltar directamente duma margem para a outra.
Extensão para o problema original:
No entanto, o problema exige que a rã atinga a margem direita com energia positiva. À primeira vista pode parecer tornar o problema muito mais complexo, mas na verdade é apenas necessário mudar o estado da pesquisa para satisfazer esta restrição. Com efeito, o estado da pesquisa passa a conter o vértice a explorar e a energia com que a rã chegou a esse nenúfar.
Considerando que a rã chega a um nenúfar n com uma energia e e pretende saltar para outro nenúfar k, o estado correspondente a esse salto será (k, e-1) ou (k, e), consoante a rã necessitou de gastar energia ou não.
O cálculo da resposta é semelhante ao caso anterior, com a diferença de se procurar apenas nós que permitam que a rã atinga a margem direita com energia positiva.
Conclusão:
A complexidade algorítmica desta solução é O(N*E*A), pois no máximo iremos explorar N*E nós na pesquisa em largura e cada um deles tem no máximo A nós adjacentes.
Ligações interessantes: