Programación Competitiva
Algunos ejercicios de programación competitiva resueltos en Python y C++. Además de recursos y tips para poder resolverlos.
¿Por qué Python y C++?
La competencia oficial de ICPC Chile se permiten las siguientes alternativas: C, C++, Java, Python, Kotlin.
Las alternativas de Java y Kotlin tienden a ser más veloces que Python, sin embargo requieren de más escritura de código, además de uso de orientación a objetos, lo cual puede complicar ciertas soluciones.
Python puede ser usado como pseudocódigo y poder elaborar una solución inicial en papel o lenguaje de prototipado rápido. Puede ser usado para entregar la solución final, pero no hay garantías de que la solución esté dentro de las restricciones de tiempo y memoria, como lo son Java y C++.
C es el lenguaje más apropiado para entregar las soluciones finales y cumplir tanto con las restricciones de tiempo y memoria. También podría ser C, pero C ofrece bibliotecas adicionales que facilitarían la obtención de las soluciones.
¿Por qué practicar programación competitiva?
Principalmente por que ayudan en el desarrollo de la lógica y matemática y permiten practicar para ejercicios de entrevistas laborales.
Finalmente por que aprender de algoritmos, estructuras de datos y lógica matemática son conceptos fundamentales para todo adepto a la informática.
Dificultades
Los problemas se pueden clasificar según su dificultad. Para facilitar la interpretación se asociaron emojis según la dificultad.
| Emoji | Dificultad | Interpretación |
|---|---|---|
🍰 |
0 - 800 |
Ejercicios de dificultad baja. |
🤓 |
900 - 1800 |
Ejercicios de dificultad mediana. |
🤯 |
1900 - 2900 |
Ejercicios de dificultad alta. |
☠️ |
3000 - 3400 |
Ejercicios de dificultad extrema. |
👹 |
3500+ |
Ejercicios de dificultad demoniaca. |
| Tags | Interpretación |
|---|---|
math, combinatorics, number theory |
El ejercicio puede ser resuelto usando fórmulas matemáticas, lógica, teoría de números o estadísticas. |
binary search |
El ejercicio puede ser resuelto usando búsqueda binaria en la respuesta. |
brute force |
El ejercicio puede ser resuelto con fuerza bruta (considerando todos los posibles casos). |
greedy |
El ejercicio puede ser resuelto con estrategias greedy. |
implementation |
El ejercicio es simple de entender y resolver. Pero dentro de la implementacion esta el desafio (puede haber casos borde o gran cantidad de datos). |
Recursos
-
Code Forces. Principal fuente de problemas y evaluador de soluciones.
-
Libro Grokking Algorithms (ISBN: 9781633438538). Libro con información valiosa para entender algoritmos y estructuras de datos.
-
One Compiler. Permite compilar código en Python y C++ de forma online y rápida.
Requisitos ICPC
Para los universitarios que deseen participar en las competencias de la ICPC Chile tienen que tener máximo 23 años y máximo cinco años de carrera cursados.
Normalmente la competencia de clasificación al mundial se hace en Noviembre, con un pequeño torneo de preparación en Octubre.