Olimpiada Internacional de Informática Problema 2 dia 1 (Race)

Explicaciones por Rodrigo Burgos Domínguez.
Aquí pueden leer el problema en español http://www.ioi2011.or.th/hsc/tasks/MEX/race.pdf.
El problema es el siguiente, dado un árbol conectado con aristas con peso, encontrar un camino que inicie en un nodo y termine en otro que tenga un costo de K (el costo es la suma del peso de todas las aristas del camino) , si existen varias soluciones encontrar la que tenga el menor numero de aristas, adicional a esto debemos aclarar que no se puede visitar mas de una vez los nodos ni las arista.
En todas las olimpiadas como les comentaba separan los casos de prueba para medir la habilidad de cada concursante, las subtareas se dividen en las siguientes:
Subtarea 1 (9 Puntos)
1 < Numero de nodos <= 100
1    ≤ K ≤ 100
Las árbol de forman una línea. Para 0 ≤ i < N-1, la autopista i conecta la ciudad i con la ciudad i+1.
Solución caso 1:
Bueno para este caso especial nos dicen que es una línea, entonces podemos seleccionar las combinaciones de estas líneas, todos los pares (a,b) donde a ≤ b, y validar que la distancia hacia este punto es igual a K, si es así guardar el su tamaño, y si es menor a cualquiera encontrado guardarlo como solución. Este algoritmo tiene una orden de O(n^2),  y es suficiente para sacar solo 9 puntos.
Subtarea 2 (12 Puntos)
 1 ≤ N ≤ 1 000
 1 ≤ K ≤ 1 000 000
Solución caso 2:
  Aquí observamos que no se puede aplicar el mismo algoritmo, ya que no nos aseguran que están en línea, entonces tenemos un árbol hecho y derecho que debemos atacar, sabemos que N es menor a 1000 y K es menor a 1000000, bueno K no nos interesa tanto en este momento puede ser mayor o menor, todo depende de las combinaciones que tengas en el árbol, pero pensemos un poco como atacar un problema de esta magnitud, realmente no quisiera estar en los zapatos de estos jóvenes.
   Este problema se requiere utilizar un lista de adyacecia, esto es para mejorar el algoritmo que se tiene que implementar (Después agregaré en el blog como implementar una lista de adyacencia).  La solución que corre en tiempo y no es tan complicada es la siguiente. Para cada nodo del árbol vamos a suponer que es la raíz, y corremos una búsqueda en profundidad. Como es un árbol sabemos que no va a existir un ciclo, entonces es suficiente con saber quien es el padre de la exploración para no regresar por alguna arista que nos regrese a un nodo ya explorado,
¿Que mas llevamos en la función recursiva?
Tenemos que llevar el número de aristas exploradas y la suma de las aristas. Y tendríamos una función así y como variable global a K:
void profundidad( int nodo, int anterior, int numaristas, int suma){
   int nodo;
    if( suma == K ) solucion = min( solucion , suma);
    if( suma > K ) return;
    for( nextnodo= 0; nextnodo < numnodos[ nodo ] ; nextnodo++ )
        if( grafo[ nodo ][ nextnodo] ¡= anterior )
            profundidad( grafo[nodo][nextnodo], nodo, numaristas + 1, suma + costo[ nodo ][ nextnodo ]);
}

Esta solución pensaran muchos que no va a correr en tiempo, pero veamos las complejidades:
   Si la ejecutamos para todos los nodos tenemos primero N multiplicado por la complejidad de la búsqueda en profundidad, si la búsqueda en profundidad fuera con una matriz de adyacencia , seria de orden N cuadrada, pero como es con una lista de adyacencia entonces la complejidad es de N + E donde E es el numero de Adyacencia y como es un árbol entonces E = N – 1, por tanto la complejidad es de 2N^2 y en total haría aproximadamente 2,000,000 de operaciones por caso, lo cual correria en un tiempo menor a 3 seg.
Y con esto tenemos  12 puntos, pero como esta solución también resuelve el caso 1 entonces son 12 + 9 = 21 puntotes.

Subtarea 3 (22 puntos)
1 ≤ N ≤ 200 000
1 ≤ K ≤ 100

Solucion caso 3:
 Esta solución varia de la anterior ya que el numero N es muchísimo mayor es de 200,000 pero K es muy pequeña, ¿como resolver este problema aprovechándonos de la bondad de K?
  Pues no me parece una respuesta sencilla de resolver, me gustaba más que N fuera pequeño pero vamos a ponernos a pensar un poco. Bueno de entrada necesitamos una lista de adyacencia, por que N es muy grande y si no lo hacemos seria absurdo tener una matriz de 200,000 x 200,000. Leyendo el problema vemos que el tamaño de las aristas son de 0 a un 1000,000 y como el varlos puede ser  0, no podemos suponer que el máximo numero de aristas en la solucion sea 100 ya que pueden ser muchos 0’s.
Aquí vamos a utilizar otra técnica que tendrá que ser detallada en otro post, pero es realizar una programación dinámica sobre un árbol de muchos nodos. La programación dinámica se implementa basándonos en la idea que aun que son muchos nodos las combinaciones de llegar a un nodo son pocas, realmente para llegar a un nodo debes usar alguna arista que conecte a el , pero como es un árbol son pocas aristas, en total hay como N*2 formas distintas de llegar a todos los nodos ( por que concluimos esto? Pues por que hay N -1 aristas y solo pueden conectar a dos nodos uno a un extremo y otro hacia el otro). Básicamente es usar el mismo método de profundad que para el caso 2 pero guardando la arista y su dirección , en vez del padre, por que si sabes la arista y su dirección sabemos el nodo al que llegas y del nodo del que vienes, y además como K es menor a 100 entonces podemos guardarlo en la programación dinámica.
   Y la complejidad del algoritmo es de (N*2) *N*K, que es es como 200,000,000 de operaciones, que corren en menos de 3 segundos, y el tamaño del arreglo donde podemos guardar la programacion dinamica esta dado por [arista][direccion][K], que seria de 200,000*2*100 = 40,000,000.
 Y con esto podemos sacar los 22 puntos sin contar los primero 9, pero no nos sirve como solución para el caso 2 por que en el otro caso K es muy grande. Pero no es difícil validar que si K es más grande de 100 no lo guardes en la programación dinámica y siguas explorando para encontrar todas las soluciones. Entonces con unas pequeñas modificación se pueden obtener 43 puntos.

Subtarea 4 (57 puntos)
 1 ≤ N ≤ 200 000
 1 ≤ K ≤ 1 000 000

Solucion:
   Para este caso, todos los miedos posibles recaen en el, todas las combinaciones peores, tenemos N que puede tener hasta  200,000 nodo y a K el costo a buscar puede llegar a 1,000,000, y como pueden observar ninguna implementación anterior nos sirve para resolver este problema.
   Pensemos Pensemos( diría Jimmy Neutron).  No puedo guardar K en mi dinámica por que ya seria N * N y eso no cabe en ningún lado, bueno no con la memoria que tenemos disponible para este problema, y aparte realizar ese tamaño de operación es demasiado.  Bueno primero seguimos con la premisa de que debemos guardarlo en una lista de adyacencia.


*** Queda pendiente encontrar la solución para este caso espero tenerla pronto, si alguien tiene alguna sugerencia es bienvenida ***


Saludos