Plan formativo autodidacta
¡Aprende!
En la tabla que sigue aparece la temática (desde el punto de vista de programación) de cada uno de los problemas. Te animamos a que los revises para ver si en alguno de ellos necesitas algo de refuerzo y te anticipes preparando los temas de programación que no conozcas.
Atención: la categoría de los problemas no es definitiva y podría sufrir ligeros cambios, por lo que revísala de vez en cuando.
Ten en cuenta que las categorías no son excluyentes. En general, en cualquier problema se pueden necesitar conceptos puestos a prueba en días anteriores. Además a menudo un problema puede resolverse utilizando diferentes técnicas por lo que podrían admitirse soluciones que no hagan uso de la categoría que indicamos.
Detalles de cada categoría
Llamamos problemas ad-hoc a aquellos que resultan dificiles de clasificar en otras categorías porque no están asociados a ningún algoritmo o estructura de datos concreta.
Para resolverlos normalmente hay que usar las construcciones básicas del lenguaje (expresiones, condicionales, bucles, arrays, etc.) y pensar en un algoritmo específico para el problema que difícilmente será aprovechable para otros.
La forma de prepararse para estos problemas, pues, es practicar con el lenguaje de programación elegido y enfrentarte a otros problemas ad-hoc para coger habilidad inventando algoritmos particulares. Muchos problemas ad-hoc son sencillos, aunque en algunos es difícil llegar al algoritmo escondido.
Aquí te dejamos una pequeña lista de problemas del estilo para que puedas practicar:
Las estructuras de datos son distintas formas de organizar la información junto con las operaciones que pueden realizarse sobre ellas. Existen numerosas estructuras de datos y libros sobre ellas (ver [1], por ejemplo) y es difícil encontrar problemas que no las utilicen en mayor o menor medida. En esta categoría, no obstante, colocamos problemas que utilizan estructuras de datos que suelen estar disponibles en las bibliotecas de los lenguajes de programación (como pilas, listas, colas, conjuntos, etc.) y en donde los algoritmos que resuelven el problema son muchas veces ad-hoc, diseñados específicamente para ese problema.
Puedes conocer más sobre estas estructuras de datos en los capítulos 3, 4, 5 y 7 de [2]. No olvides consultar, además, la documentación de la biblioteca del lenguaje de programación que utilices.
Aquí te dejamos una lista de problemas del estilo para que puedas practicar:
El campo de las matemáticas es tan amplio que una única categoría para todos los problemas matemáticos es demasiado poco. Incluimos aquí problemas que tienen que ver con números primos y criba de Eratóstenes, mcd, mcm, secuencias, progresiones, números triangulares, mallados, probabilidad, ... También caen aquí problemas más sencillos de extracción de dígitos o cambio de base.
Por dar algunos recursos, puedes leer sobre el algoritmo de Euclides o la criba de Eratóstenes. También puedes consultar el capítulo 5 de [4] dedicado por entero a este tipo de problemas.
Aquí te dejamos una lista de problemas del estilo para que puedas practicar:
- 190 - Dividir factoriales
- 226 - Reescribiendo fracciones
- 272 - Tres dedos en cada mano
- 335 - Pirámides de canicas
- 414 - Conseguir un cuadrado perfecto
- 500 - Votaciones capicúa
- 613 - Unos
- 722 - Tú uno y yo dos
Ten en cuenta que hay problemas matemáticos que podrían caer en
otras categorías (por ejemplo aspectos relacionados con teoría de grafos
estarían dentro de
En los cursos de programación se suele entender como recorrido el procesar todos los elementos de un vector para hacer algún cálculo (como obtener la suma completa) y la búsqueda como un recorrido que termina cuando el algoritmo encuentra en el vector lo que estaba buscando.
En esta categoría, no obstante, entran también recorridos y búsquedas más sofisticadas, como recorridos con ventana deslizante, con acumuladores o desde los lados hacia el centro, que consiguen algoritmos de complejidad lineal en lugar de complejidades cuadráticas o peores. Una explicación sobre este tipo de problemas se encuentra, por ejemplo, en el capítulo 4 de [5].
Aquí te dejamos una lista de problemas del estilo para que puedas practicar:
Este tipo de problema no suele aparecer en concursos presenciales, pero sí en concursos celebrados sobre ¡Acepta el reto!.
Al contrario de lo que ocurre con muchas otras categorías que juegan
con restricciones de tiempo que obligan a pensar en algoritmos rápidos
(por ejemplo el problema 242 - Erasmús tiene una solución
obvia cuadrática que da Time-limit y hay que buscar una solución lineal
mucho más rápida), en esta categoría se persiguen algoritmos eficientes
en consumo de memoria.
En los problemas de esta categoría el algoritmo suele ser muy fácil de
ver y consiste, en la mayoría de las ocasiones, en almacenar los datos de
entrada en un vector y recorrerlo. Pero las restricciones de memoria
impuesta por los autores impide ese almacenamiento de forma que el
algoritmo tiene que ser capaz de calcular la respuesta calculandola
al vuelo
, según se va leyendo la entrada.
Aquí te dejamos una pequeña lista de problemas del estilo para que puedas practicar:
En esta categoría encontramos problemas cuya resolución pasa por implementar algoritmos recursivos (aunque podrían quizá resolverse de otra forma).
La recursión aparece en otras muchas categorías. Sin ir más lejos
muchos conceptos necesarios para resolver
Puedes encontrar una introducción relámpago a la recursión aquí. Para un análisis más pausado puedes ver el capítulo 5 de [5]. Dado que el esquema algorítmico de divide y vencerás suele implementarse recursivamente, también puedes revisar el capítulo 11 de [2].
Lo mejor para interiorizar la recursión es hacer problemas. Aquí tienes una buena lista para practicar (la lista ha sido seleccionada de forma que evita tocar las categorías que mencionábamos antes):
Aunque las cadenas no dejan de ser vectores de caracteres que pueden ser fuente de problemas de recorridos, búsquedas o recursivos igual que lo pueden ser los vectores de números, las cadenas suelen dar lugar a otro tipo de problemas que requieren algoritmos especializados. Muchos de estos problemas se resuelven utilizando estructuras de datos especializadas (como los tries) o algoritmos de programación dinámica clásica como la distancia de edición. También existen muchos algoritmos para buscar cadenas dentro de cadenas de forma eficiente, como KMP.
En esta categoría, además, aparecen problemas de cadenas más sencillos que se resuelven con algoritmos ad-hoc.
Puedes consultar el capitulo 6 de [4] para más detalles.
Aquí te dejamos una pequeña lista de problemas del estilo para que puedas practicar:
Los algoritmos voraces resuelven problemas de optimización en los que para llegar a la solución final, en cada toma de decisiones eligen la opción que, en ese momento, parece más razonable. Aunque esto dicho así parece que es algo que siempre debería hacerse, la realidad es que utilizar la estrategia voraz no siempre funciona: en una encrucijada en un laberinto puede que sea mejor ir al sur aunque aparentemente eso nos aleje del centro del laberinto al que queremos ir.
Por tanto una de las primeras tareas que se debe hacer para afrontar uno de estos problemas es analizar si la estrategia voraz funcionará en ese caso. Y una de las tareas del autor del problema será enmarañar el enunciado para que parezca que esa estrategia voraz no funcionará, pues lo habitual es que, una vez identificado, el algoritmo voraz sea muy rápido de escribir.
Para identificar problemas voraces lo mejor es conocer cómo abordar la demostración de que la estrategia voraz funciona y conocer ejemplos clásicos de estos algoritmos. Puedes ver más detalles en el capítulo 12 de [2] o en la sección 3.4 de [3].
Algunos ejemplo de problemas con los que practicar son:
Los problemas en esta categoría consisten normalmente en buscar una solución construida a base de pasos para resolver un problema concreto. La fuerza bruta (o búsqueda exhaustiva) analiza todas las posibles soluciones (que suelen ser muchas) mientras que la vuelta atrás organiza el espacio de posibles soluciones de tal manera que sea posible descartar de golpe conjuntos de ellas.
Uno de los ejemplos de vuelta atrás más utilizado es el de las N reinas que puedes explorar, por ejemplo aquí. Problemas de esta categoría aparecen de vez en cuando en concursos internacionales (aquí hay dos ejemplos). Puedes aprender más sobre estos algoritmos en el capítulo 14 de [2].
Aquí te dejamos una lista de problemas del estilo para que puedas practicar:
La primera aproximación que suele hacerse a la búsqueda binaria es la que permite buscar eficientemente un valor en un vector ordenado. Sin embargo esa misma idea (si lo buscado es mayor que la consulta, pregunto por un número más grande, si no por uno más pequeño) se puede utilizar también para otras cosas. En concursos de programación la búsqueda binaria es especialmente útil para buscar la propia solución (¿cómo resolverías una raíz cuadrada sin calculadora? ¡tanteando para buscar la solución!).
Lo difícil de los problemas de búsqueda binaria de la solución suele ser...
darse cuenta de que lo que hay que hacer es buscar la solución. Eso significa
que la lista siguiente con este tipo de problemas hace que automáticamente
pierdan un poco la gracia
pues la implementación, una vez que se sabe
que lo que hay que hacer, suele ser sencilla. Por eso hemos añadido en la lista
algún problema que no pertenece a la categoría 😜:
La programación dinámica es adecuada, por ejemplo, para problemas de optimización y de conteo que no pueden resolverse con algoritmos voraces y que pueden mejorar las implementaciones recursivas mediante el uso de memoria adicional.
Existen muchos ejemplos clásicos de programación dinámica como el problema de la mochila, subsecuencia común más larga (LCS) o cambio de monedas.
Pero la programación dinámica no se queda ahí y una de las claves para poder resolver estos problemas es ser capaces de ver la recurrencia que se esconde detrás del problema y ver cómo se puede trasladar a tablas. Puedes ver aquí el desarrollo de uno de esos problemas.
Si quieres profundizar más puedes consultar el capítulo 13 de [2] o el apartado 3.5 de [3]. Además, hay problemas que normalmente se ubican en otras categorías que se resuelven utilizando programación dinámica, como algunos de cadenas (distancia de edición), matemáticas (series de Fibonacci, por ejemplo), recorridos de grafos dirigidos acíclicos y otros.
Algunos problemas de programación dinámica que puedes intentar son:
Un árbol de segmentos (o segment tree) es una estructura de datos que almacena los valores de un vector de forma que es rápido hacer consultas y actualizaciones de sus valores.
A pesar de su utilidad, no es habitual que las librerías de los lenguajes tengan este tipo de árboles por lo que cuando son necesarios en un concurso hay que implementarlos desde cero. Su implementación es recursiva y, en caso de permitirse en la competición, suele encontrarse en el chuletario de los equipos.
Puedes ver una explicación de la estructura con un montón de enlaces a problemas que se resuelven con ella aquí. Si prefieres material en español, esta es otra alternativa. También aparece una descripción en la sección 2.4.4 de [3].
Los grafos son una constante en los concursos universitarios y de olimpiadas de informática. Es extremadamente extraño que no haya al menos un problema que caiga en esta categoría.
Metemos en esta categoría tanto problemas de recorridos de grafos (BFS, DFS) como de búsqueda de caminos mínimos ya sea en grafos no valoradors (BFS) como valorados (Dijkstra, Bellam-Ford, Floyd-Warhsall).
Puedes encontrar una introducción a grafos en el capítulo 9 de [2] y explicaciones mucho más extensas en el capítulo 4 de [3].
Aquí te dejamos una lista de problemas del estilo para que puedas practicar:
Bajo este nombre, que resulta tan extraño la primera vez que se ve, se ocultan problemas que suelen tener ambientaciones muy atrayentes en los concursos. Suelen tratarse de problemas de emparejamiento en los que se tiene que, por ejemplo, encontrar una asignación entre dos tipos de entidades. Por ejemplo asignar una camiseta de la colección a cada participante que sea de alguna de las tallas que le quedan bien.
Estos problemas, que parecen de vuelta atrás, se pueden traducir en un grafo bipartito en donde unos vértices representan uno de los tipos de entidades (camisetas) y otros el otro tipo (participantes) con aristas uniendo los vértices compatibles. De ahí el nombre de matching (o emparejamiento) bipartito (= en grafos bipartitos).
Puedes ver una descripción más extensa junto con un algoritmo que lo resuelve aquí. También puedes ver la descripción de un algoritmo más eficiente aquí.
Explicado rápidamente, el problema del max flow (o flujo máximo) consiste en hacer pasar por una red de tuberías con distinta capacidad la mayor cantidad de agua desde un punto a otro. Bajo esta intuición visual se ocultan muchas veces problemas que no parecen relacionados con tuberías, agua, ni grafos (ver por ejemplo 566 - La abuelita caperucita).
El max flow, que puede verse como una generalización del matching bipartito, es un problema muy estudiado (con libros dedicados íntegramente a él, como [7]) y puede resolverse en tiempo polinómico con un gran número de algoritmos. Puedes ver una introducción en esta página junto con enlaces a algoritmos que lo resuelven.
Aunque la geometría es un área de las
El área es tan grande que hay libros enteros dedicados al tema (como [6]), con multitud de estructuras de datos y algoritmos especializados. En los concursos los problemas de geometría suelen implicar ser capaces de calcular áreas, intersecciones, distancias y trabajar con segmentos, rectas, puntos, círculos y polígonos. En ocasiones los problemas no son específicos de esta categoría sino que incluyen, además, otras.
Dado que implica conocer un gran número de fórmulas, lo habitual es que, si el concurso lo permite, el chuletario de los equipos dedice una parte no despreciable de su espacio a esta categoría. Un algoritmo que nunca debe faltar es el del convex hull.
Puedes ver una introducción rápida a algunas de esas fórmulas y algoritmos aquí o consultar más detalles en el capítulo 7 de [4].
Aquí te dejamos una pequeña lista de problemas del estilo para que puedas practicar:
Muchas veces es difícil colocar un problema en una categoría; algunas veces es porque puede resolverse utilizando varias aproximaciones (por ejemplo, con programación dinámica o con grafos, como 398 - Más listos que el hambre), y otras porque requieren poner en práctica varias (como 326 - La ardilla viajera o 391 - El profesor de música).
En esta categoría colocamos esos problemas diseñados específicamente para tocar varios temas.
Referencias
| [1] | Handbook of data structures and applications. Dinesh P Mehta, Sartaj Sahni, Dinesh P Mehta, Sartaj Sahni. Chapman & Hall/CRC, cop. 2005. |
|---|---|
| [2] | Estructuras de datos y métodos algorítmicos : 213 ejercicios resueltos. Narciso Martí Oliet, Yolanda Ortega Mallén y José Alberto Verdejo López. Garceta, 2013. |
| [3] | Programación Competitiva 4, Manual para concursantes del ICPC y la IOI. Volumen I. Steven Halim, Felix Halim y Suhendry Effendy. OJBooks, 2021. |
| [4] | Programación Competitiva 4, Manual para concursantes del ICPC y la IOI. Volumen II. Steven Halim, Felix Halim y Suhendry Effendy. OJBooks, 2021. |
| [5] | Algoritmos correctos y eficientes Diseño razonado ilustrado con ejemplos. Narciso Martí Oliet, Clara Segura y Alberto Verdejo. Garceta, 2012. |
| [6] | Computational Geometry. Algorithms and Applications. Mark de Berg, Otfried Cheong, Marc van Kreveld y Mark Overmars. Springer, 2008. |
| [7] | Network Flows: Theory, Algorithms, and Applications. Ravindra Ahuja, Thomas Magnanti y James Orlin. Pearson, 1993 |