chapter01.tex

\chapter{Introducci\'on}

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

El \key{dise\~no de algoritmos} abarca la resoluci\'on
de problemas y el pensamiento matem\'atico.
Habilidades para analizar problemas y resolverlos
creativamente son necesarias.
Un algoritmo que resuelva un problema debe ser
correcto y eficiente a la vez, y a menudo el n\'ucleo
del problema es c\'omo inventar un algoritmo eficiente.

Conocimientos te\'oricos sobre algoritmos
son muy importantes para los competidores.
Normalmente, la soluci\'on a un problema
es la combinaci\'on de t\'ecnicas bien conocidas
y nuevos enfoques.
Las t\'ecnicas usadas en programaci\'on
competitiva tambi\'en forman la base
de la investigaci\'on cient\'ifica de los
algoritmos.

La \key{implementaci\'on de algoritmos} requiere
buenas habilidades de programaci\'on.
En programaci\'on competitiva, cada soluci\'on
es calificada por la corrida del algoritmo
implementado con cierto conjunto de casos de prueba.
Por lo tanto, no es suficiente que la idea del
algoritmo sea correcta, tambi\'en la implementaci\'on
debe ser correcta.

Un buen estilo de codificaci\'on en concursos es sencillo
y conciso. Los c\'odigos deben escribirse r\'apido,
debido a que no hay mucho tiempo disponible.
A diferencia de la ingenier\'ia de software tradicional,
los programas son cortos (usualmente no m\'as de
algunos cientos de l\'ineas) y no es necesario el
mantenimiento de ellos despu\'es de los concursos.

\section{Lenguajes de programaci\'on}

\index{programming language}

Actualmente, los lenguajes de programaci\'on m\'as
populares usados en concursos son C++, Python y Java.
Por ejemplo, en Google Code Jam 2016, entre los
mejores 3000 participantes
73 \% usaron C++,
15 \% usaron Python y
10 \% usaron Java \cite{goo16}.
Algunos participantes tambi\'en usaron varios lenguajes.

Muchas personas creen que C++ es la mejor opci\'on
para un concursante de programaci\'on,
y C++ est\'a casi siempre disponible en el
sistema de la competencia.
Los beneficios de usar C++ son que es un
lenguaje muy eficiente y su librer\'ia
est\'andar contiene una larga colecci\'on
de estructuras de datos y algoritmos

Por otra parte, es bueno dominar varios lenguajes
y entender sus fortalezas. Por ejemplo, si son
necesarios enteros grandes en el problema,
Python puede ser una buena opci\'on, debido
a que tiene implementadas operaciones para
calcular con enteros de este tipo.
Sin embargo, la mayor\'ia de los problemas
en concursos son elaborados de modo que usar
un lenguaje de programci\'on espec\'ifico
no proporcione 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 librer\'ia est\'andar son usados
a menudo. Los programas siguen el est\'andar de C++11,
el cual puede ser usado en la mayor parte de los
concursos actuales. Si no sabes programar en
C++ todav\'ia, ahora es un buen momento
para comenzar a aprender.

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

Una plantilla de c\'odigo en C++ t\'ipica en competencias
de programaci\'on luce as\'i:

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

using namespace std;

int main() {
    // solution comes here
}
\end{lstlisting}

La l\'inea \texttt{\#include} en el principio
del c\'odigo es una caracter\'istica del compilador
\texttt{g++} que nos permite incluir la librer\'ia
est\'andar completa. As\'i, no es necesario incluir
por separado cada una de las librer\'ias como
\texttt{iostream}, \texttt{vector} y \texttt{algorithm},
pues est\'an disponibles autom\'aticamente.

La l\'inea \texttt{using} declara que las clases
y funciones de la librer\'ia est\'andar pueden ser
usadas directamente en el c\'odigo. Sin esta
instrucci\'on \texttt{using} necesitar\'iamos
escribir, por ejemplo, \texttt{std::cout},
sin embargo es suficiente con escribir \texttt{cout}.

El c\'odigo puede ser compilado usando el siguiente
comando:

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

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

\section{Entrada y salida}

\index{input and output}

En la mayor\'ia de los concursos, el flujo de entrada y salida
est\'andares es el usado para lectura y escritura.
En C++, el flujo de entrada est\'andar es
\texttt{cin} y el flujo de salida est\'andar es \texttt{cout}
\footnote{\texttt{cin}: \textbf{c}onsole \textbf{in}put.
\texttt{cout}: \textbf{c}onsole \textbf{out}put. (N. del T.)}.
Adem\'as, las funciones de C \texttt{scanf} y \texttt{printf}
pueden ser usadas.

La entrada para un programa usualmente consiste
de n\'umeros y cadenas de texto que est\'an separados
por espacios y fines de l\'inea.
Estos pueden ser le\'idos desde el flujo \texttt{cin}
como sigue:

\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 fin de l\'inea entre cada elemento en
la entrada. Por ejemplo, el c\'odigo de arriba
puede leer ambas de las siguientes entradas:

\begin{lstlisting}
123 456 monkey
\end{lstlisting}
\begin{lstlisting}
123    456
monkey
\end{lstlisting}
El flujo \texttt{cout} es usado para la salida
como sigue:
\begin{lstlisting}
int a = 123, b = 456;
string x = "monkey";
cout << a << " " << b << " " << x << "\n";
\end{lstlisting}

La entrada y salida es frecuentemente un cuello
de botella en el programa. Las l\'ineas siguientes
al principio del c\'odigo hacen la entrada y
salida m\'as eficiente:

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

Note que el fin de l\'inea \texttt{"\textbackslash n"}
es m\'as r\'apido que \texttt{endl},
ya que \texttt{endl} siempre invoca una operaci\'on
de flush \footnote{
% TODO: explicar flush operation y los casos en los que
% conviene este comportamiento del endl como puede
% ser depuraci\'on.
}.

Las funciones del lenguaje C \texttt{scanf}
y \texttt{printf} son alternativas a los flujos
est\'andares de C++.
Normalmente estas son algo m\'as r\'apidas,
pero tambi\'en son un poco m\'as complicadas de
usar. El siguiente c\'odigo puede leer dos
enteros de la entrada:

\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}

Algunas veces el programa debe leer una l\'inea
completa desde la entrada, posiblemente
conteniendo espacios. Esto puede efectuarse
usando la funci\'on \texttt{getline}:

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

Si la cantidad de datos a leer es desconocida, el
siguiente ciclo es \'util:

\begin{lstlisting}
while (cin >> x) {
    // code
}
\end{lstlisting}

Este ciclo lee elementos
uno detr\'as de otro, mientras existan
datos disponibles en la entrada.

En algunos concursos, la entrada y salida debe
realizarse por ficheros. Una soluci\'on simple
para esto es escribir el c\'odigo normalmente
usando los flujos est\'andares, pero a\~nadiendo
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 la entrada desde el
fichero ''input.txt'' y escribe la salida al fichero
''output.txt''.

\section{Trabajando con enteros}

\index{integer}

\subsubsection{Enteros}

El tipo de dato entero m\'as usado en programaci\'on
competitiva es \texttt{int}, el cual es de
32-bit con rango de valores $-2^{31} \ldots 2^{31}-1$
o aproximadamente entre $-2 \cdot 10^9 \ldots 2 \cdot 10^9$.
Si el tipo de dato \texttt{int} no es suficiente,
el tipo de dato de 64-bit \texttt{long long} puede ser
usado. Este tiene valores en el rango $-2^{63} \ldots 2^{63}-1$
o aproximadamente $-9 \cdot 10^{18} \ldots 9 \cdot 10^{18}$.

El siguiente c\'odigo define una variable de tipo
\texttt{long long}:

\begin{lstlisting}
long long x = 123456789123456789LL;
\end{lstlisting}

El sufijo \texttt{LL} significa que el tipo de dato
del n\'umero es \texttt{long long}.

Un error com\'un cuando se usa \texttt{long long}
es que el tipo \texttt{int} siga us\'andose
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}

A pesar de que la variable \texttt{b} es de tipo
\texttt{long long}, ambos n\'umeros en la expresi\'on
\texttt{a*a} son de tipo \texttt{int} y el resultado
tambi\'en es de tipo \texttt{int}.
Debido a esto, la variable \texttt{b} contendr\'a
un resultado incorrecto. Este problema puede ser
resuelto cambiando el tipo de \texttt{a}
para \texttt{long long}
o reescribiendo la expresi\'on como \texttt{(long long)a*a}.

En concursos usualmente los problemas
son dise\~nados de modo que con el tipo
\texttt{long long} sea suficiente.
Incluso as\'i, es bueno conocer que el compilador
\texttt{g++} tambi\'en provee
un tipo de 128-bit \texttt{\_\_int128\_t}
con valores en el rango
$-2^{127} \ldots 2^{127}-1$ o aproximadamente
$-10^{38} \ldots 10^{38}$.
Sin embargo, este tipo no siempre est\'a disponible
en todos los entornos.

\subsubsection{Aritm\'etica modular}

\index{remainder}
\index{modular arithmetic}

Denotemos con $x \bmod m$ el resto cuando
$x$ es dividida por $m$.
Por ejemplo, $17 \bmod 5 = 2$,
ya que $17 = 3 \cdot 5 + 2$.

En muchas ocasiones, la respuesta al
problema es un n\'umero muy grande,
sin embargo, solo se pide producirlo
''modulo $m$'', o sea,
el resto cuando la respuesta se divide
por $m$ (por ejemplo, ''modulo $10^9+7$'').
La idea es que incluso cuando el resultado
real es muy grande, sea suficiente usar
los tipos de datos
\texttt{int} y \texttt{long long}.

Una propiedad importante del resto es
que en la adici\'on, en la substracci\'on y en la
multiplicaci\'on se puede efectuar el resto
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}
\]

Esto nos permite tomar el resto despu\'es de cada
operaci\'on y los n\'umeros nunca ser\'an muy grandes.

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

Lo habitual es el que resto siempre
deba estar entre $0\ldots m-1$.
Sin embargo, en C++ y otros lenguajes,
el resto de un n\'umero negativo
es cero o negativo. Una manera f\'acil
de asegurarse de no tener restos
negativos es primero calcular el resto
como se describi\'o y luego sumar $m$
al resultado si este fuera negativo:

\begin{lstlisting}
x = x % m;
if (x < 0)
    x += m;
\end{lstlisting}

Pero esto solo es necesario si hay
operaciones de sustracci\'on en el c\'odigo
y el resto puede quedar negativo.

\subsubsection{N\'umeros de punto flotante}

\index{floating point number}

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

La precisi\'on requerida de la soluci\'on
normalmente es dada en la descripci\'on del problema.
Una manera f\'acil de imprimir la respuesta
es usando la funci\'on \texttt{printf} con el n\'umero
de lugares decimales en la cadena de formato\footnote{Tambi\'en
puede hacerse con \texttt{cout}
especificando primero los lugares despu\'es de la coma con las
siguientes instrucciones: \texttt{cout.precision(5); cout << fixed;}
(N. del T.)}. Por ejemplo, el siguiente c\'odigo imprime
el valor de $x$ con 9 d\'igitos despu\'es de la coma:

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

La dificultad cuando se usan n\'umeros con coma
flotante es que algunos valores no pueden
ser representados exactamente, y existir\'an
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 al error de redondeo, el valor de
\texttt{x} es un poco menor que 1,
mientras que el valor correcto ser\'ia 1.

Es peligroso comparar n\'umeros de coma flotante
con el operador \texttt{==}, pues es posible
que los valores deban ser iguales pero no lo
sean debido a errores de precisi\'on.
Una mejor manera de comparar dos de estos n\'umeros
es asumiendo que son iguales si la diferencia
entre ellos es menor que $\varepsilon$,
donde $\varepsilon$ es un valor bien peque\~no.

En la pr\'actica, pueden ser comparados como
sigue ($\varepsilon=10^{-9}$):

\begin{lstlisting}
if (abs(a-b) < 1e-9) {
    // a and b are equal
}
\end{lstlisting}

Note que mientras los n\'umeros reales son algo
imprecisos en la computadora, los enteros hasta cierto
rango son representados con precisi\'on.
Por ejemplo, usando \texttt{double},
es posible representar de forma precisa
todos los enteros con valor absoluto
hasta $2^{53}$.

\section{Shortening code}

Short code is ideal in competitive programming,
because programs should be written
as fast as possible.
Because of this, competitive programmers often define
shorter names for datatypes and other parts of code.

\subsubsection{Type names}
\index{tuppdef@\texttt{typedef}}
Using the command \texttt{typedef}
it is possible to give a shorter name
to a datatype.
For example, the name \texttt{long long} is long,
so we can define a shorter name \texttt{ll}:
\begin{lstlisting}
typedef long long ll;
\end{lstlisting}
After this, the code
\begin{lstlisting}
long long a = 123456789;
long long b = 987654321;
cout << a*b << "\n";
\end{lstlisting}
can be shortened as follows:
\begin{lstlisting}
ll a = 123456789;
ll b = 987654321;
cout << a*b << "\n";
\end{lstlisting}

The command \texttt{typedef}
can also be used with more complex types.
For example, the following code gives
the name \texttt{vi} for a vector of integers
and the name \texttt{pi} for a pair
that contains two integers.
\begin{lstlisting}
typedef vector<int> vi;
typedef pair<int,int> pi;
\end{lstlisting}

\subsubsection{Macros}
\index{macro}
Another way to shorten code is to define
\key{macros}.
A macro means that certain strings in
the code will be changed before the compilation.
In C++, macros are defined using the
\texttt{\#define} keyword.

For example, we can define the following macros:
\begin{lstlisting}
#define F first
#define S second
#define PB push_back
#define MP make_pair
\end{lstlisting}
After this, the code
\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}
can be shortened as follows:
\begin{lstlisting}
v.PB(MP(y1,x1));
v.PB(MP(y2,x2));
int d = v[i].F+v[i].S;
\end{lstlisting}

A macro can also have parameters
which makes it possible to shorten loops and other
structures.
For example, we can define the following macro:
\begin{lstlisting}
#define REP(i,a,b) for (int i = a; i <= b; i++)
\end{lstlisting}
After this, the code
\begin{lstlisting}
for (int i = 1; i <= n; i++) {
    search(i);
}
\end{lstlisting}
can be shortened as follows:
\begin{lstlisting}
REP(i,1,n) {
    search(i);
}
\end{lstlisting}

\section{Mathematics}

Mathematics plays an important role in competitive
programming, and it is not possible to become
a successful competitive programmer without
having good mathematical skills.
This section discusses some important
mathematical concepts and formulas that
are needed later in the book.

\subsubsection{Sum formulas}

Each sum of the form
\[\sum_{x=1}^n x^k = 1^k+2^k+3^k+\ldots+n^k,\]
where $k$ is a positive integer,
has a closed-form formula that is a
polynomial of degree $k+1$.
For example,
\[\sum_{x=1}^n x = 1+2+3+\ldots+n = \frac{n(n+1)}{2}\]
and
\[\sum_{x=1}^n x^2 = 1^2+2^2+3^2+\ldots+n^2 = \frac{n(n+1)(2n+1)}{6}.\]

An \key{arithmetic progression} is a \index{arithmetic progression}
sequence of numbers
where the difference between any two consecutive
numbers is constant.
For example,
\[3, 7, 11, 15\]
is an arithmetic progression with constant 4.
The sum of an arithmetic progression can be calculated
using the formula
\[\frac{n(a+b)}{2}\]
where $a$ is the first number,
$b$ is the last number and
$n$ is the amount of numbers.
For example,
\[3+7+11+15=\frac{4 \cdot (3+15)}{2} = 36.\]
The formula is based on the fact
that the sum consists of $n$ numbers and
the value of each number is $(a+b)/2$ on average.

\index{geometric progression}
A \key{geometric progression} is a sequence
of numbers
where the ratio between any two consecutive
numbers is constant.
For example,
\[3,6,12,24\]
is a geometric progression with constant 2.
The sum of a geometric progression can be calculated
using the formula
\[\frac{bx-a}{x-1}\]
where $a$ is the first number,
$b$ is the last number and the
ratio between consecutive numbers is $x$.
For example,
\[3+6+12+24=\frac{24 \cdot 2 - 3}{2-1} = 45.\]

This formula can be derived as follows. Let
\[ S = a + ax + ax^2 + \cdots + b .\]
By multiplying both sides by $x$, we get
\[ xS = ax + ax^2 + ax^3 + \cdots + bx,\]
and solving the equation
\[ xS-S = bx-a\]
yields the formula.

A special case of a sum of a geometric progression is the formula
\[1+2+4+8+\ldots+2^{n-1}=2^n-1.\]

\index{harmonic sum}

A \key{harmonic sum} is a sum of the form
\[ \sum_{x=1}^n \frac{1}{x} = 1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}.\]

An upper bound for a harmonic sum is $\log_2(n)+1$.
Namely, we can
modify each term $1/k$ so that $k$ becomes
the nearest power of two that does not exceed $k$.
For example, when $n=6$, we can estimate
the sum as follows:
\[ 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}.\]
This upper bound consists of $\log_2(n)+1$ parts
($1$, $2 \cdot 1/2$, $4 \cdot 1/4$, etc.),
and the value of each part is at most 1.

