24 · Entrenar con problemas IOI

Entrenar con problemas IOI · Ruta de Aprendizaje

Antes de empezar. Compilar programas: 01 - Tu primer programa; generar soluciones exhaustivas: 13 - Backtracking; para el ejemplo de suma máxima, Kadane de 14 - Programación dinámica I. Cada problema puede requerir otros módulos, indicados en su nota.

🎯 Objetivos

Al terminar este módulo sabes:

  • Elegir problemas IOI a tu medida usando las estadísticas del vault.
  • Trabajar el formato real: graders, subtareas, interactivos.
  • Complementar la revisión del código con casos reproducibles mediante stress testing.
  • Usar soluciones oficiales y simulacros para profundizar lo aprendido.

📖 La lección

Este vault es tu gimnasio

Desde aquí, la ruta deja de ser una escalera y se vuelve un mapa: los Temas del vault (con su qué abarca / qué no), las páginas de algoritmo con implementaciones, y 72 problemas IOI reales (2015–2026) con enunciado, paquete oficial y estadísticas. La brújula de contenidos es el Syllabus IOI — entrena lo que entra, ignora lo excluido.

Cómo elegir problema (sin morir en el intento)

Cada nota de problema trae su línea de dificultad (media, cuántos sacaron 100, cuántos 0). Elige primero por prerequisitos y una subtarea alcanzable. Una media alta puede reflejar puntos parciales accesibles; el porcentaje de 100 describe resolución completa y es una señal distinta. Estas puertas de entrada están en el vault:

ProblemaMediaPor qué es buena puerta
Mutating DNA (2021)93/100prefijos + conteos
Connecting Supertrees (2020)78/100DSU + construcción
Arranging Shoes (2019)74/100greedy + Fenwick
Combo (2018)74/100tu primer interactivo
Tiling Game (2026)73/100invariante constructivo
Detecting Molecules (2016)66/100greedy con ventana

El formato IOI de verdad

La interfaz depende del paquete del problema. Un formato habitual pide implementar funciones que llama un grader, en vez de escribir un main que lea con cin. Otros formatos pueden usar entrada/salida o archivos; en tareas interactivas puede haber llamadas a una biblioteca o comunicación con un manager. Antes de programar, revisa la firma y los comandos oficiales. El siguiente dibujo ilustra el formato de funciones:

graderlee la entrada, mide, corrigetu códigosolo funciones, sin maininit(n, datos)query(u, v)return respuestauna conversación: el grader pregunta, tú respondesen los interactivos, además, tú puedes preguntarle a él (y hay un límite de preguntas)cada carpeta de problema trae el grader oficial para correr esto en tu máquina

Si el diagrama no cabe, deslízalo horizontalmente.

Cada carpeta de problema del vault trae los graders y ejemplos oficiales para correr local. La guía completa del flujo (compilar con grader, probar, depurar) es Formato IOI y debugging — léela antes de tu primer intento serio.

La estrategia de subtareas, ahora en serio

Un problema IOI no se “resuelve o no se resuelve”: se cosecha. Lee todas las subtareas antes de programar; asegura las baratas (fuerza bruta del módulo 13 incluida). Cada restricción adicional puede habilitar una idea más sencilla; luego considera qué habría que cambiar para resolver el caso general.

Encontrar tus propios bugs: stress testing

Un veredicto WA no siempre muestra la entrada que falló. Comparar una solución rápida con una enumeración independiente puede producir un caso pequeño que sí puedas seguir a mano. Ambas versiones deben respetar el mismo problema y formato.

Un ejemplo completo: suma máxima no vacía

Lee n y n enteros; imprime la mayor suma de un subarreglo contiguo no vacío. Para este ejercicio, 1≤n≤100000 y cada valor está entre −10⁹ y 10⁹. La solución rápida usa Kadane del módulo 14. La fuerza bruta solo se ejecutará con n pequeño.

Una versión con error intencional inicia actual=0, actualiza actual=max(0,actual+x) y conserva la mayor suma. Para 3 seguido de -5 -2 -7, imprime 0: eligió el subarreglo vacío, prohibido.

La fuerza bruta enumera cada inicio l y cada final r≥l. No incluye intervalos vacíos:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// Enumeración O(n^2): se usa solo con casos pequeños.
int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    long long mejor = a[0];
    for (int l = 0; l < n; l++) {
        long long suma = 0;
        for (int r = l; r < n; r++) {
            suma += a[r];
            mejor = max(mejor, suma);
        }
    }
    cout << mejor << "\n";
}

Sus sumas candidatas son −5, −7, −14, −2, −9 y −7; la respuesta es −2. Se inicia el máximo con un elemento real, no con cero. Es O(n²), suficiente para comparar casos pequeños.

Descarga estos archivos en una carpeta de práctica:

  • sol_incorrecta.cpp: versión con el error que vamos a encontrar.
  • sol.cpp: versión corregida, que inicia con el primer elemento y decide entre empezar de nuevo o continuar.
  • bruta.cpp: enumeración anterior.
  • gen.cpp: con semilla 1 entrega el caso negativo anterior; con las demás, n entre 1 y 8 y valores entre −10 y 10.
  • stress.py: ejecuta ambos programas y conserva el primer fallo. Necesita Python 3.

