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.
| Problema | Competencia | Dificultad |
|---|---|---|
| La gran fila | 2016 Clasificatoria | 🟢 fácil |
| Cubiertos | 2017 Regional | 🟢 fácil |
| Reacciones | 2022 Nacional | 🟢 fácil |
| ¿Cuántas poleras de cada talla? | 2025 Nacional | 🟢 fácil |
| Parejas para el tango | 2015 Regional | 🟡 media |
| Papas fritas | 2023 Regional | 🟡 media |
| Reuniones | 2019 Regional | 🟡 media |
| Empacadora de supermercado | 2020 Regional | 🟡 media |
| Pájaros furiosos | 2022 Regional | 🟡 media |
| Cola | 2025 Regional | 🟡 media |
| La torre de la maldad | 2021 Nacional | 🔴 difícil |
| Poleras | 2023 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.
| Problema | Año | Media (puntos parciales) | Lograron 100 |
|---|---|---|---|
| Arranging Shoes | 2019 | 74/100 | 52% |
| Nile | 2024 | 68/100 | 35% |
| Detecting Molecules | 2016 | 66/100 | 51% |
| Souvenirs | 2025 | 46/100 | 16% |
| Overtaking | 2023 | 45/100 | 8% |
| Boxes with souvenirs | 2015 | 44/100 | 30% |
| Nowruz | 2017 | 34/100 | 0% |
| Festival | 2025 | 32/100 | 4% |
| Carnival Tickets | 2020 | 30/100 | 11% |
| Wiring | 2017 | 26/100 | 14% |
| Ancient Books | 2017 | 26/100 | 5% |
| Roller Coaster Railroad | 2016 | 26/100 | 1% |
| Closing Time | 2023 | 23/100 | 3% |
| Teams | 2015 | 23/100 | 4% |
| Monuments | 2026 | 20/100 | <1% |
| Radio Towers | 2022 | 19/100 | 2% |
| Shortcut | 2016 | 18/100 | <1% |
| Partition | 2026 | 18/100 | 2% |
| Comparing Plants | 2020 | 15/100 | 3% |
| Hieroglyphs | 2024 | 5/100 | <1% |