\subsubsection{Set theory}

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

A \key{set} is a collection of elements.
For example, the set
\[X=\{2,4,7\}\]
contains elements 2, 4 and 7.
The symbol $\emptyset$ denotes an empty set,
and $|S|$ denotes the size of a set $S$,
i.e., the number of elements in the set.
For example, in the above set, $|X|=3$.

If a set $S$ contains an element $x$,
we write $x \in S$,
and otherwise we write $x \notin S$.
For example, in the above set
\[4 \in X \hspace{10px}\textrm{and}\hspace{10px} 5 \notin X.\]

\begin{samepage}
New sets can be constructed using set operations:
\begin{itemize}
\item The \key{intersection} $A \cap B$ consists of elements
that are in both $A$ and $B$.
For example, if $A=\{1,2,5\}$ and $B=\{2,4\}$,
then $A \cap B = \{2\}$.
\item The \key{union} $A \cup B$ consists of elements
that are in $A$ or $B$ or both.
For example, if $A=\{3,7\}$ and $B=\{2,3,8\}$,
then $A \cup B = \{2,3,7,8\}$.
\item The \key{complement} $\bar A$ consists of elements
that are not in $A$.
The interpretation of a complement depends on
the \key{universal set}, which contains all possible elements.
For example, if $A=\{1,2,5,7\}$ and the universal set is
$\{1,2,\ldots,10\}$, then $\bar A = \{3,4,6,8,9,10\}$.
\item The \key{difference} $A \setminus B = A \cap \bar B$
consists of elements that are in $A$ but not in $B$.
Note that $B$ can contain elements that are not in $A$.
For example, if $A=\{2,3,7,8\}$ and $B=\{3,5,8\}$,
then $A \setminus B = \{2,7\}$.
\end{itemize}
\end{samepage}

