Greedy

Estrategias voraces y exchange arguments.

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

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

📋 En el temario OCI: el temario no lo nombra como tópico, pero exige sort con comparador propio (⊖) y los problemas regionales lo usan todo el tiempo.

Una estrategia voraz decide en cada paso lo que se ve mejor ahora y nunca se arrepiente. Cuando funciona es la solución más corta que existe — y el trabajo de verdad no es encontrarla, sino demostrar que funciona.

📌 Qué abarca

  • Algoritmos voraces; greedy con ordenamiento; greedy + estructura (heap/cola de prioridad).
  • Exchange arguments (argumento de intercambio) para probar optimalidad.
  • Patrones que aparecen una y otra vez: ordenar por hora de término (máximo de actividades sin traslape), emparejar extremos con dos punteros, atender al más urgente con una cola de prioridad, y ordenar por una razón (peso/valor, tiempo/beneficio).
  • Se aprende con demostración en 23 - Greedy demostrable.

⛔ Fuera del syllabus IOI

  • El greedy no tiene exclusiones propias: en el syllabus ni siquiera es un ítem aparte, entra por las técnicas de prueba. Eso mismo lo dice todo — lo que se evalúa no es conocer greedys, sino demostrar el que se te ocurrió.

🎯 En competencia

En la OCI — Es la técnica más común de la fase Regional aunque el temario no la nombre: ordenar y tomar lo mejor disponible. El problema típico se resuelve con un sort y un recorrido; la dificultad está en convencerse de que el greedy es correcto. En este vault hay 12 problemas OCI del tema (8 de fases regionales, 3 de fases nacionales y 1 de clasificatorias IOI); están en la tabla de abajo.

En la IOI — Muchos problemas Constructivos y Ad-hoc tienen núcleo greedy. El riesgo es asumir un greedy sin probarlo: busca siempre el contraejemplo o el argumento de intercambio antes de confiar en él.

⚠️ La trampa típica

Confiar en un greedy que parece obvio. Antes de enviarlo, testéalo contra una fuerza bruta en casos chicos: es el WA más caro de la competencia, porque el código se ve bien y no sabes dónde mirar.

⚙️ 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
La gran fila2016 Clasificatoria🟢 fácil
Cubiertos2017 Regional🟢 fácil
Reacciones2022 Nacional🟢 fácil
¿Cuántas poleras de cada talla?2025 Nacional🟢 fácil
Parejas para el tango2015 Regional🟡 media
Papas fritas2023 Regional🟡 media
Reuniones2019 Regional🟡 media
Empacadora de supermercado2020 Regional🟡 media
Pájaros furiosos2022 Regional🟡 media
Cola2025 Regional🟡 media
La torre de la maldad2021 Nacional🔴 difícil
Poleras2023 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
Arranging Shoes201974/10052%
Nile202468/10035%
Detecting Molecules201666/10051%
Souvenirs202546/10016%
Overtaking202345/1008%
Boxes with souvenirs201544/10030%
Nowruz201734/1000%
Festival202532/1004%
Carnival Tickets202030/10011%
Wiring201726/10014%
Ancient Books201726/1005%
Roller Coaster Railroad201626/1001%
Closing Time202323/1003%
Teams201523/1004%
Monuments202620/100<1%
Radio Towers202219/1002%
Shortcut201618/100<1%
Partition202618/1002%
Comparing Plants202015/1003%
Hieroglyphs20245/100<1%