Entrenamiento OIE 2023 - Nivel inicial

Bienvenido al entrenamiento de la OIE'2023 enfocado a aquellos que están dando sus primeros pasos en la programación y la algoritmia.

El entrenamiento está organizado sobre el juez on-line Acepta el reto. Si quieres participar, necesitarás crearte un usuario en el juez (si tienes ya uno, puedes utilizar ese) y registrarte aquí.

El entrenamiento está dividido en once sesiones de dos semanas de duración, que comienzan los lunes a las 9:00. Durante cada sesión se espera que los participantes revisen los contenidos enlazados de esa sesión e intenten los problemas propuestos. Las dudas que puedan surgir pueden hacerse usando el discord de la OIE. Cuando terminan las dos semanas, además de comenzar la sesión siguiente, se publican algunas explicaciones sobre los problemas de la sesión para que aquellos que no los hayan conseguido resolver puedan seguir intentándolo.

Resumen
Sesión Fecha de inicio
#13 de octubre
#217 de octubre
#331 de octubre
#414 de noviembre
#528 de noviembre
#612 de diciembre
#79 de enero
#823 de enero
#96 de febrero
#1020 de febrero
#116 de marzo

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.

En la pestaña de cada sesión puedes ver la lista de los ejercicios de ¡Acepta el Reto! de esa sesión así como quiénes han hecho envíos a ellos en el periodo establecido y una clasificación. El orden en la clasificación de cada sesión viene dado por el número de problemas resueltos y, en caso de empate, por la suma de los tiempos invertidos en hacer cada uno más una penalización de 20 minutos por cada envío incorrecto.

En esta pestaña resumen puedes ver una clasificación general en la que aparece el número de problemas resueltos en cada sesión por los participantes. En este caso no hay criterio de desempate, por lo que dos participantes con el mismo número de problemas resueltos aparecerán en orden arbitrario.

En las clasificaciones aparecen en rojo los nombres de los participantes y en negro los envíos realizados por los profesores responsables del entrenamiento. No te extrañe si hay pocos envíos suyos, los problemas los resolvieron hace mucho ;)

Clasificación general

La tabla que aparece a continuación condensa el número total de problemas resueltos de cada sesión por cada participante.

#1

Primera sesión de la serie de entrenamiento.

El objetivo de estas dos semanas es que rompas el hielo con la programación y el lenguaje C++, y aprendas a utilizar las herramientas básicas que necesitarás para resolver los problemas propuestos. Si eres nuevo, te proponemos algo de lectura para empezar:

En la lista de la derecha tienes los problemas que te proponemos que resuelvas para esta sesión. Son problemas que están disponibles en la web Acepta el reto, y es donde tendrás que enviar tus soluciones. Si nunca has usado la plataforma, aquí te ayudamos a resolver tu primer problema. También tienes algo de ayuda adicional (que puede venirte bien más adelante) aquí.

Los envíos que hagas dentro del plazo a Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.

Esta sesión de entramiento ya ha terminado. Si te quedaste con dudas, puedes consultar la explicación de las soluciones de los problemas.

#2

Segunda sesión de la serie de entrenamiento.

En esta sesión vamos a practicar los condicionales y los operadores relacionales y booleanos. Ten en cuenta que en cada sesión se asume que se entienden bien los conceptos de las sesiones previas, por lo que seguirás teniendo que usar variables, expresiones y entrada/salida, que aprendiste en la sesión anterior.

Si quieres aprender sobre los temas de esta sesión, te proponemos algo de lectura:

Los envíos que hagas a Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.

Esta sesión de entramiento ya ha terminado. Si te quedaste con dudas, puedes consultar la explicación de las soluciones de los problemas.

#3

Tercera sesión de la serie de entrenamiento.

En esta sesión vamos a practicar los bucles (for, while y do-while). También vamos a aprovechar para introducir el concepto de función. Ambas cosas, en conjunto, deberían permitirte comprender las plantillas que has estado utilizando en las dos sesiones anteriores para resolver los problemas.

Ten en cuenta que en cada sesión se asume que se entienden bien los conceptos de las sesiones previas, por lo que seguirás teniendo que usar variables, expresiones, condicionales y entrada/salida, que aprendiste en las sesiones anteriores.

Si quieres aprender sobre los temas de esta sesión, te proponemos algo de lectura:

  • Transparencias de Fundamentos de la programación de Luis Hernández Yañez, de la Universidad Complutense de Madrid:
    • Tipos e instrucciones I:
      • Bucles while's: transparencias 186-189 (páginas 139-142 del PDF)
      • Funciones: transparencias 199-210 (páginas 152-163 del PDF)
    • Tipos e instrucciones II:
      • Repetición: más sobre while's, for, do-while: transparencias 313-330 (páginas 89-106 del PDF)
      • Ámbito y visibilidad; secuencias: transparencias 339-373 (páginas 115-149 del PDF)
    • Abstracción prodecimental: más sobre funciones
  • Material de la OIE
    • Bucles while
    • Funciones
    • Bucles for: se mencionan ejemplos donde se usan vectores y arrays que todavía no hemos aprendido; no te preocupes si no entiendes esa parte.
  • Material de la OIFem