La semilla es el argumento de ./gen 42: permite reproducir el mismo caso con el mismo generador. Se combinan un caso borde deliberado y casos aleatorios; el azar no garantiza encontrar un error.

Compila inicialmente la versión incorrecta con nombre de ejecutable sol, que es el que espera el script:

g++ -O2 -std=c++17 gen.cpp -o gen
g++ -O2 -std=c++17 bruta.cpp -o bruta
g++ -O2 -std=c++17 sol_incorrecta.cpp -o sol
python3 stress.py --casos 1000

Se detiene en la semilla 1 con DIFERENCIA. caso.txt conserva 3 y -5 -2 -7; salida_sol.txt contiene 0 y salida_bruta.txt, −2. Reducir el caso a un único −2 conserva el fallo y aísla la causa: permitir un vacío.

Ahora compila la corrección y repite:

g++ -O2 -std=c++17 sol.cpp -o sol
python3 stress.py --casos 1000

La versión corregida debe coincidir en esos casos. El script distingue diferencias de respuesta, errores de ejecución y timeouts; conserva stderr y la semilla. Por defecto cada proceso tiene dos segundos, ajustables con --timeout 5. Sobrescribe esos archivos de diagnóstico en la carpeta de trabajo.

El mismo algoritmo con una función y un grader

Como ejemplo didáctico, descarga suma_maxima.h, funcion.cpp y grader.cpp. El header declara suma_maxima(a); tu función devuelve el resultado; el grader aporta main, lee y escribe:

g++ -O2 -std=c++17 grader.cpp funcion.cpp -o sol
./sol < caso.txt
python3 stress.py --casos 1000

Imprime −2 para el caso negativo y permite reutilizar el mismo stress: el grader adapta la interfaz de función a entrada/salida. Este grader no valida la respuesta: solo la imprime; la comparación la hace el script con la bruta. En un problema IOI real usa la firma, restricciones, archivos y comandos de su paquete oficial; un interactivo puede requerir un manager distinto.

gensemilla icaso.txtn ≤ 8solla tuyabrutaenumeracióndiffiguales:siguiente idifieren:¡lo tienes!1000 veces, con semillas 1, 2, 3, …si difieren, revisa el caso y ambas soluciones para localizar el errormil casos sin diferencias ayudan a buscar bugs; la demostración sigue pendiente

Si el diagrama no cabe, deslízalo horizontalmente.

Si aparece una diferencia, compara ambas salidas y revisa también la fuerza bruta. Tener dos programas no garantiza que uno esté bien. Conviene que la enumeración siga directamente la definición del problema y use una idea diferente de la optimización.

Los casos pequeños hacen viable la enumeración y facilitan reducir un contraejemplo. Después de corregir, conserva ese caso y vuelve a compararlo junto con otros límites y casos aleatorios.

Sirve para dos cosas distintas, y la segunda es la que casi nadie usa: depurar un WA, y buscar contraejemplos a un greedy todavía no demostrado — exactamente lo que te pidió el módulo 23. Si sobrevive mil casos, solo sabes que coincide en esos casos. Combina entradas aleatorias con casos límite y enumeración exhaustiva pequeña; después demuestra el greedy. Un contraejemplo sí basta para refutarlo.

Cuándo no aplica: en tareas interactivas (ahí el caso lo construye el manager, ver Formato IOI y debugging) y cuando hay varias respuestas válidas — en ese caso no compares las salidas con diff, sino escribe un tercer programa que verifique que tu salida cumple lo que pide el enunciado, y compárale solo el puntaje.

Aprovechar una solución oficial

Intentar ejemplos pequeños y una solución para alguna subtarea ayuda a leer la editorial con una pregunta concreta. Si una pista desbloquea el problema, puedes continuar desde ahí; no hace falta esperar un tiempo fijo.

Al estudiar una solución oficial, busca qué observación hace posible el algoritmo y por qué cubre todos los casos. Reimplementarla sin copiar permite poner a prueba esa explicación. Los simulacros de Simulacros son una opción para practicar también la selección de problemas y el uso del tiempo.

🏋️ Práctica

Práctica directa: Reproducir un contraejemplo

Ejecuta sol y bruta del ejemplo con entrada 3 / -5 -2 -7. La versión con el error imprime 0; la bruta imprime -2.

En los ejemplos de entrada y salida, / separa líneas; no se escribe en el archivo.

Aplicar en problemas

Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.

Secuencias IOI propone un orden de problemas con pistas para avanzar cuando haga falta. Simulacros ofrece conjuntos para practicar en condiciones de competencia.

Un comienzo posible: Mutating DNA (entrada suave), Connecting Supertrees (construcción + DSU) y Combo (primer interactivo, con Formato IOI y debugging al lado). Después, el mapa es tuyo: navega por Temas según lo que quieras fortalecer.

Para pensar: una subtarea puede esconder un error

Quieres la suma máxima de un subarreglo no vacío. Tu solución parte con respuesta 0 y pasa una subtarea donde todos los elementos son positivos. Un stress test encuentra a = {−5, −2, −7}: tu programa devuelve 0 y la fuerza bruta devuelve −2. ¿Es un problema de velocidad o de definición?


← 23 - Greedy demostrable · Ruta de Aprendizaje · los temas: Temas →