If each element of $A$ also belongs to $S$,
we say that $A$ is a \key{subset} of $S$,
denoted by $A \subset S$.
A set $S$ always has $2^{|S|}$ subsets,
including the empty set.
For example, the subsets of the set $\{2,4,7\}$ are
\begin{center}
$\emptyset$,
$\{2\}$, $\{4\}$, $\{7\}$, $\{2,4\}$, $\{2,7\}$, $\{4,7\}$ and $\{2,4,7\}$.
\end{center}

Some often used sets are
$\mathbb{N}$ (natural numbers),
$\mathbb{Z}$ (integers),
$\mathbb{Q}$ (rational numbers) and
$\mathbb{R}$ (real numbers).
The set $\mathbb{N}$
can be defined in two ways, depending
on the situation:
either $\mathbb{N}=\{0,1,2,\ldots\}$
or $\mathbb{N}=\{1,2,3,...\}$.

We can also construct a set using a rule of the form
\[\{f(n) : n \in S\},\]
where $f(n)$ is some function.
This set contains all elements of the form $f(n)$,
where $n$ is an element in $S$.
For example, the set
\[X=\{2n : n \in \mathbb{Z}\}\]
contains all even integers.

\subsubsection{Logic}

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

The value of a logical expression is either
\key{true} (1) or \key{false} (0).
The most important logical operators are
$\lnot$ (\key{negation}),
$\land$ (\key{conjunction}),
$\lor$ (\key{disjunction}),
$\Rightarrow$ (\key{implication}) and
$\Leftrightarrow$ (\key{equivalence}).
The following table shows the meanings of these operators:

