Resumen del entrenamiento

El entrenamiento está dividido en 11 sesiones que puedes ver en la tabla derecha. Cada sesión tiene una duración de dos semanas; en la tabla aparece la fecha de comienzo. Las sesiones que no han comenzado aún aparecen en negro. Las ya empezadas (incluidas las terminadas) aparecen en azul y el enlace lleva a la información de la sesión. A esa misma información puedes acceder pulsando sobre su pestaña en la parte superior.

Primera sesión de la serie de entrenamientos.

Esta primera sesión está dedicada a la resolución de problemas interactivos. En la mayoría de problemas de programación competitiva, tu programa tiene a su disposición todos los datos de entrada y la dificultad está en procesar esos datos eficientemente para finalmente imprimir la salida correcta. En los problemas interactivos, el planteamiento cambia un poco: tu programa no dispone de toda la información inicialmente, sino que debe interactuar con el juez para ir obteniendo la información necesaria. Este tipo de problemas no aparece en muchos concursos de programación, pero tanto en la OIE como sobre todo en la IOI sí aparecen, por tanto inauguramos esta serie de entrenamientos con una sesión dedicada a la resolución de estos problemas para familiarizarnos con ellos.

• Enunciados de los problemas en castellano.
• Documento explicativo sobre problemas interactivos que usan graders y entrada y salida estándar. (Usado en los entrenamientos de 2021; no es correcto lo que dice de que todos los problemas de esta semana usan graders ya que este año hay de los dos tipos mezclados)
• Graders para los problemas Combo y Messy. (Atención: el código que enviéis al juez en Messy debe retornar int[]).

• Las soluciones de los problemas Factorial, Caballeros y XOR se pueden encontrar en el canal de YouTube de la OIE.
• Soluciones al resto de problemas.

Segunda sesión de la serie de entrenamientos.

Esta segunda sesión está dedicada a la resolución de problemas constructivos. Estos son problemas en los que te piden construir un determinado objeto que satisfaga una serie de propiedades.

• Enunciados de los problemas en castellano.

• Las solución al problema Atrapasueños se puede encontrar en el canal de YouTube de la OIE.
• Soluciones al resto de problemas..

Tercera sesión de la serie de entrenamientos.

Esta tercera sesión está dedicada a problemas que requieren calcular eficientemente el ancestro común más bajo de dos vértices en un árbol enraizado.

• Manual Aprende OIE con la teoría.
• Enunciados de los problemas en castellano.
• Soluciones de los problemas en castellano.

Cuarta sesión de la serie de entrenamientos.

Esta sesión trata sobre dos técnicas para resolver problemas sobre árboles: Heavy-Light Decomposition y Centroid Decomposition.

• Manual Aprende OIE de HLD.
• Manual Aprende OIE de CD.
• Soluciones a los problemas.

Quinta sesión de la serie de entrenamientos.

En esta sesión trabajamos con algunos pequeños "trucos" que permiten mejorar la complejidad de nuestras soluciones a problemas de programación dinámica.

• Enunciados de los problemas en castellano.
• Manual SOS DP.
• Manual Optimizaciones DP.
• Soluciones a todos los problemas.

Sexta sesión de la serie de entrenamientos.

Este entrenamiento va sobre algoritmos sobre grafos. Los problemas principalmente están centrados en estos dos temas: componentes fuertemente conexas y emparejamiento máximo en un grafo bipartito.

• Manual árbol DFS.
• Manual componentes fuertemente conexas.
• Manual de emparejamiento máximo en grafos bipartitos.
• Soluciones a los problemas.

Séptima sesión de la serie de entrenamientos.

• Manual sobre SQRT decomposition.
• Soluciones a todos los problemas.

Octava sesión de la serie de entrenamientos.

Esta sesión combina problemas que usan 2 estructuras de datos: BBSTs y tries

Los árboles binarios balanceados de búsqueda (BBST) son una estructura de datos básica. Aunque en la librería estándar de C++ ya hay una implementación con la funcionalidad más importante (std::set, y en el caso de los compiladores de GNU hay una implementación con funcionalidad extendida en los policy based data structures), a veces hay que implementarlo por nuestra cuenta para que soporte las operaciones que queremos. En programación competitiva, entre los diferentes tipos de BBST que existen, se suele preferir el treap, por su facilidad de implementación y la gran variedad de operaciones que permite realizar.

Los tries son estructuras de datos muy sencillas que se suelen usar principalmente en problemas de procesamiento de cadenas, pero también aparecen en otros contextos y con un poco de creatividad se pueden aplicar de forma muy poderosa.

• Manual sobre Treaps.
• Manual sobre Tries.

Novena sesión de la serie de entrenamientos.

En esta sesión no hay manuales; es una de las sesiones puramente de resolución de problemas.

Décima sesión de la serie de entrenamientos.

Esta sesión trata sobre Geometría Computacional.

• Manual de la sesión.

Undécima sesión de la serie de entrenamientos.

Esta sesión trata sobre temas avanzados de estructuras de datos.

• Manual de conectividad dinámica.
• Manual de árboles de segmentos persistentes.
• Manual de árbol de Li Chao.