Los envíos que hagas a Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.

Esta sesión de entramiento ya ha terminado. Si te quedaste con dudas, puedes consultar la explicación de las soluciones de los problemas.

#4

Cuarta sesión de la serie de entrenamiento.

En esta sesión vamos a seguir practicando bucles y aparecerán algunos problemas de bucles anidados, donde será necesario poner un bucle dentro de otro

Ten en cuenta que en cada sesión se asume que se entienden bien los conceptos de las sesiones previas.

Si quieres aprender sobre los temas de esta sesión, te proponemos algo de lectura:

  • Transparencias de Fundamentos de la programación de Luis Hernández Yañez, de la Universidad Complutense de Madrid:
    • Tipos e instrucciones II:
      • Bucles anidados: transparencias 331-338 (páginas 107-114 del PDF)
      • Ámbito y visibilidad: transparencias 339-348 (páginas 115-124 del PDF)
  • Material de la OIFem

Los envíos que hagas a Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.

Esta sesión de entramiento ya ha terminado. Si te quedaste con dudas, puedes consultar la explicación de las soluciones de los problemas.

#5

Quinta sesión de la serie de entrenamiento.

En esta sesión introducimos el concepto de arrays (conocidos también como arreglos en algunos lugares), que nos permiten guardar múltiples valores bajo el mismo nombre de variable, y acceder a cada uno utilizando un índice.

En el uso de arrays es muy habitual que surja la necesidad de recorrerlos, para lo que necesitarás utilizar los bucles que ya has practicado en sesiones previas.

Si quieres aprender sobre los temas de esta sesión, te proponemos algo de lectura. En algunos de los documentos se habla también de los vectores que son un tipo de datos disponible en C++ que pueden ser utilizados en lugar de los arrays clásicos. Los vectores proporcionan capacidades adicionales a los de los arrays, aunque ninguna de ellas son necesarias para resolver los problemas de esta serie.

  • Transparencias de Fundamentos de la programación de Luis Hernández Yañez, de la Universidad Complutense de Madrid:
    • Tipos e instrucciones II:
      • Arrays simples: transparencias 374-392 (páginas 150-168 del PDF)
    • Tipos estructurados:
      • Arrays de nuevo: transparencias 517-521 (páginas 6-10 del PDF)
      • Más sobre arrays: transparencias 522-530 (páginas 11-19 del PDF)
      • Cadenas de caracteres y tipo string: transparencias 531-542 (páginas 20-31 del PDF)
    • Recorrido y búsqueda en arrays:
      • Recorrido de arrays: 590-603 (páginas 3-16 del PDF)
      • Búsqueda en arrays: 604-613 (páginas 17-26 del PDF)
      • Cadenas : 614-629 (páginas 27-42 del PDF)
  • Material de la OIE
  • Material de la OIFem
    • Vectores: hasta la mitad de la página 4.

Los envíos que hagas a Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.

#6

Sexta sesión de la serie de entrenamiento.

Tras haber practicado en la sesión anterior el uso de arrays, en esta profundizaremos usando arrays bidimensionales, es decir arrays de arrays, o arrays con dos dimensiones.

Si al usar arrays es habitual que surja la necesidad de recorrerlos con un bucle, al tener arrays bidimensionales esos recorridos necesitan bucles anidados. Además, algunos de los problemas de la sesión pueden necesitar bucles adicionales o arrays auxiliares para guardar información más allá del array bidimensional que aparece de forma natural en el enunciado.

Si quieres aprender sobre los temas de esta sesión, te proponemos algo de lectura.

  • Transparencias de Fundamentos de la programación de Luis Hernández Yañez, de la Universidad Complutense de Madrid:
  • Material de la OIE
    • Matrices: en este caso, se implementan con vectores de vectores.

Los envíos que hagas a Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.

#7

Septima sesión de la serie de entrenamiento.

Debido a un error, se han mostrado en esta sesión los problemas de la primera sesión, en lugar de los correctos. Perdonad la confusión.

Ahora que ya sabemos utilizar arrays una operación muy habitual sobre ellos es ordenarlos. La ordenación de datos es algo habitual antes de mostrarlos al usuario, pero es también algo increíblemente común como paso previo a operaciones posteriores que se ven beneficiadas de que los datos estén ordenados. En ese caso es posible que los usuarios no lleguen a ver el resultado de la ordenación pero, internamente, el programa la habrá hecho en su propio beneficio.

En esta sesión vamos a practicar la ordenación, primero con problemas muy sencillos que pueden programarse haciendo la ordenación manualmente, y luego con problemas más exigentes que requieren algoritmos de ordenación eficientes. Si quieres aprender sobre los temas de esta sesión, te proponemos algo de lectura.

Los envíos que hagas a Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.

#8

Octava sesión de la serie de entrenamiento.

En la sesión 3 introducimos las funciones, trozos de código que se envuelven bajo un nombre y al que se puede enviar parámetros para aumentar las posibilidades de reutilización.