\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}

The expression $\lnot A$ has the opposite value of $A$.
The expression $A \land B$ is true if both $A$ and $B$
are true,
and the expression $A \lor B$ is true if $A$ or $B$ or both
are true.
The expression $A \Rightarrow B$ is true
if whenever $A$ is true, also $B$ is true.
The expression $A \Leftrightarrow B$ is true
if $A$ and $B$ are both true or both false.

\index{predicate}

A \key{predicate} is an expression that is true or false
depending on its parameters.
Predicates are usually denoted by capital letters.
For example, we can define a predicate $P(x)$
that is true exactly when $x$ is a prime number.
Using this definition, $P(7)$ is true but $P(8)$ is false.

\index{quantifier}

A \key{quantifier} connects a logical expression
to the elements of a set.
The most important quantifiers are
$\forall$ (\key{for all}) and $\exists$ (\key{there is}).
For example,
\[\forall x (\exists y (y < x))\]
means that for each element $x$ in the set,
there is an element $y$ in the set
such that $y$ is smaller than $x$.
This is true in the set of integers,
but false in the set of natural numbers.

Using the notation described above,
we can express many kinds of logical propositions.
For example,
\[\forall x ((x>1 \land \lnot P(x)) \Rightarrow (\exists a (\exists b (x = ab \land a > 1 \land b > 1))))\]
means that if a number $x$ is larger than 1
and not a prime number,
then there are numbers $a$ and $b$
that are larger than $1$ and whose product is $x$.
This proposition is true in the set of integers.

