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ú.
En ejercicio.cpp, descomenta la línea // verificar(ans);.
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
coutromperí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.
En ejercicio.cpp busca el bloque // ETAPA 3 (TODO) y descoméntalo:
else if (are_connected({camino.front()}, {v})) { camino.push_front(v);}
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!