↓Skip to main content

Introducción a la programación competitiva con CSES

·2019 words·10 mins
Competitive Programming cses tutorial
Table of Contents
CSES paso a paso - This article is part of a series.

La programación competitiva es una disciplina que incorpora habilidades de pensamiento computacional, razonamiento matemático y conceptos de algoritmia a la programación habitual con el objetivo de resolver problemas abstractos de manera eficiente, idealmente utilizando la menor cantidad de tiempo y recursos posible.

Este ámbito de la programación está principalmente orientado a la participación en concursos y olimpiadas tan prestigiosas como la Olimpiada Informática Española o la Olimpiada Informática Internacional (International Olympiad in Informatics). No obstante, yendo más allá de los concursos, los conocimientos que se adquieren mediante la práctica de esta actividad se pueden aplicar de manera transversal en el trabajo diario o incluso en otras áreas del saber, ya que la programación competitiva ofrece una oportunidad de adquirir conocimientos robustos de algoritmia y estructuras de datos, así como de mejorar notablemente nuestra capacidad y velocidad de razonamiento lógico y matemático.

Finalmente, como aportación personal, la programación competitiva también puede ser muy divertida y satisfactoria, pues por encima de todos los conocimientos queda el sentimiento de autosuperación que se alcanza especialmente después de obtener la solución a un problema que llevaba dando vueltas en mi cabeza durante horas, ¡o incluso días! Ante todo, estamos aquí para disfrutar, aprender y conocer a gente con nuestros mismos gustos.

Materiales y requisitos previos
#

Esta guía asume un conocimiento razonablemente robusto de los fundamentos del lenguaje C++, incluyendo: entrada y salida de datos (cin, cout), tipos de datos, uso de variables y constantes, estructuras condicionales (if-else, switch), bucles (while, do-while, for), arrays y vectores, cadenas de caracteres (string), funciones, y preferiblemente algunas nociones básicas sobre punteros y recursión.

Adicionalmente, es conveniente tener un buen conocimiento de la lengua inglesa, pues la mayoría de los recursos sobre programación competitiva, y sobre todo los de mayor calidad (entre ellos los que utilizaremos en esta guía) están principal o únicamente disponibles en inglés.

Si quieres asegurarte de que conoces estos conceptos y que eres capaz de trabajar con ellos, te recomiendo que le eches un vistazo a alguna de las siguientes guías:

Sin embargo, si lo prefieres, puedes seguir adelante y, si encuentras algo que no entiendes, siempre puedes volver aquí y consultar lo que necesites.

Como estructura principal del curso, y para practicar los conceptos adquiridos, utilizaremos el CSES Problem Set, que contiene problemas desde los niveles más introductorios hasta otros más especializados sobre árboles, geometría, etc. A lo largo de las diferentes lecciones, indicaremos algunos de estos problemas como recomendación para intentar resolverlos. También ofrecemos soluciones a problemas seleccionados con fines ilustrativos.

También te recomiendo crearte una cuenta en Codeforces, donde puedes practicar con los miles de problemas disponibles en su problem set, así como participar en los concursos que organizan todas las semanas. Si estás empezando, prueba a participar en las Educational Rounds, así como en los concursos de división 3 y 4. Si ya tienes un nivel más avanzado, puedes probar a competir en las divisiones 2 y 1.

Finalmente, utilizaremos como referencia los libros Competitive Programmer’s Handbook (PDF) y Guide to Competitive Programming, ambos de Antti Laaksonen, uno de los creadores de la web de CSES. Estos libros están estructurados mayoritariamente en el mismo orden que siguen los tópicos del problem set, de modo que también son una buena guía para avanzar paso a paso.