\subsubsection{Functions}

The function $\lfloor x \rfloor$ rounds the number $x$
down to an integer, and the function
$\lceil x \rceil$ rounds the number $x$
up to an integer. For example,
\[ \lfloor 3/2 \rfloor = 1 \hspace{10px} \textrm{and} \hspace{10px} \lceil 3/2 \rceil = 2.\]

The functions $\min(x_1,x_2,\ldots,x_n)$
and $\max(x_1,x_2,\ldots,x_n)$
give the smallest and largest of values
$x_1,x_2,\ldots,x_n$.
For example,
\[ \min(1,2,3)=1 \hspace{10px} \textrm{and} \hspace{10px} \max(1,2,3)=3.\]

\index{factorial}

The \key{factorial} $n!$ can be defined
\[\prod_{x=1}^n x = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n\]
or recursively
\[
\begin{array}{lcl}
0! & = & 1 \\
n! & = & n \cdot (n-1)! \\
\end{array}
\]

\index{Fibonacci number}

The \key{Fibonacci numbers}
%\footnote{Fibonacci (c. 1175--1250) was an Italian mathematician.}
arise in many situations.
They can be defined recursively as follows:
\[
\begin{array}{lcl}
f(0) & = & 0 \\
f(1) & = & 1 \\
f(n) & = & f(n-1)+f(n-2) \\
\end{array}
\]
The first Fibonacci numbers are
\[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\]
There is also a closed-form formula
for calculating Fibonacci numbers\footnote{This formula is sometimes called
\index{Binet's formula} \key{Binet's formula}.}:
\[f(n)=\frac{(1 + \sqrt{5})^n - (1-\sqrt{5})^n}{2^n \sqrt{5}}.\]

