Resolviendo el #TuentiContest: Problema 12 – The Stargate Problem

Hola de nuevo. A ver si esta semana hacemos coincidir las fechas del mes con los problemas que resolví y terminamos las recopilaciones el domingo. Hoy, el problema 12. Dejamos el volante de un coche normal y nos dedicamos ahora a viajar en el espacio y, si tenemos suerte, en el tiempo. Como te comenté en el problema anterior, esta solución también es en C++. Recuerda que también puedes ver mis soluciones a los otros problemas de la competición. Más allá del disfraz futurista y complicado del problema, en realidad es un problema típico de teoría de grafos. Un claro problema para separar a los que estudiaron informática de los que empezaron por otros lados (telecomunicaciones, electrónica, diseñadores web y autodidactas) y aprendieron a programar en el camino. Aquí, la máxima dificultad de los organizadores fue buscar las referencias de Stargate y The Big Bang Theory. Análisis del problema La entrada de datos se resume bastante bien con la imagen del problema. Nos darán un grafo dirigido, representado como una matriz de adyacencia, en la que cada celda indica el costo de viajar del nodo i al nodo j. Dada esta información, nos piden calcular cuál es el tiempo mínimo de viaje entre un par de nodos. ¡Ah! y sumarle al resultado 25000, solo porque sí. En caso de que no pudiésemos determinar el mínimo o que fuese imposible realizar el viaje, debíamos responder BAZINGA. Antes de continuar quiero usar este párrafo como paréntesis para indicar que en este problema el primer ejemplo tiene errores. Para empezar no son 5 nodos, son 6. Y luego la distancia mínima (0,4) no es 25750, es 27445. La distancia mínima de 25750 corresponde al viaje (0,5). Y si no, que alguien me corrija, por favor. Lo más importante en este problema era notar que existen costos y ciclos negativos en el grafo. Imagina que el costo de viajar de A a B de forma directa sea 100 y que, por otro lado, hay un ciclo negativo tal que viajar de A a A sea -10. Una situación como la anterior hace imposible calcular el costo total mínimo de ir de A a B pues podemos dar vueltas sobre A infinitas veces para bajar el costo tanto como queramos y luego ir a B. Fíjate en la imagen:

Este detalle era el que nos daba la solución del problema. Para calcular caminos de coste mínimos, el arsenal de teoría de grafos nos ofrece varias posibilidades: Dijkstra, Bellman-Ford y Floyd-Warshall. Los dos primeros obtienen el camino mínimo entre un par de nodos dado (de hecho, el segundo es el algoritmo ideal para este problema), el último va más allá y calcula el camino mínimo entre todos los pares de nodo (y este fue el que usé en mi solución).

¿Y por qué calculé el mínimo entre todos los pares sí solo nos pedían uno? Simple, es el único que me sé de memoria. Por alguna razón que nunca he comprendido no hay manera que memorice alguno de los dos primeros. Sin embargo, Floyd-Warshall siempre ha sido fácil de recordar para mi y por esa razón fue el que elegí.

Sin importar cuál eliges entre los dos últimos lo importante es saber que Dijkstra no funciona si existen aristas de costo negativo. Por lo tanto, no podía ser usado en esta situación.

Solución enviada En vista de que el problema nos indica que el costo inicial de quedarse en un sitio es cero, luego de ejecutar Floyd-Warshall sobre el grafo, los ciclos negativos podrán verse revisando la diagonal de la matriz. Si algún elemento de la diagonal es negativo, entonces existe un ciclo de costo negativo en el nodo en cuestión. Sin embargo, eso no asegura que el coste mínimo que nos interesa no se pueda obtener. Lo que hago es recordar el coste mínimo calculado en ese momento y volver a ejecutar el algoritmo. Si el ciclo negativo es parte del camino mínimo que nos interesa, en una segunda pasada el costo disminuirá. Entonces podremos concluir que el mínimo sería infinito. Esta solución, aunque está lejos de ser la más óptima, resolvió el problema sin inconvenientes de tiempos de ejecución, tanto los casos de test como los de submit. Les dejo entonces con la implementación en C++.

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include<boost/tokenizer.hpp>

using namespace std;
using namespace boost;

void floydWarshall(vector<vector<int> >& universe){
  int maximum = 1<<30;
  int size = universe.size();
  for(int k=0;k<size;k++){
    for(int i=0;i<size;i++){
      for(int j=0;j<size;j++){
        if(universe[i][k] != maximum &&
             universe[k][j] != maximum)
          universe[i][j] = min(universe[i][j],
                                 universe[i][k]+universe[k][j]);
      }
    }
  }
}
int main() {
  int maximum = 1<<30;
  string line;
  char_separator<char> espacio(" t");
  while(getline(cin,line)){
    tokenizer<char_separator<char> > info(line,espacio);

    tokenizer<char_separator<char> >::iterator it = info.begin();
    int numberOfPlanets = atoi((*it).c_str()); it++;
    int earthIndex = atoi((*it).c_str()); it++;
    int atlantisIndex = atoi((*it).c_str()); it++;
    vector<vector<int> > universe(numberOfPlanets,vector<int>(numberOfPlanets, maximum));

    for(int i=0;i<numberOfPlanets;i++) universe[i][i] =0;

    char_separator<char> coma(",");
    for(;it!=info.end();it++){
      tokenizer<char_separator<char> > edge(*it,coma);
      tokenizer<char_separator<char> >::iterator itEdge = edge.begin();

      int from = atoi((*itEdge).c_str()); itEdge++;
      int to = atoi((*itEdge).c_str()); itEdge++;
      int distance = atoi((*itEdge).c_str()); itEdge++;
      universe[from][to] = distance;
    }

 

    floydWarshall(universe);
    // es infinito llegar
    if(universe[earthIndex][atlantisIndex] == maximum){
      cout << "BAZINGA";
    } else { // se puede llegar
      int firstCost = universe[earthIndex][atlantisIndex];

      int negative = 0;
      for(int i=0;i<numberOfPlanets && negative >= 0;i++)
        negative = universe[i][i];

      // Hay ciclos negativos pero podrian no influir
      if(negative < 0){
        // recalculo a ver si la distancia disminuye
        floydWarshall(universe);
        if(universe[earthIndex][atlantisIndex] < firstCost) {
          cout << "BAZINGA";

        // El ciclo negativo no influye en el camino deseado
        } else {
          cout << universe[earthIndex][atlantisIndex]+25000;
        }
      } else {
        cout << universe[earthIndex][atlantisIndex]+25000;
      }
    }

    cout << endl;
  }
  return 0;
}

