Resolviendo el #TuentiContest: Problema 11 – Gas stations

Hola de nuevo. Empieza una racha de tres soluciones consecutivas en C++. Ahora, el problema 11. En esta ocasión nos ponen al volante de un coche para viajar alrededor de España, y como somos de los que no nos gusta parar a repostar, queremos hacerlo lo menos posible, sabiendo de antemano dónde están todas las estaciones de gasolina. Recuerda que también puedes ver mis soluciones a los otros problemas de la competición. El problema de las gasolinera me llama la atención de forma especial porque nos inclina a complicarnos más de la cuenta, cuando en realidad la solución es más sencilla de lo que se piensa. Análisis del problema La entrada consistía primero en un número que nos indica cuántos casos debemos contemplar y luego, para cada caso, capacidad del tanque, distancia total a viajar y distancias, desde el inicio, de cada estación. Quizás colocarlo después de las vacas es lo que nos inclina a complicarnos la vida pues la pregunta en este problema es muy parecida. ¿Cuál es la mínima cantidad de estaciones de servicio en las que debo parar y cuáles? Sin embargo, a diferencia de las vacas, aquí hay un dado implícito que facilita toda la solución. Cada vez que paramos en una estación de servicio, podemos llenar el tanque completamente. En el caso de las vacas, cada una nos ofrecía una cantidad distinta de leche y entonces había que buscar combinaciones óptimas. Como siempre podemos llenar el tanque, no hay diferencia entre cuál estación usar. Así que lo lógico será manejar lo más lejos que podamos y llenar el tanque solo cuando sea necesario para seguir avanzando. Esto, con seguridad nos dará una solución mínima. No hace falta programación dinámica ni mucho menos contemplar todas las combinaciones de estaciones. Un detalle adicional importante, no para nosotros sino para el jurado de la competición, es que la solución mínima no es única. Durante el evento, varias personas preguntaron si se evaluarían las distintas opciones (supongo que sí se hizo) y @TueniEng nunca respondió (al menos yo no vi que lo hiciera). Un ejemplo rápido de dos soluciones posibles: Queremos recorrer 100km, nuestro tanque solo rinde 70km y hay dos estaciones, a los 50km y a los 70km. En ambos casos solo debemos detenernos una vez y puede ser en cualquiera de las dos gasolineras. El algoritmo que les propongo se detendrá en la más lejana. En lo que respecta a dónde está el destino, puede ocurrirnos que esté entre dos estaciones de servicio o que esté al final de todas las estaciones. Ambos casos deben contemplarse, aunque me atrevería a apostar que no se probó ningún caso en el que el destino se encontrara antes de la última estación. Solución enviada Mi solución en C++ calcula la respuesta final mientras lee los datos de entrada. Partiendo desde la primera estación de servicio, cada vez que recibo la distancia a la próxima estación (o el destino, si se encuentra antes) calculo si puedo llegar y en caso de que no pueda, lleno el tanque en la estación donde estoy. En vista de que mi algoritmo calcula si es necesario repostar para llegar a la próxima estación, cuando termina de pasar por todas las estaciones, aún queda la posibilidad de que el destino esté aún más lejos, así que debo hacer una última verificación para saber si debo parar en la estación más lejana.

#include <iostream>
#include <list>

using namespace std;

int main() {
  int T;
  cin >> T;
  while(T-- > 0){
    int k, df, n;
    cin >> k >> df >> n;
    int sofar = 0;
    int di,dj;
    bool done = false;
    list<int> stops;
    cin >> di;
    for(int i=1;i<n;i++){
      cin >> dj;
      dj = min(df,dj);
      if(k+sofar < dj && !done){
        stops.push_back(di);
        sofar=di;
      }
      if(dj==df) {
        done = true;
      }
      di = dj;
    }

    if(df > dj) {
      if(k+sofar < df && !done){
        stops.push_back(dj);
      }
    }

    if(stops.size()==0){
      cout << "No stops" << endl;
    } else {
      list<int>::iterator it = stops.begin();
      cout << *it;
      for(++it;it!=stops.end();++it){
        cout << " " << *it;
      }
      cout << endl;
    }
  }
  return 0;
}

En las líneas [19,22] contemplo que el destino se encuentre antes de la próxima estación y verifico si puedo llegar al siguiente punto (sea gasolinera o destino final). Si no puedo llegar, lleno el tanque donde estoy, recuerdo cuánto en conducido y continúo. El condicional siguiente es para indicar si ya solucioné el problema. En ese caso debo terminar de leer los datos (recuerda que calculo la solución mientras leo los datos de entrada) sin realizar ninguna cuenta extra. Las líneas [30,34] realizar una última verificación en caso de que la estación de gasolina se encuentre más allá de la última estación. A partir de la línea 36, simplemente imprimo las estaciones en las que paré. Solución mejorada En lo que respecta a mi solución, pude haber colocado la condición !done mucho más arriba para limitar las cuentas a realizar luego de solucionar el problema. A pesar de que me salto correctamente la posibilidad de volver a detenerme en otra estación, todo el bloque de líneas [19,27] es innecesario si ya llegamos al destino y aún hay parte de él que se ejecuta hasta el final. Por otro lado, para obtener una solución general más limpia podríamos leer primero todos los datos y después calcular la solución. Dado que los datos de las estaciones ya están ordenados, vienen en una sola línea y están separados por espacios en blanco, la lectura y almacenamiento de ellos es un simple split. Al tener todos los datos leídos en un arreglo dinámico ordenado, podemos incluir también el destino final en él y buscar directamente cada estación más lejana con búsqueda binaria. Esto dejaría de forma independiente la lectura de datos y la solución del problema, lo cual podría ser más legible, pero no por ello es una solución más óptima. La lectura de datos, así se haga en una línea al estilo perl

@estaciones = split / /;

es O(n) y luego vendría una serie búsquedas binarias (una por cada estación mientras no lleguemos al destino) que sería en total O(k*log(n)) (o quizás no “n” si limitas cada vez el tamaño del arreglo sobre el que buscas). Al final, el orden del cálculo completo de la solución sería el mayor de ambos que es O(n), el mismo orden de mi solución. Lo que sí es cierto, es que utilizar otro lenguaje más amigable con la lectura y manipulación de arreglos te daría una solución más legible y con mucho menos líneas. Por ejemplo, siguiendo con perl, imprimir las estaciones al final sería simplemente:

print ( (join ' ', @paradas), "n" );

De todas formas, mi objetivo personal era utilizar C++ al máximo durante la competición para irme acostumbrando a su API y sintaxis, con la que hasta ahora no estaba muy familiarizado (y lo que me queda). Y tú, ¿cómo lo resolviste?