\subsubsection{Logarithms}

\index{logarithm}

The \key{logarithm} of a number $x$
is denoted $\log_k(x)$, where $k$ is the base
of the logarithm.
According to the definition,
$\log_k(x)=a$ exactly when $k^a=x$.

A useful property of logarithms is
that $\log_k(x)$ equals the number of times
we have to divide $x$ by $k$ before we reach 
the number 1.
For example, $\log_2(32)=5$
because 5 divisions are needed:

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

Logarithms are often used in the analysis of
algorithms, because many efficient algorithms
halve something at each step.
Hence, we can estimate the efficiency of such algorithms
using logarithms.

The logarithm of a product is
\[\log_k(ab) = \log_k(a)+\log_k(b),\]
and consequently,
\[\log_k(x^n) = n \cdot \log_k(x).\]
In addition, the logarithm of a quotient is
\[\log_k\Big(\frac{a}{b}\Big) = \log_k(a)-\log_k(b).\]
Another useful formula is
\[\log_u(x) = \frac{\log_k(x)}{\log_k(u)},\]
and using this, it is possible to calculate
logarithms to any base if there is a way to
calculate logarithms to some fixed base.

\index{natural logarithm}

The \key{natural logarithm} $\ln(x)$ of a number $x$
is a logarithm whose base is $e \approx 2{,}71828$.

