Problema D - The Magician's Problem

Autor: Luís Paquete (Universidade de Coimbra)
Tipo de problema: Geometria
Número de ficheiros de teste: 10

Este é um problema giro com várias resoluções possíveis. Vou exemplificar uma solução que corre em O(B^3), o que basta para passar (B<=200). Era possível fazer bem melhor, mas assim ilustro três princípios que todos os meus alunos têm obrigação de saber:

O primeiro princípio aplica-se logo on facto de bastar fazer algo O(B^3). Para quê complicar se passa no tempo? Em concurso devemos analisar as restrições de memória e tempo e fazer aquilo que é mais fácil de fazer.

O princípio de reduzir dimensões dá muito jeito. Neste caso, se o problema fosse apenas em 2D, seria mais fácil de resolver mentalmente? Um ponto onde podemos atravessar a parede seria definido apenas por Y. Assim, seja parede(Y) a quantidade de parede que atravessamos ao longo da coordenada Y. Resolver o problema seria descobrir o Y com menor valor desta função. E vale a pena testar todos os Y? Não! Basta testar apenas os Y de início e logo a seguir ao fim de cada caixa! Este princípio pode ser aplicado em 3D. E os possíveis pontos candidatos são pares (Y,Z) através do mesmo raciocínio.

Como descobrir parede(Y,Z)? Tomando apenas em linha de conta a coordenada X, chamemos ao ponto incial de uma parede INi e ao ponto final dessa parede OUTi. Se tivermos todos estes pontos ordenados (por X), basta-nos então percorrê-los por ordem e, caso o seu Y e Z seja relevante para o cálculo em causa, saber "dentro de quantas paredes estamos" e com isso calcular a "quantidade de parede que atravessamos"! Podemos também usar a ordenação dos pontos por Y e por Z para por exemplo eliminarmos pontos candidatos iguais (evitando recalcular). E ainda podemos fazer muitos mais cortes.

O essencial aqui era de algum modo usar a "geometria" dos dados para de algum modo melhorarmos e eficiência da nossa pesquisa. Neste caso, o ponto chave foi "ordenar", algo que é recorrente em problemas deste tipo.

Ligações interessantes