Sitios para practicar y otros recursos
#

  • USACO Guide: una muy buena guía que recorre los tópicos de la USA Computing Olympiad (USACO). Además de las cuidadas explicaciones, contiene ejemplos en C++, Java y Python, problemas resueltos, y propuestas de problemas para resolver de diferentes fuentes.
  • Manual de Algoritmia de la Olimpiada Informática Española: contiene explicaciones muy bien detalladas de algoritmos de grafos, programación dinámica, y muchos otros conceptos que verás más de una vez en la resolución de los problemas.
  • CP-Algorithms: traducción al inglés de la web http://e-maxx.ru/algo (muy recomendada si hablas ruso). Tiene explicaciones y ejemplos de algoritmos más avanzados, y también ofrece con cada lección una selección de problemas relacionados y de dificultad variable para afianzar los conceptos.
  • Codeforces: contiene problemas, concursos, artículos con explicaciones… Es una de las webs más activas y organizan actividades regularmente para todos los niveles.
  • DMOJ: tiene un archivo con miles de problemas de olimpiadas alrededor del mundo, ordenados por categorías. También organizan concursos bastante a menudo.
  • ¡Acepta el Reto!: juez online con problemas en español. Tiene contenido bastante variado, aunque debido a la falta de separación por categorías o tópicos puede resultar difícil encontrar problemas de un tipo concreto.
  • Jutge.org: juez online con problemas en español y catalán. Tiene contenido de todo tipo, aunque puede resultar difícil encontrar problemas de un tipo concreto.
  • Online Judge: juez de la Universidad de Valladolid, muy popular entre la comunidad. Sin embargo, por muy castellano que sea, los problemas son en inglés.
  • Hackerrank: está enfocada principalmente a practicar algoritmia para las entrevistas de trabajo, pero contiene problemas de calidad y de todo tipo.
  • LeetCode: similar a Hackerrank.

El primer problema
#

¡Muy bien! Ya tenemos todo a punto para resolver nuestro primer problema. Inicia sesión en CSES para poder realizar el envío, y abre el primer problema del Problem Set: Weird Algorithm. Antes de leer el enunciado, hay varias cosas a tener en cuenta:

  • Time limit indica la cantidad de tiempo (en segundos) que puede tardar tu programa, como máximo, en ejecutarse. No solamente tenemos que alcanzar una solución, sino que además esta debe ser eficiente. En este primer problema no nos tenemos que preocupar, ya que los casos de prueba son pequeños, pero más adelante, encajar el algoritmo dentro del límite de tiempo sí que será un reto por sí mismo. Si nos pasamos de tiempo en la ejecución, obtendremos un error de Time limit exceeded.
  • Memory limit indica lo mismo, pero en memoria. En este caso, si utilizamos más de 512 MB (por ejemplo, porque hemos diseñado estructuras demasiado grandes, o porque tenemos un bucle infinito que duplica datos hasta que llena la memoria asignada), obtendremos un error de Memory limit exceeded.
  • En Input tenemos una descripción de los datos de la entrada, y en Output se describe cómo tenemos que presentar la solución en la salida estándar.
  • El apartado Constraints especifica el rango de valores que pueden adoptar las diferentes variables de la entrada. Aunque puede no parecer importante, nos puede dar pistas sobre el tipo de dato que tenemos que utilizar (enteros con o sin signo, variables de tipo long frente a las de tipo int, etc.).
  • Finalmente, tenemos un ejemplo que se corresponde con las descripciones anteriores.

Ahora que entendemos todas las partes del problema, leamos el enunciado:

Consider an algorithm that takes as input a positive integer $n$. If $n$ is even, the algorithm divides it by two, and if $n$ is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until $n$ is one. For example, the sequence for $n = 3$ is as follows:

$$3\rightarrow 10\rightarrow 5\rightarrow 16\rightarrow 8\rightarrow 4\rightarrow 2\rightarrow 1$$

Your task is to simulate the execution of the algorithm for a given value of $n$.

Input
The only input line contains an integer $n$.

Output
Print a line that contains all values of $n$ during the algorithm.

Constraints
$1\leq n\leq 10^6$

Diseño del algoritmo
#

Como buena práctica, una vez que hemos leído el enunciado, recomiendo coger lápiz y papel para plasmar lo que hemos leído y así poder diseñar un algoritmo para obtener la solución. Hacer dibujitos también ayuda.

En el enunciado se explica que nuestro algoritmo recibe un número entero positivo $n$ (no hace falta comprobar que sea entero ni positivo), que se ejecutará hasta que $n=1$. Mientras tanto, podemos hacer dos cosas:

  1. Si $n$ es par, reducimos $n$ a la mitad.
  2. Si $n$ es impar, lo multiplicamos 3 y al resultado le sumamos 1.

Finalmente, en el apartado Output se indica que tenemos que mostrar por pantalla el valor de $n$ a cada paso (incluyendo los valores inicial y final), con todos los valores en la misma línea y separados por un espacio.

