Olimpiada de Informatica IOI 2011 Problema 1 Dia 1.

EL problema era el siguiente:
http://www.ioi2011.or.th/hsc/tasks/MEX/garden.pdf

Se tiene un grupo de personas que van a ser un tour sobre un grafo, las personas al situarse en un nodo siempre escogen la arista con menor peso (o como dice el problema la más hermosa), si ellos vinieron de la arista más hermosa escogen las segunda más hermosa, si ya no hay más opciones de elección, entonces regresan por la que entraron al nodo. Su tarea es ver de cuantas formas ellos pueden moverse una cantidad K de pasoso sobre el grafo y llegar a un Nodo Destino especifico.
Para algunos casos, pueden ser varias preguntas donde cambian el valor de K pero el destino sigue siendo el mismo.




Subtarea 1 (49 puntos)
2 ≤ N ≤ 1 000
1 ≤ M ≤ 10 000
Q = 1
G[0] es un entero entre 1 y 100, inclusivo.

Solución:
Una solución que se puede aplicar para el caso especifico de la subtarea 1, es realizar una simulación para cada nodo y contar hasta llegar al máximo G[0], seria aproximadamente 1000*100 la complejidad, recordar que deben pre calcular los mejores y segundos mejores aristas para no estar explorando las 10,000 aristas, en eso radica sacar estos 49 puntos.


Subtarea 2 (20 puntos)
2 ≤ N ≤ 150 000
1 ≤ M ≤ 150 000
Q = 1
G[0] es un entero entre 1 y 1 000 000 000, inclusivo.




Subtarea 3 (31 puntos)
2 ≤ N ≤ 150 000
1 ≤ M ≤ 150 000
1 ≤ Q ≤ 2 000
Cada elemento de G es un entero entre 1 y 1 000 000 000, inclusivo.


Solución:
Bueno este caso no se puede utilizar la técnica pasada ya que G es mayor a 1 000 000 000 y el números de nodos es mayor a 150 000, de primea instancia debemos tener un grafo con listas ligadas para manejar la cantidad de nodos que hay.
En este punto debemos observar que nada más nos interesa saber para cada nodo el más hermoso camino y el segundo más hermoso. ( Bueno la explicación del porque solo dos es simple , ya que si vengo por el segundo mejor o el tercer o el ultimo mejor camino siempre escogeré el mejor en el siguiente paso, en el caso de venir por el mejor siempre escogeré el segundo mejor). De ahí es simple desprender que para diferencia un paso de otro es suficiente saber si vengo o no del mejor camino y el nodo en el que estoy. Obviamente no se puede utilizar aun así la técnica de programación dinámica porque tendríamos que guardar el nodo más los pasos dados en el grafo, más la arista de la que vengo. Un total de 150,000 * 1,000,000,000 * 2 que seria demasiado, entonces ya que reduje en algo el problema que es lo que me falta?.
¿Que otra cosa observamos del problema?
Bueno en el problema es claro que siempre o por lo general se va ser una o dos vertientes, es fácil observar que siempre se van a formar ciclos, estos ciclos si contienen al nodo final podremos calcular por medio de divisiones y módulos si va a llegar a un K o no.
Por ejemplo tenemos un ciclo de tamaño 10 , sabemos que tardamos 100 pasos en llegar a el, y sabemos que nuestro nodo destino se encuentra en este ciclo y es el numero 2 despues de a ver entrado. Y el largo que tenemos que encontrar es de 10230, ok entonces son 10230 – 100 pasos para llegar a nuestro nodo, si es negativo el resultado entonces no llegamos, en otro caso tenemos 10130 sacamos el modulo 10 que sería igual a 0, pero como nuestro nodo destino es el número dos después de entra al ciclo entonces no llegamos a el en el numero de pasos que estamos buscando. Esta operación la realizamos para cada nodo y por ello es necesario guardar la información correcta, en este caso distancia al ciclo , posición del ciclo, tamaño del ciclo.
Entonces ahora si podemos usar la programación dinámica. Por cada nodo * arista del que provino guardar la distancia al nodo base, Si el no se encontró entonces regresar un valor determinando que no se encontró y si no , la distancia al ciclo que lo contiene y el tamaño del ciclo.
En total se harían (N * 2 + M ) * Q operaciones. Lo cual nos serviría para la subtarea 2 y subtarea 3.

Si tiene dudas o sugerencias o criticas, no duden en comentarlas.

Saludos.