Existen un tipo particular de funciones llamadas funciones recursivas que son aquellas que se llaman a sí mismas con parámetros "más pequeños". El significado de "más pequeño" dependerá de la función concreta, pero lo importante es que en cada llamada los parámetros se acercan cada vez más a lo que se conoce como caso base en el que la función deja de llamarse a sí misma y devuelve un valor directamente.

En esta sesión vamos a practicar el uso de funciones recursivas. Ten en cuenta que algunas veces la recursión se puede evitar utilizando bucles. Para practicar, si te encuentras algún problema que puedas resolver usando bucles evita la tentación y utiliza recursión.

Si no habías oído hablar nunca sobre recursión, te proponemos algo de lectura.

  • Transparencias de Fundamentos de la programación de Luis Hernández Yañez, de la Universidad Complutense de Madrid:
  • Material de la OIE
  • Material de la OIFem

Los envíos que hagas a Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.

#9

Novena sesión de la serie de entrenamiento.

En sesiones anteriores aprendimos sobre arrays que, gracias a los bucles, podemos recorrer para buscar un elemento dentro de ellos.

También aprendimos a ordenarlos. Saber que tenemos el array ordenado es una información muy útil si queremos buscar un elemento. Cuando está desordenado, la búsqueda exige pasar por todos los valores para ver si es el que queremos y, en el peor de los casos, puede que tengamos que recorrer el array entero. Pero si está ordenado podemos usar una aproximación más inteligente. La idea es mirar en el elemento situado en el centro del array. Si es el buscado, ¡hemos acabado! Si no, comparamos el elemento con el buscado y dependiendo de cuál sea mayor, miramos en la parte izquierda o en la parte derecha. Con una sola comparación ¡hemos descartado la mitad del espacio de búsqueda!

A este procedimiento se le conoce con el nombre de búsqueda binaria (o búsqueda dicotómica) y supone un ahorro tan grande en tiempo que se utiliza para infinidad de cosas en informática, no solo para búsqueda de números en arrays ordenados. En esta sesión vamos a practicar algunos de esos usos. Los problemas que te proponemos se solucionan usando búsqueda binaria aunque a veces, tras leer el enunciado, ¡esté un poco escondida!

Si no habías oído hablar nunca sobre búsqueda binaria, te proponemos algo de lectura.

Los envíos que hagas a Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.

#10

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

A estas alturas ya tendréis cierta soltura con el control del flujo de ejecución del programa. Usando condicionales, bucles o subrutinas tenéis experiencia controlando qué línea de código se ejecutará a continuación en función de la necesidad concreta del momento.

También habéis practicado distintos tipos de datos básicos como enteros o cadenas, y cómo agregarlos utilizando arrays. Pero en informática es muy habitual tener que guardar la información en memoria utilizando estructuras de datos que mejoren ciertas operaciones. Por ejemplo, un array es una forma de almacenar información que permite un acceso inmediato a una determinada posición dado su índice, pero saber si hay algún elemento repetido es una operación muy costosa. Si en un determinado problema no se necesita saber el elemento de una posición concreta nunca, pero es necesario añadir elementos asegurando que no hay repetidos, utilizar un array normal puede no ser buena idea.

Para eso llegan ¡las estructuras de datos!. Son mecanismos que proporciona el lenguaje, o que pueden programarse, para organizar la información de formas imaginativas de modo que se favorezcan unas operaciones, normalmente en perjuicio de otras. En esta sesión os proponemos problemas que utilizan las siguientes:

  • Pilas: como en las pilas de platos, en esta estructura los elementos que se extraen son los últimos que se añadieron. En C++ se consiguen con la clase stack.
  • Colas: funcionan como la cola de un supermercado. Los elementos que se extraen son los primeros que se añadieron. En C++ se consiguen con la clase queue.
  • Conjuntos: son estructuras donde la inserción de elementos repetidos no tiene efecto, al igual que ocurre en los conjuntos matemáticos donde no puede haber elementos repetidos. En C++ se consiguen con la clase set o unordered_set .
  • Colas de prioridad: son como las colas, pero donde la inserción de elementos es ordenada. Cuando se añade un elemento no se coloca "al final de la cola", sino que se coloca en un punto intermedio dependiendo del orden relativo de los elementos. En C++ se consiguen con la clase priority_queue.
  • Tablas hash: recuerdan a los arrays pero el acceso a los elementos no se hace por un número entero, sino por un valor de cualquier otro tipo, como una cadena. También se pueden utilizar números si el uso de un array es imposible porque los índices están dispersos. En C++ se consiguen con la clase map o unordered_map.
#11

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

Después de varios meses aprendiendo cosas nuevas en cada sesión, llega el momento de ponerlas en práctica con problemas de todo tipo. La Olimpiada Informática Española está aquí mismo, y despedimos estas sesiones de entrenamiento con un "concurso" en el que cada uno tendrá que averiguar qué se necesita usar en cada problema de todo lo que hemos estado aprendiendo.

Recuerda que los envíos que hagas en Acepta el reto a los problemas propuestos para la sesión aparecerán reflejados aquí. Pincha en el número o nombre del problema para ver su enunciado.