Constructivos y Ad-hoc

Construir una salida válida; ideas a la medida.

Volver a los 11 temas · Referencia · temarios: Syllabus OCI · Syllabus IOI.

📍 Clases relacionadas: módulos 13 de la Ruta de Aprendizaje.

📋 En el temario OCI: en todas las fases: es lo que más sale, porque el temario regional es corto y los problemas viven de la idea, no del algoritmo.

Problemas que no se resuelven aplicando un algoritmo conocido, sino encontrando la idea propia de ese problema — muchas veces, construir una salida válida cualquiera en vez de buscar la óptima.

📌 Qué abarca

  • Estrategias de resolución: entender–planear–hacer–verificar, distinción de casos, generalización/especialización, trabajar hacia atrás.
  • Fuerza bruta exhaustiva; backtracking; branch & bound.
  • Construir una salida válida que cumpla las restricciones (a menudo con un invariante o una idea a la medida).
  • Cómo reconocerlos: N sorprendentemente chico sin que se vea un patrón; el enunciado pide cualquier salida válida y no la óptima; o el problema no calza con ningún algoritmo conocido por más vueltas que le des. Eso último no es señal de que te falte teoría: es la señal de que es ad-hoc.

⛔ Fuera del syllabus IOI

  • No tiene exclusiones: un problema ad-hoc puede tocar incluso un tema “fuera de foco” si se resuelve sin conocimiento previo de ese tema.

🎯 En competencia

En la OCI — Es lo que más sale en todas las fases. Simular, buscar un patrón, probar todos los casos chicos: esa es la habilidad que la Regional mide de verdad, y la razón de que la ruta insista tanto en resolver a mano antes de programar. En este vault hay 39 problemas OCI del tema (21 de fases regionales, 15 de fases nacionales y 3 de clasificatorias IOI); están en la tabla de abajo.

En la IOI — Aquí caen los problemas “raros” sin algoritmo de libro. La fuerza bruta asegura las subtareas chicas mientras buscas el patrón/invariante para la general.

⚠️ La trampa típica

Empezar a programar antes de leer todas las subtareas. En este tema, más que en ningún otro, las subtareas chicas se resuelven con una idea distinta —y mucho más simple— que la general.

⚙️ Algoritmos y técnicas

🇨🇱 Problemas OCI (en español)

Empieza por acá: son problemas oficiales chilenos, con enunciado en español y mirror para enviar. Consulta la orientación de estudio al comienzo de esta página. La dificultad orienta la elección, pero no garantiza una solución completa.

ProblemaCompetenciaDificultad
Partido de ping-pong2015 Nacional🟢 fácil
La gran fila2016 Clasificatoria🟢 fácil
Organizador de canciones inteligente2016 Regional🟢 fácil
Ataque2016 Nacional🟢 fácil
La calculadora del almacén2017 Regional🟢 fácil
La tarea de matemática2017 Nacional🟢 fácil
Bus de turismo2018 Regional🟢 fácil
El juego del OCIo2018 Regional🟢 fácil
Azulejos2019 Regional🟢 fácil
Llaves2020 Regional🟢 fácil
Torneo de ajedrez2020 Nacional🟢 fácil
Tormenta China2021 Regional🟢 fácil
Ocilandia2021 Nacional🟢 fácil
Reacciones2022 Nacional🟢 fácil
Rey De Los Piratas2023 Regional🟢 fácil
Dados de Rol2023 Nacional🟢 fácil
Cachipun2023 Nacional🟢 fácil
Ricardo y su nóctulo2024 Regional🟢 fácil
Cuenta de goles2025 Regional🟢 fácil
Carta de navegación2025 Nacional🟢 fácil
Olonso y los laberintos2015 Regional🟡 media
Colección de láminas2015 Regional🟡 media
Lokómon GO2016 Regional🟡 media
El malvado profesor Moriarki2016 Regional🟡 media
Escaleras y Serpientes2018 Nacional🟡 media
El juego del calendario2021 Regional🟡 media
Contraseña2022 Regional🟡 media
El lokómon de Olivier2022 Regional🟡 media
Ajedrez2015 Nacional🟡 media
Las sumas de Gabriela2018 Regional🟡 media
Cubos de papel2019 Nacional🟡 media
Cámaras2025 Regional🟡 media
Varita mágica2017 Nacional🔴 difícil
Jaque mate2020 Regional🔴 difícil
Cuatro en línea2022 Nacional🔴 difícil
Figuras2023 Nacional🔴 difícil
Dominó2016 Clasificatoria🔴 difícil
El camino del dragón2016 Clasificatoria🔴 difícil
El lokómon legendario2020 Regional🔴 difícil

🌍 Problemas IOI

De más abordable a más duro, según el puntaje promedio que sacaron los competidores: una media alta sugiere más puntos parciales accesibles, no más soluciones completas. Consulta también el porcentaje de 100 y los prerrequisitos.

ProblemaAñoMedia (puntos parciales)Lograron 100
Connecting Supertrees202078/10044%
Combo201874/10055%
Tiling Game202673/10065%
Detecting Molecules201666/10051%
The Big Prize201754/1009%
Vision Program201953/10014%
Stations202051/10026%
Counting Mushrooms202050/100<1%
World Map202548/1004%
Sorting201547/10018%
Souvenirs202546/10016%
Triple Peaks202543/100<1%
Unscrambling a Messy Bug201642/10020%
Broken Line201941/1000%
Prisoner Challenge202238/1002%
Scales201538/1003%
Message202437/100<1%
Classroom Game202637/1000%
Sphinx’s Riddle202435/1002%
Nowruz201734/1000%
Longest Trip202334/1003%
Magic City202634/1001%
Mechanical Doll201832/10011%
Ball Machine202630/1001%
Carnival Tickets202030/10011%
Fountain Parks202130/1003%
Thousands Islands202229/1002%
Split the Attractions201927/1002%
Ancient Books201726/1005%
Robot Contest202326/1000%
Soccer Stadium202323/100<1%
Bit Shift Registers202117/1002%
Beech Tree202315/100<1%
Comparing Plants202015/1003%
Towns201514/1002%