chapter01.tex

\chapter{Introducci\'on}

La programaci\'on competitiva combina dos temas:
(1) el diseño de algoritmos y (2) la implementaci\'on de algoritmos.

El \key{diseño de algoritmos} consiste en la resoluci\'on de problemas
y el pensamiento matem\'atico.
Se necesitan habilidades para analizar problemas y resolverlos
creativamente.
Un algoritmo para resolver un problema
debe ser tanto correcto como eficiente,
y el n\'ucleo del problema suele
tratar sobre la invenci\'on de un algoritmo eficiente.

El conocimiento te\'orico de algoritmos
es importante para los programadores competitivos.
T\'ipicamente, una soluci\'on a un problema es
una combinaci\'on de t\'ecnicas bien conocidas y
nuevas ideas.
Las t\'ecnicas que aparecen en la programaci\'on competitiva
tambi\'en forman la base para la investigaci\'on cient\'ifica
de algoritmos.

La \key{implementaci\'on de algoritmos} requiere buenas
habilidades de programaci\'on.
En la programaci\'on competitiva, las soluciones
se eval\'uan probando un algoritmo implementado
utilizando un conjunto de casos de prueba.
Por lo tanto, no basta con que la idea del
algoritmo sea correcta, sino que la implementaci\'on tambi\'en
debe ser correcta.

Un buen estilo de codificaci\'on en concursos es
directo y conciso.
Los programas deben escribirse r\'apidamente,
porque no hay mucho tiempo disponible.
A diferencia de la ingenier\'ia de software tradicional,
los programas son cortos (por lo general, como m\'aximo unas pocas
cientos de l\'ineas de c\'odigo), y no necesitan
mantenerse despu\'es del concurso.

\section{Lenguajes de programaci\'on}

\index{lenguaje de programaci\'on}

Actualmente, los lenguajes de programaci\'on m\'as populares
usados en concursos son C++, Python y Java.
Por ejemplo, en Google Code Jam 2017,
entre los mejores 3,000 participantes,
el 79 \% us\'o C++,
el 16 \% us\'o Python y
el 8 \% us\'o Java \cite{goo17}.
Algunos participantes tambi\'en usaron varios lenguajes.

Mucha gente piensa que C++ es la mejor opci\'on
para un programador competitivo,
y C++ est\'a casi siempre disponible en
los sistemas de concurso.
Los beneficios de usar C++ son que
es un lenguaje muy eficiente y
su biblioteca est\'andar contiene una
gran colecci\'on
de estructuras de datos y algoritmos.

Por otro lado, es bueno
dominar varios lenguajes y entender
sus fortalezas.
Por ejemplo, si se necesitan n\'umeros enteros grandes
en el problema,
Python puede ser una buena elecci\'on, porque
contiene operaciones integradas para
calcular con n\'umeros enteros grandes.
Aun as\'i, la mayor\'ia de los problemas en concursos de programaci\'on
est\'an diseñados de modo que
usar un lenguaje de programaci\'on espec\'ifico
no sea una ventaja injusta.

Todos los programas de ejemplo en este libro est\'an escritos en C++,
y las estructuras de datos y algoritmos de la
biblioteca est\'andar se usan con frecuencia.
Los programas siguen el est\'andar C++11,
que puede usarse en la mayor\'ia de los concursos hoy en d\'ia.
Si a\'un no sabes programar en C++,
ahora es un buen momento para empezar a aprender.

\subsubsection{Plantilla de c\'odigo en C++}

Una plantilla t\'ipica de c\'odigo en C++ para programaci\'on competitiva
se ve as\'i:

\begin{lstlisting}
#include <bits/stdc++.h>

using namespace std;

int main() {
    // la solucion viene aqui
}
\end{lstlisting}

La l\'inea \texttt{\#include} al principio
del c\'odigo es una caracter\'istica del compilador \texttt{g++}
que nos permite incluir toda la biblioteca est\'andar.
As\'i, no es necesario incluir por separado
bibliotecas como \texttt{iostream},
\texttt{vector} y \texttt{algorithm},
sino que est\'an disponibles autom\'aticamente.

La l\'inea \texttt{using} declara
que las clases y funciones
de la biblioteca est\'andar pueden usarse directamente
en el c\'odigo.
Sin la l\'inea \texttt{using} tendr\'iamos
que escribir, por ejemplo, \texttt{std::cout},
pero ahora basta con escribir \texttt{cout}.

El c\'odigo puede compilarse usando el siguiente comando:

\begin{lstlisting}
g++ -std=c++11 -O2 -Wall test.cpp -o test
\end{lstlisting}

Este comando produce un archivo binario \texttt{test}
a partir del c\'odigo fuente \texttt{test.cpp}.
El compilador sigue el est\'andar C++11
(\texttt{-std=c++11}),
optimiza el c\'odigo (\texttt{-O2})
y muestra advertencias sobre posibles errores (\texttt{-Wall}).

\section{Input y output}

\index{input y output}

En la mayor\'ia de los concursos, se usan flujos est\'andar para
leer input y escribir output.
En C++, los flujos est\'andar son
\texttt{cin} para input y \texttt{cout} para output.
Adem\'as, se pueden usar las funciones de C
\texttt{scanf} y \texttt{printf}.

El input para el programa usualmente consiste en
n\'umeros y cadenas que est\'an separados por
espacios y saltos de l\'inea.
Se pueden leer del flujo \texttt{cin}
de la siguiente manera:

\begin{lstlisting}
int a, b;
string x;
cin >> a >> b >> x;
\end{lstlisting}

Este tipo de c\'odigo siempre funciona,
asumiendo que hay al menos un espacio
o salto de l\'inea entre cada elemento en el input.
Por ejemplo, el c\'odigo anterior puede leer
cualquiera de los siguientes inputs:
\begin{lstlisting}
123 456 monkey
\end{lstlisting}
\begin{lstlisting}
123    456
monkey
\end{lstlisting}
El flujo \texttt{cout} se usa para el output
de la siguiente manera:
\begin{lstlisting}
int a = 123, b = 456;
string x = "monkey";
cout << a << " " << b << " " << x << "\n";
\end{lstlisting}

El input y el output a veces son
un cuello de botella en el programa.
Las siguientes l\'ineas al principio del c\'odigo
hacen que el input y el output sean m\'as eficientes:

\begin{lstlisting}
ios::sync_with_stdio(0);
cin.tie(0);
\end{lstlisting}

Ten en cuenta que el salto de l\'inea \texttt{"\textbackslash n"}
funciona m\'as r\'apido que \texttt{endl},
porque \texttt{endl} siempre provoca
una operaci\'on de vaciado del buffer.

Las funciones de C \texttt{scanf}
y \texttt{printf} son una alternativa
a los flujos est\'andar de C++.
Usualmente son un poco m\'as r\'apidas,
pero tambi\'en son m\'as dif\'iciles de usar.
El siguiente c\'odigo lee dos enteros del input:
\begin{lstlisting}
int a, b;
scanf("%d %d", &a, &b);
\end{lstlisting}
El siguiente c\'odigo imprime dos enteros:
\begin{lstlisting}
int a = 123, b = 456;
printf("%d %d\n", a, b);
\end{lstlisting}

A veces el programa debe leer una l\'inea completa
del input, posiblemente conteniendo espacios.
Esto se puede lograr usando la
funci\'on \texttt{getline}:

\begin{lstlisting}
string s;
getline(cin, s);
\end{lstlisting}

Si la cantidad de datos es desconocida, el siguiente
bucle es \'util:
\begin{lstlisting}
while (cin >> x) {
    // code
}
\end{lstlisting}
Este bucle lee elementos del input
uno tras otro, hasta que no haya m\'as
datos disponibles en el input.

En algunos sistemas de concursos, se usan archivos para
el input y el output.
Una soluci\'on f\'acil para esto es escribir
el c\'odigo como de costumbre usando flujos est\'andar,
pero agregar las siguientes l\'ineas al principio del c\'odigo:
\begin{lstlisting}
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
\end{lstlisting}
Despu\'es de esto, el programa lee el input del archivo
''input.txt'' y escribe el output en el archivo
''output.txt''.

\section{Trabajando con n\'umeros}

\index{entero}

\subsubsection{Enteros}

El tipo de entero m\'as usado en la programaci\'on competitiva
es \texttt{int}, que es un tipo de 32 bits con
un rango de valores de $-2^{31} \ldots 2^{31}-1$
o aproximadamente $-2 \cdot 10^9 \ldots 2 \cdot 10^9$.
Si el tipo \texttt{int} no es suficiente,
se puede usar el tipo de 64 bits \texttt{long long}.
Tiene un rango de valores de $-2^{63} \ldots 2^{63}-1$
o aproximadamente $-9 \cdot 10^{18} \ldots 9 \cdot 10^{18}$.

El siguiente c\'odigo define una
variable \texttt{long long}:
\begin{lstlisting}
long long x = 123456789123456789LL;
\end{lstlisting}
El sufijo \texttt{LL} significa que el
tipo del n\'umero es \texttt{long long}.

Un error com\'un al usar el tipo \texttt{long long}
es que el tipo \texttt{int} a\'un se usa en alguna parte
del c\'odigo.
Por ejemplo, el siguiente c\'odigo contiene
un error sutil:

\begin{lstlisting}
int a = 123456789;
long long b = a*a;
cout << b << "\n"; // -1757895751
\end{lstlisting}

Aunque la variable \texttt{b} es del tipo \texttt{long long},
ambos n\'umeros en la expresi\'on \texttt{a*a}
son del tipo \texttt{int} y el resultado es
también del tipo \texttt{int}.
Debido a esto, la variable \texttt{b}
contendr\'a un resultado incorrecto.
El problema se puede resolver cambiando el tipo
de \texttt{a} a \texttt{long long} o
cambiando la expresi\'on a \texttt{(long long)a*a}.

Usualmente los problemas de concursos est\'an configurados de manera que el
tipo \texttt{long long} es suficiente.
Aun as\'i, es bueno saber que
el compilador \texttt{g++} tambi\'en proporciona
un tipo de 128 bits \texttt{\_\_int128\_t}
con un rango de valores de
$-2^{127} \ldots 2^{127}-1$ o aproximadamente $-10^{38} \ldots 10^{38}$.
Sin embargo, este tipo no est\'a disponible en todos los sistemas de concursos.

\subsubsection{Aritm\'etica modular}

\index{resto}
\index{aritm\'etica modular}

Denotamos por $x \bmod m$ el resto
cuando $x$ se divide por $m$.
Por ejemplo, $17 \bmod 5 = 2$,
porque $17 = 3 \cdot 5 + 2$.

A veces, la respuesta a un problema es un
n\'umero muy grande pero es suficiente
mostrarlo ''m\'odulo $m$'', es decir,
el resto cuando la respuesta se divide por $m$
(por ejemplo, ''m\'odulo $10^9+7$'').
La idea es que incluso si la respuesta real
es muy grande,
basta con usar los tipos
\texttt{int} y \texttt{long long}.

Una propiedad importante del resto es que
en la suma, resta y multiplicaci\'on,
el resto se puede tomar antes de la operaci\'on:

\[
\begin{array}{rcr}
(a+b) \bmod m & = & (a \bmod m + b \bmod m) \bmod m \\
(a-b) \bmod m & = & (a \bmod m - b \bmod m) \bmod m \\
(a \cdot b) \bmod m & = & (a \bmod m \cdot b \bmod m) \bmod m
\end{array}
\]

Por lo tanto, podemos tomar el resto despu\'es de cada operaci\'on
y los n\'umeros nunca se volver\'an demasiado grandes.

Por ejemplo, el siguiente c\'odigo calcula $n!$,
el factorial de $n$, m\'odulo $m$:
\begin{lstlisting}
long long x = 1;
for (int i = 2; i <= n; i++) {
    x = (x*i)%m;
}
cout << x%m << "\n";
\end{lstlisting}

Usualmente queremos que el resto siempre
est\'e entre $0\ldots m-1$.
Sin embargo, en C++ y otros lenguajes,
el resto de un n\'umero negativo
es cero o negativo.
Una forma f\'acil de asegurarse de que no
haya restos negativos es primero calcular
el resto como de costumbre y luego sumar $m$
si el resultado es negativo:
\begin{lstlisting}
x = x%m;
if (x < 0) x += m;
\end{lstlisting}
Sin embargo, esto solo es necesario cuando hay
restas en el c\'odigo y el resto puede volverse negativo.

\subsubsection{N\'umeros de punto flotante}

\index{n\'umero de punto flotante}

Los tipos de punto flotante usuales en
la programaci\'on competitiva son
el \texttt{double} de 64 bits
y, como una extensi\'on en el compilador \texttt{g++},
el \texttt{long double} de 80 bits.
En la mayor\'ia de los casos, \texttt{double} es suficiente,
pero \texttt{long double} es m\'as preciso.

La precisi\'on requerida de la respuesta
usualmente se da en el enunciado del problema.
Una forma f\'acil de mostrar la respuesta es usar
la funci\'on \texttt{printf}
y dar el n\'umero de lugares decimales
en la cadena de formato.
Por ejemplo, el siguiente c\'odigo muestra
el valor de $x$ con 9 lugares decimales:

\begin{lstlisting}
printf("%.9f\n", x);
\end{lstlisting}

Una dificultad al usar n\'umeros de punto flotante
es que algunos n\'umeros no pueden ser representados
con precisi\'on como n\'umeros de punto flotante,
y habr\'a errores de redondeo.
Por ejemplo, el resultado del siguiente c\'odigo
es sorprendente:

\begin{lstlisting}
double x = 0.3*3+0.1;
printf("%.20f\n", x); // 0.99999999999999988898
\end{lstlisting}

Debido a un error de redondeo,
el valor de \texttt{x} es un poco menor que 1,
mientras que el valor correcto deber\'ia ser 1.

Es arriesgado comparar n\'umeros de punto flotante
con el operador \texttt{==},
porque es posible que los valores deber\'ian ser
iguales pero no lo son debido a errores de precisi\'on.
Una mejor manera de comparar n\'umeros de punto flotante
es asumir que dos n\'umeros son iguales
si la diferencia entre ellos es menor que $\varepsilon$,
donde $\varepsilon$ es un n\'umero peque\~no.

En la pr\'actica, los n\'umeros se pueden comparar
de la siguiente manera ($\varepsilon=10^{-9}$):

\begin{lstlisting}
if (abs(a-b) < 1e-9) {
    // a y b son iguales
}
\end{lstlisting}

Ten en cuenta que aunque los n\'umeros de punto flotante son imprecisos,
los enteros hasta un cierto l\'imite pueden ser
representados con precisi\'on.
Por ejemplo, usando \texttt{double},
es posible representar con precisi\'on todos los
enteros cuyo valor absoluto sea como m\'aximo $2^{53}$.

\section{Acortando c\'odigo}

El c\'odigo corto es ideal en la programaci\'on competitiva,
porque los programas deben escribirse
lo m\'as r\'apido posible.
Debido a esto, los programadores competitivos a menudo definen
nombres m\'as cortos para los tipos de datos y otras partes del c\'odigo.

\subsubsection{Nombres de tipos}
\index{tuppdef@\texttt{typedef}}
Usando el comando \texttt{typedef}
es posible dar un nombre m\'as corto
a un tipo de dato.
Por ejemplo, el nombre \texttt{long long} es largo,
as\'i que podemos definir un nombre m\'as corto \texttt{ll}:
\begin{lstlisting}
typedef long long ll;
\end{lstlisting}
Despu\'es de esto, el c\'odigo
\begin{lstlisting}
long long a = 123456789;
long long b = 987654321;
cout << a*b << "\n";
\end{lstlisting}
se puede acortar de la siguiente manera:
\begin{lstlisting}
ll a = 123456789;
ll b = 987654321;
cout << a*b << "\n";
\end{lstlisting}

El comando \texttt{typedef}
tambi\'en se puede usar con tipos m\'as complejos.
Por ejemplo, el siguiente c\'odigo da
el nombre \texttt{vi} a un vector de enteros
y el nombre \texttt{pi} a una pareja
que contiene dos enteros.
\begin{lstlisting}
typedef vector<int> vi;
typedef pair<int,int> pi;
\end{lstlisting}

\subsubsection{Macros}
\index{macro}
Otra forma de acortar el c\'odigo es definir
\key{macros}.
Un macro significa que ciertas cadenas en
el c\'odigo ser\'an cambiadas antes de la compilaci\'on.
En C++, los macros se definen usando la
palabra clave \texttt{\#define}.

Por ejemplo, podemos definir los siguientes macros:
\begin{lstlisting}
#define F first
#define S second
#define PB push_back
#define MP make_pair
\end{lstlisting}
Despu\'es de esto, el c\'odigo
\begin{lstlisting}
v.push_back(make_pair(y1,x1));
v.push_back(make_pair(y2,x2));
int d = v[i].first+v[i].second;
\end{lstlisting}
se puede acortar de la siguiente manera:
\begin{lstlisting}
v.PB(MP(y1,x1));
v.PB(MP(y2,x2));
int d = v[i].F+v[i].S;
\end{lstlisting}

Un macro tambi\'en puede tener par\'ametros,
lo que hace posible acortar bucles y otras
estructuras.
Por ejemplo, podemos definir el siguiente macro:
\begin{lstlisting}
#define REP(i,a,b) for (int i = a; i <= b; i++)
\end{lstlisting}
Despu\'es de esto, el c\'odigo
\begin{lstlisting}
for (int i = 1; i <= n; i++) {
    search(i);
}
\end{lstlisting}
se puede acortar de la siguiente manera:
\begin{lstlisting}
REP(i,1,n) {
    search(i);
}
\end{lstlisting}

A veces, los macros causan errores que pueden ser dif\'iciles
de detectar. Por ejemplo, considera el siguiente macro
que calcula el cuadrado de un n\'umero:
\begin{lstlisting}
#define SQ(a) a*a
\end{lstlisting}
Este macro \emph{no} siempre funciona como se espera.
Por ejemplo, el c\'odigo
\begin{lstlisting}
cout << SQ(3+3) << "\n";
\end{lstlisting}
corresponde al c\'odigo
\begin{lstlisting}
cout << 3+3*3+3 << "\n"; // 15
\end{lstlisting}

Una versi\'on mejor del macro es la siguiente:
\begin{lstlisting}
#define SQ(a) (a)*(a)
\end{lstlisting}
Ahora el c\'odigo
\begin{lstlisting}
cout << SQ(3+3) << "\n";
\end{lstlisting}
corresponde al c\'odigo
\begin{lstlisting}
cout << (3+3)*(3+3) << "\n"; // 36
\end{lstlisting}


\section{Matem\'aticas}

Las matem\'aticas juegan un papel importante en la programaci\'on competitiva,
y no es posible convertirse en un programador competitivo exitoso sin
tener buenas habilidades matem\'aticas.
Esta secci\'on discute algunos conceptos y f\'ormulas matem\'aticas importantes
que se necesitar\'an m\'as adelante en el libro.

\subsubsection{F\'ormulas de suma}

Cada suma de la forma
\[\sum_{x=1}^n x^k = 1^k+2^k+3^k+\ldots+n^k,\]
donde $k$ es un entero positivo,
tiene una f\'ormula cerrada que es un
polinomio de grado $k+1$.
Por ejemplo\footnote{\index{Faulhaber's formula}
Incluso hay una f\'ormula general para tales sumas, llamada \key{f\'ormula de Faulhaber},
pero es demasiado compleja para presentarla aqu\'i.},
\[\sum_{x=1}^n x = 1+2+3+\ldots+n = \frac{n(n+1)}{2}\]
y
\[\sum_{x=1}^n x^2 = 1^2+2^2+3^2+\ldots+n^2 = \frac{n(n+1)(2n+1)}{6}.\]

Una \key{progresi\'on aritm\'etica} es una \index{arithmetic progression}
secuencia de n\'umeros
donde la diferencia entre dos n\'umeros consecutivos
es constante.
Por ejemplo,
\[3, 7, 11, 15\]
es una progresi\'on aritm\'etica con constante 4.
La suma de una progresi\'on aritm\'etica se puede calcular
usando la f\'ormula
\[\underbrace{a + \cdots + b}_{n \,\, \textrm{n\'umeros}} = \frac{n(a+b)}{2}\]
donde $a$ es el primer n\'umero,
$b$ es el \'ultimo n\'umero y
$n$ es la cantidad de n\'umeros.
Por ejemplo,
\[3+7+11+15=\frac{4 \cdot (3+15)}{2} = 36.\]
La f\'ormula se basa en el hecho
de que la suma consiste en $n$ n\'umeros y
el valor de cada n\'umero es $(a+b)/2$ en promedio.

\index{geometric progression}
Una \key{progresi\'on geom\'etrica} es una secuencia
de n\'umeros
donde la raz\'on entre dos n\'umeros consecutivos
es constante.
Por ejemplo,
\[3,6,12,24\]
es una progresi\'on geom\'etrica con constante 2.
La suma de una progresi\'on geom\'etrica se puede calcular
usando la f\'ormula
\[a + ak + ak^2 + \cdots + b = \frac{bk-a}{k-1}\]
donde $a$ es el primer n\'umero,
$b$ es el \'ultimo n\'umero y la
raz\'on entre n\'umeros consecutivos es $k$.
Por ejemplo,
\[3+6+12+24=\frac{24 \cdot 2 - 3}{2-1} = 45.\]

Esta f\'ormula se puede derivar de la siguiente manera. Sea
\[ S = a + ak + ak^2 + \cdots + b .\]
Multiplicando ambos lados por $k$, obtenemos
\[ kS = ak + ak^2 + ak^3 + \cdots + bk,\]
y resolviendo la ecuaci\'on
\[ kS-S = bk-a\]
se obtiene la f\'ormula.

Un caso especial de una suma de una progresi\'on geom\'etrica es la f\'ormula
\[1+2+4+8+\ldots+2^{n-1}=2^n-1.\]

\index{harmonic sum}

Una \key{suma arm\'onica} es una suma de la forma
\[ \sum_{x=1}^n \frac{1}{x} = 1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}.\]

Un l\'imite superior para una suma arm\'onica es $\log_2(n)+1$.
A saber, podemos
modificar cada t\'ermino $1/k$ de modo que $k$ se convierta
en la potencia de dos m\'as cercana que no exceda a $k$.
Por ejemplo, cuando $n=6$, podemos estimar
la suma de la siguiente manera:
\[ 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6} \le
1+\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}.\]
Este l\'imite superior consta de $\log_2(n)+1$ partes
($1$, $2 \cdot 1/2$, $4 \cdot 1/4$, etc.),
y el valor de cada parte es como m\'aximo 1.

\subsubsection{Teor\'ia de conjuntos}

\index{set theory}
\index{set}
\index{intersection}
\index{union}
\index{difference}
\index{subset}
\index{universal set}
\index{complement}

Un \key{conjunto} es una colecci\'on de elementos.
Por ejemplo, el conjunto
\[X=\{2,4,7\}\]
contiene los elementos 2, 4 y 7.
El s\'imbolo $\emptyset$ denota un conjunto vac\'io,
y $|S|$ denota el tama\~no de un conjunto $S$,
es decir, el n\'umero de elementos en el conjunto.
Por ejemplo, en el conjunto anterior, $|X|=3$.

Si un conjunto $S$ contiene un elemento $x$,
escribimos $x \in S$,
y de lo contrario escribimos $x \notin S$.
Por ejemplo, en el conjunto anterior
\[4 \in X \hspace{10px}\textrm{y}\hspace{10px} 5 \notin X.\]

\begin{samepage}
Se pueden construir nuevos conjuntos utilizando operaciones de conjuntos:
\begin{itemize}
\item La \key{intersecci\'on} $A \cap B$ consiste en los elementos
que est\'an en ambos $A$ y $B$.
Por ejemplo, si $A=\{1,2,5\}$ y $B=\{2,4\}$,
entonces $A \cap B = \{2\}$.
\item La \key{uni\'on} $A \cup B$ consiste en los elementos
que est\'an en $A$ o $B$ o en ambos.
Por ejemplo, si $A=\{3,7\}$ y $B=\{2,3,8\}$,
entonces $A \cup B = \{2,3,7,8\}$.
\item El \key{complemento} $\bar A$ consiste en los elementos
que no est\'an en $A$.
La interpretaci\'on de un complemento depende del
\key{conjunto universal}, que contiene todos los elementos posibles.
Por ejemplo, si $A=\{1,2,5,7\}$ y el conjunto universal es
$\{1,2,\ldots,10\}$, entonces $\bar A = \{3,4,6,8,9,10\}$.
\item La \key{diferencia} $A \setminus B = A \cap \bar B$
consiste en los elementos que est\'an en $A$ pero no en $B$.
N\'otese que $B$ puede contener elementos que no est\'an en $A$.
Por ejemplo, si $A=\{2,3,7,8\}$ y $B=\{3,5,8\}$,
entonces $A \setminus B = \{2,7\}$.
\end{itemize}
\end{samepage}

Si cada elemento de $A$ tambi\'en pertenece a $S$,
decimos que $A$ es un \key{subconjunto} de $S$,
denotado por $A \subset S$.
Un conjunto $S$ siempre tiene $2^{|S|}$ subconjuntos,
incluyendo el conjunto vac\'io.
Por ejemplo, los subconjuntos del conjunto $\{2,4,7\}$ son
\begin{center}
$\emptyset$,
$\{2\}$, $\{4\}$, $\{7\}$, $\{2,4\}$, $\{2,7\}$, $\{4,7\}$ y $\{2,4,7\}$.
\end{center}

Algunos conjuntos usados frecuentemente son
$\mathbb{N}$ (n\'umeros naturales),
$\mathbb{Z}$ (n\'umeros enteros),
$\mathbb{Q}$ (n\'umeros racionales) y
$\mathbb{R}$ (n\'umeros reales).
El conjunto $\mathbb{N}$
se puede definir de dos maneras, dependiendo
de la situaci\'on:
ya sea $\mathbb{N}=\{0,1,2,\ldots\}$
o $\mathbb{N}=\{1,2,3,...\}$.

Tambi\'en podemos construir un conjunto usando una regla de la forma
\[\{f(n) : n \in S\},\]
donde $f(n)$ es alguna funci\'on.
Este conjunto contiene todos los elementos de la forma $f(n)$,
donde $n$ es un elemento en $S$.
Por ejemplo, el conjunto
\[X=\{2n : n \in \mathbb{Z}\}\]
contiene todos los enteros pares.

\subsubsection{L\'ogica}

\index{logic}
\index{negation}
\index{conjunction}
\index{disjunction}
\index{implication}
\index{equivalence}

El valor de una expresi\'on l\'ogica es
\key{verdadero} (1) o \key{falso} (0).
Los operadores l\'ogicos m\'as importantes son
$\lnot$ (\key{negaci\'on}),
$\land$ (\key{conjunci\'on}),
$\lor$ (\key{disyunci\'on}),
$\Rightarrow$ (\key{implicaci\'on}) y
$\Leftrightarrow$ (\key{equivalencia}).
La siguiente tabla muestra los significados de estos operadores:

\begin{center}
\begin{tabular}{rr|rrrrrrr}
$A$ & $B$ & $\lnot A$ & $\lnot B$ & $A \land B$ & $A \lor B$ & $A \Rightarrow B$ & $A \Leftrightarrow B$ \\
\hline
0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\
\end{tabular}
\end{center}

La expresi\'on $\lnot A$ tiene el valor opuesto de $A$.
La expresi\'on $A \land B$ es verdadera si ambos $A$ y $B$
son verdaderos,
y la expresi\'on $A \lor B$ es verdadera si $A$ o $B$ o ambos
son verdaderos.
La expresi\'on $A \Rightarrow B$ es verdadera
si cada vez que $A$ es verdadero, tambi\'en $B$ es verdadero.
La expresi\'on $A \Leftrightarrow B$ es verdadera
si $A$ y $B$ son ambos verdaderos o ambos falsos.

\index{predicate}

Un \key{predicado} es una expresi\'on que es verdadera o falsa
dependiendo de sus par\'ametros.
Los predicados usualmente se denotan con letras may\'usculas.
Por ejemplo, podemos definir un predicado $P(x)$
que es verdadero exactamente cuando $x$ es un n\'umero primo.
Usando esta definici\'on, $P(7)$ es verdadero pero $P(8)$ es falso.

\index{quantifier}

Un \key{cuantificador} conecta una expresi\'on l\'ogica
a los elementos de un conjunto.
Los cuantificadores m\'as importantes son
$\forall$ (\key{para todos}) y $\exists$ (\key{existe}).
Por ejemplo,
\[\forall x (\exists y (y < x))\]
significa que para cada elemento $x$ en el conjunto,
hay un elemento $y$ en el conjunto
tal que $y$ es menor que $x$.
Esto es verdadero en el conjunto de los enteros,
pero falso en el conjunto de los n\'umeros naturales.

Usando la notaci\'on descrita anteriormente,
podemos expresar muchos tipos de proposiciones l\'ogicas.
Por ejemplo,
\[\forall x ((x>1 \land \lnot P(x)) \Rightarrow (\exists a (\exists b (a > 1 \land b > 1 \land x = ab))))\]
significa que si un n\'umero $x$ es mayor que 1
y no es un n\'umero primo,
entonces hay n\'umeros $a$ y $b$
que son mayores que $1$ y cuyo producto es $x$.
Esta proposici\'on es verdadera en el conjunto de los enteros.

\subsubsection{Funciones}

La funci\'on $\lfloor x \rfloor$ redondea el n\'umero $x$
hacia abajo a un entero, y la funci\'on
$\lceil x \rceil$ redondea el n\'umero $x$
hacia arriba a un entero. Por ejemplo,
\[ \lfloor 3/2 \rfloor = 1 \hspace{10px} \textrm{y} \hspace{10px} \lceil 3/2 \rceil = 2.\]

Las funciones $\min(x_1,x_2,\ldots,x_n)$
y $\max(x_1,x_2,\ldots,x_n)$
dan el valor m\'as peque\~no y el m\'as grande de los valores
$x_1,x_2,\ldots,x_n$.
Por ejemplo,
\[ \min(1,2,3)=1 \hspace{10px} \textrm{y} \hspace{10px} \max(1,2,3)=3.\]

\index{factorial}

El \key{factorial} $n!$ se puede definir como
\[\prod_{x=1}^n x = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n\]
o recursivamente
\[
\begin{array}{lcl}
0! & = & 1 \\
n! & = & n \cdot (n-1)! \\
\end{array}
\]

\index{Fibonacci number}

Los \key{n\'umeros de Fibonacci}
%\footnote{Fibonacci (c. 1175--1250) fue un matem\'atico italiano.}
aparecen en muchas situaciones.
Se pueden definir recursivamente de la siguiente manera:
\[
\begin{array}{lcl}
f(0) & = & 0 \\
f(1) & = & 1 \\
f(n) & = & f(n-1)+f(n-2) \\
\end{array}
\]
Los primeros n\'umeros de Fibonacci son
\[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\]
Tambi\'en hay una f\'ormula de forma cerrada
para calcular los n\'umeros de Fibonacci, que a veces se llama
\index{Binet's formula} \key{f\'ormula de Binet}:
\[f(n)=\frac{(1 + \sqrt{5})^n - (1-\sqrt{5})^n}{2^n \sqrt{5}}.\]

\subsubsection{Logaritmos}

\index{logarithm}

El \key{logaritmo} de un n\'umero $x$
se denota $\log_k(x)$, donde $k$ es la base
del logaritmo.
Seg\'un la definici\'on,
$\log_k(x)=a$ exactamente cuando $k^a=x$.

Una propiedad \'util de los logaritmos es
que $\log_k(x)$ equivale al n\'umero de veces
que tenemos que dividir $x$ por $k$ antes de llegar
al n\'umero 1.
Por ejemplo, $\log_2(32)=5$
porque se necesitan 5 divisiones por 2:

\[32 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \]

Los logaritmos se utilizan a menudo en el an\'alisis de
algoritmos, porque muchos algoritmos eficientes
dividen algo a la mitad en cada paso.
Por lo tanto, podemos estimar la eficiencia de tales algoritmos
usando logaritmos.

El logaritmo de un producto es
\[\log_k(ab) = \log_k(a)+\log_k(b),\]
y en consecuencia,
\[\log_k(x^n) = n \cdot \log_k(x).\]
Adem\'as, el logaritmo de un cociente es
\[\log_k\Big(\frac{a}{b}\Big) = \log_k(a)-\log_k(b).\]
Otra f\'ormula \'util es
\[\log_u(x) = \frac{\log_k(x)}{\log_k(u)},\]
y usando esto, es posible calcular
logaritmos en cualquier base si hay una forma de
calcular logaritmos en alguna base fija.

\index{natural logarithm}

El \key{logaritmo natural} $\ln(x)$ de un n\'umero $x$
es un logaritmo cuya base es $e \approx 2.71828$.
Otra propiedad de los logaritmos es que
el n\'umero de d\'igitos de un entero $x$ en base $b$ es
$\lfloor \log_b(x)+1 \rfloor$.
Por ejemplo, la representaci\'on de
$123$ en base $2$ es 1111011 y
$\lfloor \log_2(123)+1 \rfloor = 7$.

\section{Concursos y recursos}

\subsubsection{IOI}

La Olimpiada Internacional de Informática (IOI)
es un concurso de programación anual para
estudiantes de secundaria.
Cada país puede enviar un equipo de
cuatro estudiantes al concurso.
Usualmente hay alrededor de 300 participantes
de 80 países.

La IOI consiste en dos concursos de cinco horas cada uno.
En ambos concursos, se les pide a los participantes
resolver tres tareas de algoritmos de diversas dificultades.
Las tareas se dividen en subtareas,
cada una de las cuales tiene una puntuación asignada.
Aunque los concursantes se dividen en equipos,
compiten como individuos.

El temario de la IOI \cite{iois} regula los temas
que pueden aparecer en las tareas de la IOI.
Casi todos los temas del temario de la IOI
están cubiertos en este libro.

Los participantes para la IOI se seleccionan a través de
concursos nacionales.
Antes de la IOI, se organizan muchos concursos regionales,
como la Olimpiada Báltica de Informática (BOI),
la Olimpiada Centroeuropea de Informática (CEOI)
y la Olimpiada de Informática de Asia-Pacífico (APIO).

Algunos países organizan concursos de práctica en línea
para futuros participantes de la IOI,
como el Concurso Abierto de Informática de Croacia \cite{coci}
y la Olimpiada de Computación de EE.UU. \cite{usaco}.
Además, una gran colección de problemas de concursos polacos
está disponible en línea \cite{main}.

\subsubsection{ICPC}

El Concurso Internacional Colegial de Programación (ICPC)
es un concurso de programación anual para estudiantes universitarios.
Cada equipo en el concurso está compuesto por tres estudiantes,
y a diferencia de la IOI, los estudiantes trabajan juntos;
hay solo una computadora disponible para cada equipo.

El ICPC consiste en varias etapas, y finalmente los
mejores equipos son invitados a las Finales Mundiales.
Aunque hay decenas de miles de participantes
en el concurso, solo hay un número pequeño\footnote{El número exacto de plazas finales varía de año en año; en 2017, hubo 133 plazas finales.} de plazas finales disponibles,
así que incluso avanzar a las finales
es un gran logro en algunas regiones.

En cada concurso ICPC, los equipos tienen cinco horas para
resolver alrededor de diez problemas de algoritmos.
Una solución a un problema se acepta solo si resuelve
todos los casos de prueba eficientemente.
Durante el concurso, los competidores pueden ver los resultados de otros equipos,
pero durante la última hora la tabla de clasificación se congela y no
es posible ver los resultados de las últimas entregas.

Los temas que pueden aparecer en el ICPC no están tan bien
especificados como los de la IOI.
En cualquier caso, está claro que se necesita más conocimiento
en el ICPC, especialmente más habilidades matemáticas.

\subsubsection{Concursos en línea}

También hay muchos concursos en línea que están abiertos para todos.
En este momento, el sitio de concursos más activo es Codeforces,
que organiza concursos aproximadamente cada semana.
En Codeforces, los participantes se dividen en dos divisiones:
los principiantes compiten en Div2 y los programadores más experimentados en Div1.
Otros sitios de concursos incluyen AtCoder, CS Academy, HackerRank y Topcoder.

Algunas empresas organizan concursos en línea con finales presenciales.
Ejemplos de tales concursos son Facebook Hacker Cup,
Google Code Jam y Yandex.Algorithm.
Por supuesto, las empresas también usan esos concursos para reclutar:
desempeñarse bien en un concurso es una buena manera de demostrar las propias habilidades.

\subsubsection{Libros}

Ya existen algunos libros (además de este libro) que
se enfocan en la programación competitiva y la resolución de problemas algorítmicos:

\begin{itemize}
\item S. S. Skiena y M. A. Revilla:
\emph{Programming Challenges: The Programming Contest Training Manual} \cite{ski03}
\item S. Halim y F. Halim:
\emph{Competitive Programming 3: The New Lower Bound of Programming Contests} \cite{hal13}
\item K. Diks et al.: \emph{Looking for a Challenge? The Ultimate Problem Set from
the University of Warsaw Programming Competitions} \cite{dik12}
\end{itemize}

Los primeros dos libros están destinados para principiantes,
mientras que el último libro contiene material avanzado.

Por supuesto, los libros generales de algoritmos también son adecuados para
programadores competitivos.
Algunos libros populares son:

\begin{itemize}
\item T. H. Cormen, C. E. Leiserson, R. L. Rivest y C. Stein:
\emph{Introduction to Algorithms} \cite{cor09}
\item J. Kleinberg y É. Tardos:
\emph{Algorithm Design} \cite{kle05}
\item S. S. Skiena:
\emph{The Algorithm Design Manual} \cite{ski08}
\end{itemize}