Another property of logarithms is that
the number of digits of an integer $x$ in base $b$ is
$\lfloor \log_b(x)+1 \rfloor$.
For example, the representation of
$123$ in base $2$ is 1111011 and
$\lfloor \log_2(123)+1 \rfloor = 7$.

\section{Contests}

\subsubsection{IOI}

The International Olympiad in Informatics (IOI)
is an annual programming contest for
secondary school students.
Each country is allowed to send a team of
four students to the contest.
There are usually about 300 participants
from 80 countries.

The IOI consists of two five-hour long contests.
In both contests, the participants are asked to
solve three algorithm tasks of various difficulty.
The tasks are divided into subtasks,
each of which has an assigned score.
Even if the contestants are divided into teams,
they compete as individuals.

The IOI syllabus \cite{iois} regulates the topics
that may appear in IOI tasks.
This book covers almost all the topics in the IOI syllabus.

Participants for the IOI are selected through
national contests.
Before the IOI, many regional contests are organized,
such as the Baltic Olympiad in Informatics (BOI),
the Central European Olympiad in Informatics (CEOI)
and the Asia-Pacific Informatics Olympiad (APIO).

Some countries organize online practice contests
for future IOI participants,
such as the Croatian Open Competition in Informatics (COCI)
and the USA Computing Olympiad (USACO).
In addition,
many problems from Polish contests
are available online\footnote{Młodzieżowa Akademia Informatyczna (MAIN), \texttt{http://main.edu.pl/}}.

\subsubsection{ICPC}

The International Collegiate Programming Contest (ICPC)
is an annual programming contest for university students.
Each team in the contest consists of three students,
and unlike in the IOI, the students work together;
there is only one computer available for each team.

The ICPC consists of several stages, and finally the
best teams are invited to the World Finals.
While there are tens of thousands of participants
in the contest, there are only a small number\footnote{The exact number of final
slots varies from year to year; in 2016, there were 128 final slots.} of final slots available,
so even advancing to the finals
is a great achievement in some regions.

In each ICPC contest, the teams have five hours of time to
solve about ten algorithm problems.
A solution to a problem is accepted only if it solves
all test cases efficiently.
During the contest, competitors may view the results of other teams,
but for the last hour the scoreboard is frozen and it
is not possible to see the results of the last submissions.

The topics that may appear at the ICPC are not so well
specified as those at the IOI.
In any case, it is clear that more knowledge is needed
at the ICPC, especially more mathematical skills.

\subsubsection{Online contests}

There are also many online contests that are open for everybody.
At the moment, the most active contest site is Codeforces,
which organizes contests about weekly.
In Codeforces, participants are divided into two divisions:
beginners compete in Div2 and more experienced programmers in Div1.
Other contest sites include AtCoder, CS Academy, HackerRank and Topcoder.

Some companies organize online contests with onsite finals.
Examples of such contests are Facebook Hacker Cup,
Google Code Jam and Yandex.Algorithm.
Of course, companies also use those contests for recruiting:
performing well in a contest is a good way to prove one's skills.

\section{Resources}

\subsubsection{Competitive programming books}

There are already some books (besides this book) that
concentrate on competitive programming and algorithmic problem solving:

\begin{itemize}
\item S. Halim and F. Halim:
\emph{Competitive Programming 3: The New Lower Bound of Programming Contests} \cite{hal13}
\item S. S. Skiena and M. A. Revilla:
\emph{Programming Challenges: The Programming Contest Training Manual} \cite{ski03}
\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}

The first two books are intended for beginners,
whereas the last book contains advanced material.

\subsubsection{General algorithm books}

Of course, general algorithm books are also suitable for
competitive programmers.
Some popular books are:

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