🎯 Mini-ejercicio guiado — Longest Trip (formato interactivo)

Objetivo: entender el formato IOI con grader y aprender a debuggear, no resolver el problema completo. Trabajas sobre Longest Trip. Guía teórica: Formato IOI y debugging.

Descarga el paquete completo, descomprímelo y abre una terminal dentro de longest-trip-ejercicio/. Incluye código inicial, grader y ejemplos; no necesitas acceso al repositorio privado.

Cómo correr (desde la carpeta descomprimida):

./correr.sh        # compila y ejecuta el ejemplo 01
./correr.sh 02     # ejemplo 02 (grande)

El script compila tu ejercicio.cpp junto al grader de ejemplo. Nunca usa -static (en Mac eso falla con library not found for -lcrt0.o).

¿Qué hace el programa?

Implementas longest_trip(N, D) y descubres el grafo preguntando are_connected(A, B) (¿hay arista entre el grupo A y el grupo B?). El grader imprime, por escenario: la longitud, el viaje, y el nº de llamadas que usaste; al final, el máximo de llamadas.


Etapa 1 — Correr el esqueleto y leer la salida (por hacer)

Corre ./correr.sh. Verás algo como:

5            <- escenario 1: viaje de longitud 5
0 1 2 3 4    <- el viaje
4            <- usaste 4 llamadas a are_connected
2            <- escenario 2: viaje de longitud 2
0 1
3            <- usaste 3 llamadas
4            <- maximo de llamadas

Checkpoint: ¿por qué en el escenario 2 el viaje es tan corto? Mira 01.in: el grafo del escenario 2 tiene dos aristas (0–1 y 2–3) en dos componentes. La Etapa 1 solo extiende por el final, así que se queda en 0 1.

Etapa 2 — Auto-verificar tu respuesta (la clave del debugging)

⚠️ El grader de ejemplo no comprueba si tu viaje es válido (eso lo hace el checker oculto del juez). Así que verifícalo tú.

  1. En ejercicio.cpp, descomenta la línea // verificar(ans);.
  2. Corre ./correr.sh. La función verificar imprime a cerr (stderr) cuántos pares consecutivos están rotos. Verás líneas [debug] longitud=....

Dos lecciones de oro:

  • verificar imprime a std::cerr, no a cout. Si imprimieras debug a cout romperías el protocolo del grader. Pruébalo: cambia un cerr por cout y mira cómo se corrompe la salida. (Luego revídelo.)
  • Esas consultas extra cuentan en el presupuesto. Por eso #define DEBUG 1 existe: lo pones en 0 antes de enviar al juez.

Etapa 3 — Extender por ambos extremos 🛠️ (tu turno)

En la Etapa 1 solo agregabas nodos por el final. Mejóralo: si el nodo nuevo no conecta con el final, intenta conectarlo con el frente del camino.

  1. En ejercicio.cpp busca el bloque // ETAPA 3 (TODO) y descoméntalo:
    else if (are_connected({camino.front()}, {v})) {
        camino.push_front(v);
    }
  2. Corre con verificar activo y compara la longitud y el nº de llamadas contra la Etapa 1.

Checkpoint: ¿mejoró algún escenario? ¿Cuántas llamadas usas ahora? (Recuerda: una solución correcta pero que se pase del presupuesto de llamadas saca 0.)


Para ir más lejos (opcional)

  • Esto no resuelve el caso difícil (densidad D=1 general). Mira cómo lo hacen las soluciones de referencia del paquete oficial:
    • la solución solution-subtask2.cpp del paquete oficial — idea de los dos extremos.
    • las carpetas solutions/correct/ y solutions/incorrect/ del paquete oficial — compara una correcta con una que da WA para entrenar el ojo.
    • solutions/model_solution/solution.cpp del paquete oficial — la solución oficial completa.
  • Lee las subtareas en el enunciado enlazado desde Longest Trip: la subtarea de densidad D=3 (grafo completo) se resuelve devolviendo cualquier orden, ¡con 0 llamadas!