Programacion, ACM ICPC, UVa Online Judge

Entradas etiquetadas como ‘Grafos’

UVa Online Judge – 12363 – Hedge Mazes

El link del problema es el siguiente:
12363 – Hedge Mazes

El problema es de Grafos.
En el problema, nos dan la descripción de un grafo, que son las conexiones entre sus nodos y un numero Q de consultas. Cada consulta esta compuesta de 2 números u,v que representan un nodo origen y un nodo destino y para cada una de las consultas, hay que responder de manera eficiente si solo existe un camino entre esos 2 nodos.
Si es que llega a existir un solo camino entre esos nodos, imprimimos una Y, en caso contrario, imprimimos una N.

Cuando digo de manera eficiente, me refiero a que las consultas se deben de hacer lo mas rápido posible.

La solución consiste en hacer uso de los puentes del grafo.
Un puente es una arista en el grafo que si es removida, el grafo se desconecta.
Si nos ponemos a pensar en este hecho, eso quiere decir que al pasar por el puente, solo existe ese camino único para ir de un nodo A a un nodo B.

Por lo tanto, tenemos que si dos nodos están conectados solamente por puentes, quiere decir que la ruta es única.
Así que la solución, es, una vez generados los puentes, podemos usar conjuntos disjuntos para obtener cuales elementos están en el mismo conjunto, y si están en el mismo conjunto, es que existe solo 1 camino entre ellos.

Código en C++

Anuncios

UVa Online Judge – 10278 – Fire Station

El link del problema es el siguiente:
10278 – Fire Station

El problema es de Grafos y se resuelve utilizando Dijkstra.
Lo que nos dan en la entrada es la descripción de unas intersecciones de alguna ciudad, en la cual ya existen algunas estaciones de bombero, y lo que nos piden es decidir en que lugar hay que colocar la nueva estación para minimizar la máxima distancia desde una estación hacia todas las intersecciones.
Esto se resume a un Dijkstra con múltiples fuentes. Lo que hay que hacer es colocar la nueva en la estación 0, luego en la 1, luego la 2, etc, e ir determinando cual de todas las estaciones es la mejor para colocar la nueva estación de bomberos.

Ejemplo:

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10

Ya se dispone de una estación de bomberos en la intersección 2.
Ahora al agregar la estación nueva en la 1 tenemos que la distancia mas grande hacia las demás es 20
Si fuera en la 2 seria 30
Si fuera en la 3 seria 20
Si fuera en la 4 seria 20
Si fuera en la 5 seria 10
Y si fuera en la 6 seria 20

Por lo tanto la respuesta es 5.

Código en C++

UVa Online Judge – 168 – Theseus and the Minotaur

El link del problema es el siguiente:
168 – Theseus and the Minotaur

El problema es de Grafos y la idea es solo hacer un recorrido.
El problema nos da la descripción de un grafo, nos dan la posición de Teseo y del Minotauro y un numero k, donde cada k movimientos Teseo deja una vela y el Minotauro ya no podrá pasar.
Conociendo eso nos piden la ruta que seguirían hasta el momento en el que Teseo pelee contra el Minotauro.
La idea es solo recorrer el grafo, e ir simulando los movimientos.
Cuando Teseo se va a mover, se mueve al primer nodo que no tiene vela de acuerdo a como se introdujo en la entrada y cada k movimientos imprimimos la letra que corresponde.
En el texto tenemos que dice que hay que recorrer en orden alfabético, pero no es asi.
La descripción del problema es errónea, puede que este motivo sea uno de los factores por los cuales varias personas obtienen WA.

Código en C++

UVa Online Judge – 10422 – Knights in FEN

El link del problema es el siguiente:
10422 – Knights in FEN

El problema es de Grafos y se soluciona con un BFS.
Lo que nos dan es una configuración inicial y hay que decir si es posible llegar a la configuración final que muestro a continuación, en menos de 11 movimientos.

 En este problema, lo importante es la representación del estado, que en este caso es un tablero de 5×5, así que una representación conveniente es una matriz de 5×5.
Para poder contabilizar los estados visitados, podemos utilizar un mapa de la estructura que tenemos, e ir insertando los estados conforme vallamos visitándolos.
Por ultimo hay que estar cocientes, que desde una configuración del tablero, hay 8 posibles movimientos que se pueden realizar, y cada vez que realizamos uno de estos movimientos, hay que intercambiar el centro y la pieza que corresponde de acuerdo al movimiento.

Código en C++

UVa Online Judge – 10044 – Erdos Numbers

El link del problema es el siguiente:
10044 – Erdos Numbers

El problema es de Grafos y se puede solucionar con un BFS.
El problema habla acerca de Paul Erdos (Que fue un gran matemático).
En la descripción de la entrada nos dan una lista de publicaciones en las que en algunas participo Erdos y otros colaboradores y en otras no.
Una vez leída la entrada, viene una lista de nombres, y a cada uno de ellos hay que calcularle a lo que el problema denomina “Numero de Erdos”.

Para calcular el numero pedido, el problema lo define como el numero de relaciones que hay para que alguien llegara a publicar algo con Erdos.
Las personas que publicaron directamente con el, tienen un Numero de Erdos igual a 1.
Las personas que publicaron con alguien que publico con Erdos, tienen un Numero de Erdos igual a 2.
Una persona relacionada con la persona del punto anterior, tiene un Numero de Erdos igual a 3.
Y así sucesivamente.