Como pueden ver, el algoritmo de Floyd-Warshall son solo cinco líneas (quitando las llaves de cierre y refiriéndome solo a lo importante). Por esa razón me lo sé de memoria. Como en todas mis soluciones en C++, la mayor parte del código se la llevó la lectura de datos (en el trozo oculto de código). La lógica general de la solución es la que les comenté anteriormente y comienza a partir de la línea 51. El orden del algoritmo de Floyd-Warshall es O(n³), y en vista de que lo llamo dos veces en caso de que haya algún ciclo negativo, la solución general es O(2n³). Solución mejorada Para este problema hay dos tipos de mejoras: mejorar la solución manteniendo el algoritmo de Floyd-Warshall y escribir una solución mejor implementando Bellman-Ford. Me encargaré de comentar la primera. Como habrás notado, el problema principal en mi solución es la forma en que detecto que el mínimo es infinito, buscando primero cualquier ciclo negativo y luego haciendo una segunda pasada para ver si el ciclo afecta el camino deseado. Sin embargo, el algoritmo de Floyd-Warshall puede reescribirse para recuperar los caminos mínimos y no solo su coste. Nos ocupará un poco más de memoria pues necesitaremos otra matriz pero eso casi nunca es un inconveniente. Con el cambio hecho, luego de la primera pasada podemos revisar los nodos involucrados en el camino mínimo y verificar de forma inmediata si alguno de ellos tiene un ciclo negativo. Así, hacemos más eficiente la verificación, la cual será en el peor de los casos O(n) si el camino involucra todos los nodos del grafo y terminamos con una solución mucho más rápida. Para recordar un camino en Floyd-Warshall necesitaremos una matriz adicional que recuerde los pasos intermedios. La incializaremos al mismo tiempo que nuestra matriz universe. Los números de línea los muestro con respecto a la solución enviada e indican dónde comenzaría cada trozo.

vector<vector<int> > universe(numberOfPlanets,vector<int>(numberOfPlanets, maximun));
vector<vector<int> > paths(numberOfPlanets,vector<int>(numberOfPlanets, -1));

Y luego, la iremos actualizando cada vez que actualizamos un costo de viaje dentro del algoritmo de Floyd-Warshall.

if(universe[i][k]+universe[k][j] < universe[i][j]) {
  universe[i][j] = universe[i][k]+universe[k][j];
  paths[i][j] = k;
}

De esta manera, después de la primera pasada podremos recorrer el camino mínimo que nos interesa y verificar si tiene algún ciclo negativo. En caso de que lo tenga, podemos responder inmediatamente BAZINGA. Ahora verán primero el método que busca ciclos negativos en los nodos del camino mínimo y luego el trozo que reemplazaría las líneas [51,76].

bool negativePath(vector<vector<int> >& universe, vector<vector<int> >& paths, int from, int to) {
  int intermediate = paths[from][to];
  if(intermediate == -1 ||
     intermediate == from || intermediate == to) {
    return (universe[from][from] < 0) && (universe[to][to] < 0);
  } else {
    bool v1=negativePath(universe,paths,from,intermediate);
    bool v2=negativePath(universe,paths,intermediate,to);
    return  v1||v2;
  }
}
floydWarshall(universe,paths);
if((universe[earthIndex][atlantisIndex] == maximum || negativePath(universe,paths,earthIndex,atlantisIndex)){
  cout << "BAZINGA" << endl;
}else {
  cout << universe[earthIndex][atlantisIndex]+25000;
}

Como ves, no solo es más eficiente sino también mucho más legible. Prueba fiel de que nuestra primera solución no siempre es la mejor solución. Y ni hablar si cambiamos a implementar Bellman-Ford desde el principio y hacemos una lectura y parseo de datos decente. Y tú, ¿cómo lo resolviste?

7 thoughts on “Resolviendo el #TuentiContest: Problema 12 – The Stargate Problem

    1. Hola Alejandro.

      El valor de infinito lo manejé con un entero muy alto. Encontrarás la asignación en la línea 11 y un condicional para solo utilizar caminos no infinitos en las líneas 16 y 17.

      Si algún arco tiene valor infinito, se salta en el cálculo del valor mínimo. Por eso puedo hacer la operación de la línea 18.

      Espero que te sea útil la información. Cualquier otra cosa, no dudes en escribirme.

      Saludos.

      1. Hola José.

        Te agradezco enormemente por tu colaboración, he podido darle solución al problema que tenia.Esta muy interesante tu blog, cuando salga de exámenes mirare los problemas de programación para intentar de resolverlos.

        Te estaré molestando mas adelante, para preguntarte por inteligencia artificial.

        Nuevamente gracias y muchos éxitos.

Deja un comentario