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++

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++

UVa Online Judge – 11110 – Equidivisions

El link del problema es el siguiente:
11110 – Equidivisions

Lo que nos piden es determinar si dada una descripción de una matriz, hay que decir si hay «n» conjuntos de «n» elementos en total.
La primera linea nos dice el numero de conjuntos que habrá, haré mención a esta variable como n, seguido de n-1 renglones.

Cada renglon indica las posicion de los elementos pertenecientes al conjunto 1,2,3,…,n-1.
Los elementos sobrantes en la matriz son los elementos que pertenecen al conjunto n.
Ejemplo:

5
1 1 1 2 1 3 3 2 2 2
2 1 4 2 4 1 5 1 3 1
4 5 5 2 5 3 5 5 5 4
2 5 3 4 3 5 4 3 4 4

Tomamos solo el primer renglon:
1 1 1 2 1 3 3 2 2 2
Aca hay que verlo como parejas que vendrian siendo las siguientes:
1 1
1 2
1 3
3 2
2 2
Esas parejas representan las coordenadas de los elementos en el conjunto 1.
Como se observa son 5 conjuntos pero solo nos dan 4 renglones, debido a que los elementos sobrantes en la matriz, representan al ultimo conjunto.

El primer paso es obtener cuantos elementos tiene cada conjunto
Por ejemplo si nos dan lo siguiente como entrada:
5
1 1 1 2
2 2
3 3
4 4
Podemos decir que esta mal, ya que el primer conjunto tiene 2 elementos y los demás 1 elemento, ademas que el ultimo conjunto tiene mas de 2 elementos.
Si la entrada no pasa la primera validación, podemos imprimir un «wrong».
Una vez validado que en la entrada todos los conjuntos tienen el mismo numero de elementos, hay que revisar que estén conectados.

Para la conectividad el problema especifica que es en 4 adyacencias (arriba,abajo,izquierda,derecha).
Lo que hacemos es recorrer la matriz y cada vez que encontremos un elemento que no hemos analizado, realizar un flood fill.
Cuando digo elemento, me refiero a cada posición de la matriz individualmente.
Ejemplo:

5
1 1 1 2 1 3 3 2 2 2
2 1 3 1 4 1 5 1 4 2
4 5 5 2 5 3 5 5 5 4
2 4 1 4 3 5 4 3 4 4

Esa entrada pertenece a la segunda imagen mostrada en el problema.
Una vez procesada la entrada y vemos que la validación es correcta, procedemos a revisar la conectividad.
Primero procederiamos a analizar el conjunto de unos, que no tiene problemas.
Después a analizar el conjunto de los cuatro, que solo marcaría los números 4 que se encuentran adyacentes, el de la posición 1,4 y 2,4.
Luego a analizar el conjunto del numero cinco, que marcara solo los números en la posición 1,5 y 2,5.
Luego a analizar el conjunto del numero dos, que no tiene problemas.
Luego a analizar el otro conjunto del numero 5, ya que estos no se contaron al analizar al primer conjunto encontrado.
Acá, al ver que analizamos un conjunto que ya estaba analizado, podríamos terminar el algoritmo y decir «wrong».

Si al terminar de realizar el flood fill sobre todos los conjuntos, tenemos que no analizamos nuevamente un conjunto, entonces la matriz dada es correcta.

Código en C++

UVa Online Judge – 439 – Knight Moves

El link del problema es el siguiente:
439 – Knight Moves

Este problema es de grafos y se puede solucionar con un BFS.
Lo que nos piden es el mínimo numero de movimientos que tiene que hacer un caballo sobre un tablero de ajedrez para llegar de una posición a otra.
Basicamente lo unico que hay que hacer es colocarse en la posicion inicial donde nos encontramos y visitar los 8 vecinos posibles de una casilla, verificando que la casilla sea valida en el tablero.
Para representar una posición nosotros podemos utilizar lo que es el «pair» de la librería #include<utility>

pair<int,int> ori,dest;

Para movernos en el tablero podemos utilizar 2 arreglos que contengan las 8 posibles combinaciones de movimientos del caballo:

int x[] = {1, 1,2, 2,-1,-1,-2,-2};
int y[] = {2,-2,1,-1, 2,-2, 1,-1};

Al utilizar la cola, hay que llevar el numero de pasos que se van dando para ir contabilizando, entonces opte por utilizar una pareja relacionada con un entero:

queue<pair<pair<int,int>,int> cola;

El primer elemento de la pareja, representa la posición x,y del caballo.
La segunda parte de la pareja es un entero, que representa el numero de pasos realizados.

 

Código en C++

UVa Online Judge – 1056 – Degrees of Separation

El link del problema es el siguiente:
1056 – Degrees of Separation

El problema es de Grafos.
Dado un grafo, nos piden revisar dos condiciones:

1.- EL grafo es desconectado
2.- Si no lo es, cual es la ruta mas larga que une a cualesquiera dos nodos

Para la representación del grafo, es recomendable una matriz de adyacencia, ya que el grafo es de a lo mas 50×50.
Para la manipulación de la entrada, es recomendable usar un mapa de un String con un Entero (map<string,int>), con el cual fácilmente a cada nombre le podemos asociar un numero.

Una vez representado el grafo en la matriz de adyacencia, procedemos a utilizar el algoritmo de Floyd Warshall.
Este algoritmo tiene complejidad n^3, pero debido a que el grafo es pequeño, se puede utilizar el algoritmo y obtener una respuesta en el tiempo limite.
Una vez ejecutado el algoritmo de Floyd Warshall, procedemos a buscar el numero mas grande de la matriz resultante.
Si el numero mas grande es igual a Infinito, tenemos que el grafo es desconectado, si no, procedemos a imprimir el numero obtenido.

Otro enfoque diferente, es utilizar una búsqueda por amplitud (BFS).
Para obtener la distancia, lo que hacemos es elegir un nodo aleatorio del grafo y ejecutamos el algoritmo.
Una vez ejecutado, nosotros conocemos la distancia de el nodo elegido hacia todos los demás. Si alguno tiene distancia igual a Infinito, entonces el grafo es desconectado.
Si no, procedemos a ejecutar nuevamente un BFS desde el nodo mas lejano obtenido de la primera búsqueda en profundidad, y sobre los resultados obtenidos, obtener la distancia mas larga.

Este problema básicamente consiste en encontrar lo que se le conoce como diámetro de un Grafo.
Hay un teorema que menciona el hecho que se esta utilizando acá. Si se elige un nodo aleatorio y se realiza una búsqueda en profundidad y elegimos a su vecino mas lejano y realizamos nuevamente una búsqueda en profundidad a partir del nodo obtenido anteriormente, obtendremos el diámetro del Grafo.

Código en C++