📘 Syllabus IOI (versión oficial 2025)

Resumen del documento oficial del Comité Científico (ISC) que define qué temas pueden aparecer en la IOI y cuáles están excluidos. Es la referencia para decidir qué entrenar y, sobre todo, qué NO vale la pena estudiar.

🏷️ Las 6 categorías

El syllabus clasifica cada tema en una de seis categorías (de más a menos apto):

SímboloCategoríaQué significa para entrenar
✓Incluido, sin límiteConocimiento previo dado por hecho; aparece sin explicación.
✓defIncluido, a definirDebes conocerlo; el enunciado dará la definición concreta.
✓ndIncluido, no en el enunciadoNo aparece nombrado, pero la solución puede requerirlo. El grueso del entrenamiento vive aquí.
?Fuera de focoNo se espera que lo sepas; rara vez aparece.
✗oExcluido, abierto a discusiónExcluido por ahora, frontera difusa.
✗Explícitamente excluidoGarantizado que ningún problema lo requiere. No lo estudies para competir.

Reglas de borde: lo que es prerequisito de algo incluido, también está incluido; lo que extiende algo excluido, también queda excluido; lo no mencionado es “fuera de foco”.


✅ Qué SÍ entra, por tema del vault

Grafos

✓nd BFS/DFS, componentes conexas, clausura transitiva · orden topológico · caminos Euler · caminos mínimos (Dijkstra, Bellman-Ford, Floyd-Warshall) · grafos bipartitos · DAG · árbol de expansión mínima (Kruskal y Prim) · biconexión (puentes, puntos de articulación) · SCC (conexión fuerte) · matching bipartito (O(V·E) por caminos aumentantes) · flujo máximo / corte mínimo (Ford-Fulkerson por caminos aumentantes).

Árboles

✓nd árboles (hoja, diámetro, bosque) · árboles con raíz · árboles de expansión · estructura (centro, centroide) · LCA en O(log n) · heavy-light decomposition · centroid decomposition.

Programación Dinámica

✓nd DP y sus optimizaciones explícitas: convex hull trick, Knuth-Yao, divide & conquer optimization. (Se desalientan problemas donde la optimización es un paso mecánico final; debe poder probarse que la técnica aplica.)

Estructuras de Datos

✓nd stacks/colas · representaciones de grafos · binary heap · DSU (Union-Find) · Fenwick (BIT) y segment tree (incl. “tournament/interval trees”) · BBST balanceado y aumentado · persistentes · anidamiento de estructuras (p.ej. secuencia de conjuntos) · tries · prefix sums · compresión de coordenadas · análisis amortizado.

Greedy

✓nd algoritmos voraces · (los argumentos de intercambio entran vía técnicas de prueba: inducción, contradicción, contraejemplo).

Geometría

✓nd puntos/vectores/rectas/segmentos · colinealidad, producto punto y cruz, giros horarios · intersección de rectas · área de polígono · punto en polígono · compresión de coordenadas · convex hull O(n log n) · sweep line.

⚠️ El ISC prefiere aritmética entera y objetos rectilíneos (evita precisión).

Matemática y Combinatoria

✓ enteros, operaciones, exponenciación rápida, paridad/divisibilidad, aritmética modular básica (suma/resta/multiplicación) · ✓nd criba de Eratóstenes, factorización, primalidad por división O(√n), Euclides (gcd), enteros de precisión arbitraria (ops básicas) · conteo: permutaciones/combinaciones, factorial y coeficientes binomiales, Inclusión-exclusión, pigeonhole, Pascal/binomio · teoría de juegos básica: posiciones ganadoras/perdedoras, minimax.

Búsqueda Binaria

✓nd búsqueda secuencial y búsqueda binaria (incluida la búsqueda sobre la respuesta).

Interactivos

✓def tareas reactivas / dirigidas por eventos (implementar el diálogo con el grader). Responder “consultas online” es aceptable.

Constructivos y Ad-hoc

✓nd estrategias de resolución (entender–planear–hacer–verificar, distinción de casos, generalización), fuerza bruta, backtracking, branch & bound. Un problema ad-hoc puede tocar incluso un tema “fuera de foco” si se resuelve sin conocimiento previo de ese tema.


⛔ Exclusiones clave (NO estudiar para competir)

Esto es lo más útil del syllabus: temas que ningún problema requiere.

  • Strings avanzados ✗: KMP, hashing de Rabin-Karp, suffix array/tree, suffix automaton, Aho-Corasick. → Solo entran strings básicos, búsqueda ingenua de substring y tries. (Ver Strings y Secuencias.)
  • Matemática pesada ✗: inverso/división modular, FFT, álgebra lineal (mult./exp./inversión de matrices, Gauss, interpolación polinomial), números complejos, cónicas, trigonometría, cálculo, estadística, resolver recurrencias, Burnside.
  • Teoría de juegos avanzada ✗: Sprague-Grundy / NIM general (solo entran posiciones ganadoras/perdedoras y minimax básico).
  • Flujos/matching avanzados ✗: algoritmos de flujo/matching más eficientes que Ford-Fulkerson, min-cost flow, matching general (no bipartito).
  • Estructuras avanzadas ✗: tablas hash, link-cut / árboles dinámicos, estructuras 2D (BIT 2D, treap de treaps), heaps de Fibonacci/binomiales.
  • Geometría dura ✗: dualidad punto-recta, Voronoi/Delaunay, intersección de círculos, geometría 3D, transformaciones vía álgebra lineal.
  • Teoría ✗: computabilidad, problema de la parada, clases P/NP y NP-dureza, criptografía, algoritmos distribuidos/paralelos.

Que un tema esté ✗ no impide que aparezca un problema ad-hoc relacionado; solo garantiza que no se necesita ese conocimiento para resolverlo.


🔧 Otras secciones (no algorítmicas) que sí se evalúan

  • Software Engineering ✓nd: traducir un algoritmo a un programa eficiente, leer/escribir en formato simple, probar y depurar tu propio código, gestión del tiempo y de riesgos durante la prueba, llevar versiones.
  • Computer Literacy ✓nd: usar el SO, el IDE, compilar/ejecutar/depurar.
  • Formal methods ✓nd: razonar sobre correctitud y eficiencia, pre/post condiciones, invariantes.