Así pues, tenemos el siguiente algoritmo:

  1. Leemos el valor de $n$.
  2. Si $n = 1$, vamos al paso 6.
    Si no, continuamos al paso 3.
  3. Imprimimos el valor de $n$ en la pantalla.
  4. Si $n$ es par, asignamos $n := n/2$.
    Si no ($n$ es impar), asignamos $n := 3n + 1$.
  5. Volvemos al paso 2.
  6. Imprimimos el último valor de $n$ en la pantalla.

Implementación
#

Ahora, escribe tu programa que implemente este algoritmo. Para enviarlo, accede al apartado Submit del problema, selecciona tu archivo, elige “C++” en la lista de lenguajes, y haz click en el botón para enviar. Si todo va bien, recibirás una calificación de ACCEPTED. Si recibes un error (WRONG ANSWER, COMPILE ERROR, TIME LIMIT EXCEEDED, MEMORY LIMIT EXCEEDED, etc.), analiza los casos en los que falla y revisa tu código antes de volverlo a enviar.

A continuación tienes una posible solución al problema, pero te recomiendo que pruebes a resolverlo primero antes de mirarla.

Solución 
#include <iostream>
using namespace std;

int main () {
    int n;
    cin >> n;

    while (n != 1) {
        cout << n << ' ';
        if (n % 2 == 0) n /= 2; // n es par
        else n = 3*n + 1; // n es impar
    }

    cout << n << endl;
    return 0;
}

¡Enhorabuena! Ya has resuelto tu primer problema. Si te ha parecido fácil, puedes probar a resolver los siguientes:

  • Missing Number (CSES 1083, solución).

    Explicación (spoiler!)

    Una solución intuitiva podría ser introducir todos los números de la entrada en un vector e ir buscando uno a uno hasta que encontremos el valor que falta, o bien ordenar el vector con sort y recorrerlo hasta que encontremos un salto de más de 1 entre dos valores adyacentes.

    Sin embargo, la solución resulta mucho más eficiente si nos damos cuenta que los valores $1, 2, \dots, n$ suman a $k = \frac{n(n+1)}{2}$, y que si a este valor le restamos la suma de los datos de la entrada, obtendremos el número que nos falta. Es decir:

    $$x = \frac{n(n+1)}{2} - \sum_{i = 1}^{n-1} a_i$$

    donde $a_i$ es el $i$-ésimo valor de la entrada y $x$ es el número que buscamos.

  • Repetitions (CSES 1069, solución).

    Explicación (spoiler!)

    Simplemente hemos de recorrer la cadena manteniendo cuatro valores:

    • Una variable de tipo char con el carácter en la posición inmediatamente anterior.
    • Otra variable de tipo char con el carácter en la posición actual.
    • Una variable de tipo int para almacenar la longitud de la secuencia más larga hasta ese punto.
    • Otra variable de tipo int para almacenar la longitud de la cadena actual.

    Mientras recorramos la cadena y el carácter anterior y el actual sean iguales, incrementaremos la longitud de la secuencia actual en uno. Así, cuando la longitud de la cadena actual supere a la longitud máxima, almacenaremos el valor de la longitud actual como valor máximo.

    Cuando el carácter anterior y el actual son diferentes, habremos entrado en una nueva secuencia y la longitud de la secuencia actual se resetea a 1. Una vez hemos recorrido la cadena entera, imprimimos el valor máximo que hayamos encontrado hasta ese punto.

  • Increasing Array (CSES 1094, solución).

    Explicación (spoiler!)

    Necesitamos tres variables: una para almacenar el número actual, $curr$, una para almacenar el número anterior, $prev$, y otra para llevar la cuenta de los movimientos, $count$. Para cada par de valores $curr$ y $prev$, tenemos dos casos posibles:

    1. Si $curr < prev$, entonces $count := count + (prev - curr)$, y $curr := prev$.
    2. Si $curr \geq prev$, entonces pasamos al siguiente valor.

  • Next Round (Codeforces 158A, solución).

  • Bit++ (Codeforces 282A, solución).

Alberto Navalón
Author
Alberto Navalón
Computer Science student at the University of Alicante. Google Code-In Grand Prize Winner 2018, competitive programmer and language learner, now playing with NLP.
CSES paso a paso - This article is part of a series.