Si la persona no esta relacionada de ninguna manera con Erdos, se imprime la palabra “infinity”.
La solución consiste en generar un grafo a partir de las relaciones de los artículos y utilizar un BFS desde el nodo que corresponde a Erdos e ir guardando la distancia con la cual llegamos a cada nodo.
Al momento de la salida, si el nombre no fue visitado por el BFS o el nombre no existe en la base de datos de nombres que estan en las publicaciones, se imprime “infinity”, de lo contrario, la distancia que corresponda.
El BFS solo se ejecuta 1 vez y se accede a las consultas en tiempo constante.
El procesamiento de la entrada es algo complicado, pero es posible utilizando istringstream en C++ o StringTokenizer en Java, combinándolo con Mapas en C++ o HashMap en Java.

Para la separacion de los nombres en la linea de cada articulo, un nombre viene delimitado del lado derecho cuando encontramos una coma(,) o dos puntos(:) y antes de el hay un punto(.).
Ejemplo:

Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices

El primer nombre es
Smith, M.N.
Se puede observar que, antes de la coma(,), hay un punto, así que la cadena empieza desde el principio de la cadena hasta el punto antes de la coma.
El segundo y el tercero se obtienen de manera similar, solo que el tercero se obtiene con los dos puntos(:)
El resto de la cadena es irrelevante.


Código en C++

UVa Online Judge – 928 – Eternal Truths

El link del problema es el siguiente:
928 – Eternal Truths

El problema es de Grafos y se puede resolver con un BFS.
En la descripción nos dicen que hay un laberinto, y que tenemos que salir, pero con la restricción de primero movernos 1 casilla, después 2 casillas, después 3 casillas, y nuevamente 1 casilla, y así sucesivamente hasta encontrar la salida.
Como dije hay que moverse 1,2,3,1,2.. etc casillas, pero el costo de movernos esa cantidad de casillas es 1.
Ejemplo:
Tomemos de ejemplo la imagen que esta en la descripción del problema:
 El costo de la ruta es 7, ya que fueron 7 movimientos para salir del laberinto (1,2,3,1,2,3,1).

El algoritmo para movernos en el laberinto es BFS.
Cada vez que nosotros guardemos un estado en la cola, hay que estar conscientes en que tenemos que saber cuantas casillas avanzamos en el estado anterior, ademas de ir llevando la cuenta de cuantos pasos vamos dando hasta ese punto.

Para ir marcando las posiciones en donde vamos pasando, es necesaria una matriz de 3 dimensiones (int visitado[n][m][3]).
La tercera dimension en este caso sera de 3, que nos ayudara a indicar cuando pasamos por la posicion (x,y) con un paso de 1,2 o 3 pasos.

Para resaltar la importancia de la tercera dimension de tamaño 3, podemos notar que estamos en la casilla (x,y) y el ultimo paso que dimos fue de 3, por lo tanto el siguiente paso que tendremos que dar es de 1, lo cual nos llevaria a las casillas (x+1,y),(x-1,y),(x,y+1),(x,y-1).
Y ahora suponiendo que tambien estamos en la misma casilla (x,y) pero el ultimo paso que dimos fue de 1, por lo tanto el siguiente paso que tendremos que dar es de 2, los cual nos llevaria a las casillas (x+2,y),(x-2,y),(x,y+2),(x,y-2).

Como notaran, podemos llegar a casillas diferentes desde la misma posición. Por lo tanto es importante llevar en que casillas ya pasamos con pasos de 1,2 o 3 casillas.

Por ultimo, hay que revisar cuando nos movamos 1,2 o 3 casillas hacia alguna dirección las siguientes cosas:

  • Al movernos, no nos salgamos de los limites del laberinto
  • Que la casilla este desocupara
  • Que al movernos, no haya bloques intermedios bloqueando el paso

Código en C++

UVa Online Judge – 924 – Spreading the News

El link del problema es el siguiente:
924 – Spreading the News

El problema es de Grafos y se soluciona con un BFS.
El problema dice que hay una nueva noticia y cada día se esparce a los conocidos de la persona que lo conoce.
Lo que nos pide son 2 cosas:

  • El numero de personas máximo que se entera en 1 día de la noticia
  • El primer día en el que ese máximo se dio

El máximo de personas conocidas se puede dar en mas de un día, así que nos piden el primero de todos ellos.
Lo que hay que hacer es realizar un BFS y contar a cuantos nodos visitamos, pero por nivel.
Como la búsqueda en amplitud visita por niveles, solo es necesario contar que nivel tiene mas nodos y guardar que nivel fue.
Ejemplo:
6
2 1 2
2 3 4
3 0 4 5
1 4
0
2 0 2
3
0
4
5

Lo que nos dice la entrada es primero el numero de personas en la red, en este caso 6.
Esas personas están numeradas del 0 al 5.
Las siguientes 6 lineas (que es el numero de personas) describe la relación entre ellas.
El primer numero es el numero de conocidos, llamémoslo “m”, seguido de “m” números que representan a sus conocidos.
2 1 2 es el primer renglón, por lo tanto esta haciendo referencia al nodo 0 y esta conoce a 2 personas, que es la persona 1 y la persona 2.
Esto se repite para todos los demás y se ilustra la relación en la siguiente imagen:

La relación entre las personas no es bidireccional.
No por que la persona “x” conozca a la persona “y”, “y” conoce a la persona “x”.
De ahí vienen 3 consultas, seguido de 3 números, que nos indica desde que nodo sale la noticia.

La primera consulta sale del nodo 0.
El día 1 los conocidos de 0 se enteran de la noticia que son 1 y 2.
El día 2 los conocidos de 1 y 2 que no sepan la noticia se enteran que son 3 4 y 5.

Como ya todos conocen la noticia, termina el algoritmo y nos regresa que el día 2 se enteraron 3 personas.
Cuando no se entera ninguna persona se imprime un cero, que es el segundo caso de prueba que parte del numero 4.

Código en C++