maths.tex

%! TEX root = ../implementations.tex
\chapter{Mathematics}

\section{General calculations}
\subsection{Binary exponentiation}
Binary exponentiation calculates a power in logarithmic 
time. Furthermore, it can be used for modular arithmetic:
\cppcode[firstline=20,]{code/binary_exp.cpp}
\noindent \textbf{\boldmath Running time: $\mathcal{O}(\log(\mathrm{exp}))$}


\newpage
\section{Modular arithmetic}
\subsection{Inverses}
To calculate a modular inverse, we will use Fermat's little theorem:
\[
	a^{p-1}\equiv 1 \ \mathrm{mod} \ p  \ \implies \  a^{p-2}\equiv a^{-1} \ \mathrm{mod} p
\]
If we combine this fact with binary exponentiation, we can obtain the 
modular inverse in logarithmic time:
\begin{minted}{cpp}
ll inverse(ll num) {
    return power(num, mod - 2);
}
\end{minted}
\noindent \textbf{\boldmath Running time: $\mathcal{O}(\log(\mathrm{mod}))$}

\subsection{Iterative extended euclidean algorithm}
Given two integers $a$, $b$, this algorithm calculates their $\gcd$ and two 
coefficients $x, y$ such that:
\begin{equation}
		a\cdot x + b\cdot y = g
\label{eq:gdcex}
\end{equation}
\cppcode[firstline=45,lastline=58]{code/Diophantine_eq.cpp}
\noindent \textbf{\boldmath Running time: $\mathcal{O}(\log(\mathrm{\min(n,m)}))$}
\newpage
\subsubsection*{Explanation}
The correctness of the calculation of the gcd follows from the correctness of the 
traditional implementation since, in each iteration, line 55 is equivalent to: 
\begin{alignat*}{2}
		a &\leftarrow b\\
		b &\leftarrow a \text{ mod } b
\end{alignat*}
and we know that $\gcd(a, b) = \gcd(b, \gcd(a,b))$.

The correctness of the calculated coefficients $x,y$ is slightly more complex. 
To understand it, we have to introduce the following loop invariant
\begin{equation}
		x \cdot a + y\cdot b = a_1 \quad
		x_1 \cdot a + y_1\cdot b = b_1
\label{eq:gdcProof}
\end{equation}
Before the loop starts, these two equations are trivial since: 
\[
(x,y)=(1,0) \quad  (x_1,y_1)=(0,1) \quad  (a_1,b_1)=(a,b)
\]
Now, we must prove that the invariant holds from one iteration to the
next. To do so, we can denote the values of the variable $x$ in the next
iteration as $x'$. Therefore, we can assume that (\ref{eq:gdcProof}) holds
true and we also know the values that the variables take in the next iteration:
\vspace{-20pt}

\begin{multicols}{2}

\begin{minipage}{0.4\textwidth}
\begin{alignat*}{2}
		x' &\leftarrow x_1 \\
		y' &\leftarrow y_1 \\
		x_1' &\leftarrow x-q\cdot x_1 \\
		y_1' &\leftarrow y-q\cdot y_1 \\
\end{alignat*}
\end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{alignat*}{2}
		a' &\leftarrow a\\
		b' &\leftarrow b\\
		a_1' &\leftarrow b_1 \\
		b_1' &\leftarrow a_1 -q \cdot b_1
\end{alignat*}
\end{minipage}
\end{multicols}
\noindent
Now we can easily prove the corresponding equations:
\begin{alignat*}{2}
		x' \cdot a' + y' \cdot b' = a_1' &\iff
		x_1 \cdot a + y_1 \cdot b = b_1  \iff (\ref{eq:gdcProof})
		\\
		\\
		x_1' \cdot a' + y_1' \cdot b' = b_1' 
		&\iff
		(x-q\cdot x_1) \cdot a + (y-q\cdot y_1) \cdot b = a_1 -q\cdot b_1 \iff
  		\\ &\iff
		x \cdot a + y \cdot b - q( x_1 \cdot a + y_1 \cdot b )= a_1 - q \cdot b_1
		\\ &\stackrel{\ref{eq:gdcProof}}{\iff}
		a_1 - q(b_1)= a_1 - q \cdot b_1
\end{alignat*}
\hfill $\square$
\newpage
\subsection{Linear Diophantine Equations}
A Linear Diophantine Equation is an equation of the general form:
\[
		a \cdot x + b \cdot y  = c
\]
where $a,b,c\in \mathbb{Z}$ are given constants  
and $x,y\in \mathbb{Z}$ are the unknowns.
\subsubsection{Algorithm}
If one of the constants is 0, finding the solutions is trivial. Therefore,
in the following, we will assume that they are not 0. Furthermore, we have
to keep in mind that:
\begin{center}
		\itshape
		The solution has at least one solution $\iff$ $c \,| \,\gcd(a,b)$
\end{center}
Then, we can use
the result of the Extended Euclidean Algorithm to obtain a solution:
\[
		(\ref{eq:gdcex}) \implies a \cdot x_g + b\cdot y_g = g \implies 
		a \cdot x_g \cdot \frac{c}{g}+ b\cdot y_g\cdot \frac{c}{g}= g 
		\cdot \frac{c}{g}
\]
Therefore, one solution is:
\[
		x_0 = x_g \cdot \frac{c}{g} \qquad
		y_0 = y_g \cdot \frac{c}{g} 
\]

However, that is not the only solution. It can be proven that the set of
pairs $(x,y)$ that satisfy the equations is:
\[
		\left \{ \left( x_0 + k \cdot \frac{b}{g}, 
		y_0 - k \cdot \frac{a}{g}\right): k\in \mathbb{Z} \right \}
\]

One interesting problem that we will be able to solve is finding the 
values of $k$ for which the values of $a$ and $b$ are in certain 
ranges. This is a relatively simple task since we can first find the 
range of $k$ that yields a valid $x$ value and then find the range
of $k$ that yields a valid $y$ value. The intersection will be the
answer.

Furthermore, since the functions that return the values of $x$ and 
$y$ for a given $k$
are linear, the range of $k$ that leads to values in an interval is
very easy to calculate: 
\[
		k \longrightarrow x_0 + k \cdot \frac{b}{g} \qquad
		k \longrightarrow y_0 + k \cdot\frac{a}{g}
\]
Note that we have to be careful when an endpoint of an interval 
has the value \texttt{inf} to avoid precision and overflow 
issues.

\newpage
\cppcode[firstline = 20, lastline = 42]{code/Diophantine_eq.cpp}


\subsubsection{Final implementation}
To solve the Linear Diophantine Equations, we will use a class to
that stores the three coefficients as well as the base solution.
Then, we can query the class for the solutions of the equation in 
a given range using the method \texttt{findRangeOfK}

\cppcode[firstline = 60, lastline = 91]{code/Diophantine_eq.cpp}
\noindent \textbf{\boldmath Running time: $\mathcal{O}(\log(\mathrm{\min(n,m)}))$}

For instance, if we want to get the solutions that are positive
in both variables, we can write:
\begin{minted}{cpp}
DioEq e1(a, b, d);
pll rangeK = e1.findRangeOfK({0, inf}, {0, inf});
\end{minted}

\subsubsection{Remarks}
\begin{itemize}
		\item Diophantine Linear Equations with three variables are
				simple to solve. For instance, to solve
				\[
						a\cdot x + b\cdot y + c\cdot z = d
				\]
				we can first solve 
				\[
						a \cdot x_1 + b\cdot x_2 = \gcd(a,b)
				\]
				and then solve 
				\[
						\gcd(a,b) \cdot x_2 + c \cdot y_2 = d
				\]
				And the final answers will be:
				\[
						x = x_1 \cdot x_2 \quad
						y = y_1 \cdot x_2 \quad
						z = y_2
				\]
				This process works because the linear combination of $a$ and 
				$b$ can only result in numbers that are multiples of their
				gcd. 

				However, we cannot reuse the way to calculate the number of
				solutions (with given ranges for $x$ and $y$)

\end{itemize}





\section{Catalan numbers}
We define the nth Catalan number as:
\[
	C_n= \frac{1}{n+1}{2n\choose n} = \frac{1}{n+1}\frac{(2n)!}{n! \;n!}
\]
We can also define them recursively:
\[
	C_0 = 1 \qquad C_{n+1} = \sum_{i=0}^n\big (C_i \; C_{n-i}\big)
\]
They can be used to solve many different problems. For instance:
\begin{itemize}
	\item Number of different binary trees of $n$ nodes. We can look
		at the specific case $n=3$. As we can see in the figure below,
		$C_3=5$. Furthermore, we can clearly identify the recursive relationship:
		\[
			C_3= (\text{3 is root}) + (\text{2 is root}) + (\text{1 is root}) = C_2\cdot C_0 + 
			C_1\cdot C_1 + C_0\cdot C_2
		\]

		\begin{figure}[h!]
			\centering
			\scalebox{0.5}{
			\begin{tikzpicture}
				\begin{scope}[every node/.style = {circle, thick, draw},
					every label/.append style={font = \small}]
					\node (A) at (0,0) {3};
					\node (B) at (-1,-1) {2};
					\node (C) at (-2,-2) {1};
				\end{scope}
				\begin{scope}[>={Stealth[black]},
						every edge/.style={draw=black, very thick}]
					\path [-] (A) edge (B);
					\path [-] (B) edge (C);
				\end{scope}
			\end{tikzpicture}
			\begin{tikzpicture}
				\begin{scope}[every node/.style = {circle, thick, draw},
					every label/.append style={font = \small}]
					\node (A) at (0,0) {3};
					\node (B) at (-1,-1) {1};
					\node (C) at (-0.25,-2) {2};
				\end{scope}
				\begin{scope}[>={Stealth[black]},
						every edge/.style={draw=black, very thick}]
					\path [-] (A) edge (B);
					\path [-] (B) edge (C);
				\end{scope}
			\end{tikzpicture}

			\hspace*{60 pt}

			\begin{tikzpicture}
				\begin{scope}[every node/.style = {circle, thick, draw},
					every label/.append style={font = \small}]
					\node (A) at (0,0) {2};
					\node (B) at (1,-1) {3};
					\node (C) at (-1,-1) {1};
				\end{scope}
					\node (J) at (-1,-2) {};
				\begin{scope}[>={Stealth[black]},
						every edge/.style={draw=black, very thick}]
					\path [-] (A) edge (B);
					\path [-] (A) edge (C);
				\end{scope}
			\end{tikzpicture}
			\hspace*{30 pt}
			\begin{tikzpicture}
				\begin{scope}[every node/.style = {circle, thick, draw},
					every label/.append style={font = \small}]
					\node (A) at (0,0) {1};
					\node (B) at (1,-1) {2};
					\node (C) at (2,-2) {3};
				\end{scope}
					\node (J) at (-1,-2) {};
				\begin{scope}[>={Stealth[black]},
						every edge/.style={draw=black, very thick}]
					\path [-] (A) edge (B);
					\path [-] (B) edge (C);
				\end{scope}
			\end{tikzpicture}
			\begin{tikzpicture}
				\begin{scope}[every node/.style = {circle, thick, draw},
					every label/.append style={font = \small}]
					\node (A) at (0,0) {1};
					\node (B) at (1,-1) {3};
					\node (C) at (0.25,-2) {2};
				\end{scope}
					\node (J) at (-1,-2) {};
				\begin{scope}[>={Stealth[black]},
						every edge/.style={draw=black, very thick}]
					\path [-] (A) edge (B);
					\path [-] (B) edge (C);
				\end{scope}
			\end{tikzpicture}
	}
	\end{figure}
	\item Number of expressions that contain $n$ pairs of parenthesis correctly
			paired. For instance, for $n=3$, there only $C_3=5$ valid 
			arrangements are:
			\[
					()()()\quad ()(()) \quad (())() \quad ((())) \quad (()())
			\]
			\newpage
	\item Number of different ways of arranging $n+1$ factors in parenthesis
			In the case of $n=3$, we can use the factors $a, b, c, d$. Then,
			we will have the following options:
			\[
					(ab)(cd) \quad a(b(cd)) \quad ((ab)c)d \quad (a(bc))d \quad
					a((bc)d)
			\]
	\item Number of ways to split a convex polygon of $n+2$ sides 
			into triangles. 

			\begin{figure}[h!]
					\centering
			\resizebox{80 mm}{!}{\subimport{figures/}{cat1.pdf_tex}}
			\end{figure}

	\item Number of paths from the bottom-left corner to the top-right corner
			of a $n\times n$ grid moving only up or right at every point and
			while not reaching the diagonal.
			\begin{figure}[h!]
					\centering
			\resizebox{80 mm}{!}{\subimport{figures/}{cat2.pdf_tex}}
			\end{figure}
			
\end{itemize}
\newpage
\section{Permutations}
\subsection{Converting one permutation into another }
In this problem we are given two permutations of the same size 
and we are tasked with converting one of them into the other. 
In order to do so, we will swap the elements at two positions
in the permutation zero or more times. 

\begin{figure}[h!]
\centering
\begin{tikzpicture}
		\draw (0,0) pic[]{array_rep={A =}{1,2,3,4,5,7,6}};
		\draw (0,-1.25) pic[]{array_rep={B =}{1,3,2,4,5,7,6}};
\end{tikzpicture}

\end{figure}
In this case, the most efficient way is to swap positions 1 and 2 
of permutation B to get permutation A. From examples like this one, we can 
deduce the following observations:
\begin{itemize}
		\item One swap will fix at most two numbers out of
				place.
		\item We will need at most $n-1$ swaps to change one
				permutation into the other. Note that
				we can \say{skip} the swap that corresponds
				to the last element since, at that point, by
				the Pigeonhole Principle, all elements must be in 
				the correct position.
\end{itemize}

To solve the problem, we shall change the representation 
to a graph where the edge \texttt{a \nolinebreak$\rightarrow$ \nolinebreak b} 
represents that there exists a position \texttt{j} such that 
\texttt{A[j]=a, B[j]=b}. Since the previous example was extraordinarily 
simple, we will present a new one to show this process:

\begin{figure}[h!]
\centering
\begin{subfigure}[c]{0.4\textwidth}
\centering
\begin{tikzpicture}
		\draw (0,0) pic[]{array_rep={A =}{1,2,3,4,5,6,7}};
		\draw (0,-1.25) pic[]{array_rep={B =}{2,3,1,4,7,5,6}};
\end{tikzpicture}
		
\end{subfigure}
\begin{subfigure}[c]{0.4\textwidth}
\centering
\begin{tikzpicture}
	\begin{scope}[every node/.style = {circle, thick, draw},
		every label/.append style={font = \small}]
		\node (A) at (0,0) {1};
		\node (B) at (2,0) {2};
		\node (C) at (4,0) {3};
		\node (D) at (6,0) {4};
		\node (E) at (0,-2) {5};
		\node (F) at (2,-2) {6};
		\node (G) at (4,-2) {7};
	\end{scope}
	\begin{scope}[>={Stealth[black]},
			every edge/.style={draw=black, very thick}]
		\path [->] (A) edge (B);
		\path [->] (B) edge (C);
		\path [->] (C) edge[bend right=30] (A);
		\path [->] (D) edge[loop right, out=150, in=210, looseness=7] (D);
		\path [->] (E) edge[bend right] (G);
		\path [->] (F) edge (E);
		\path [->] (G) edge (F);
	\end{scope}
\end{tikzpicture}
\end{subfigure}
\end{figure}
This graph will fulfill the following properties:
\begin{itemize}
		\setlength{\itemsep}{2pt}
		\item All edges are part of a cycle (possibly of length 1). 
				This is due to the fact that all vertices have an 
				in-degree and out-degree of 1.
		\item Since all edges form cycles,  connectivity and
				strong connectivity are equivalent. In particular, 
				we can make the edges undirected without altering 
				the connectivity.
\end{itemize}

The final piece of the puzzle is noticing that the elements that 
form a cycle of length $k$ need exactly $k-1$ swaps to be rearranged.
In order to prove this, we can use induction. 

If $k\le 2$, it is trivial. We can now assume that we have a cycle of
length $k$. When we swap the first two elements, we can either fix
one element that was out of place or two. However, if we had fixed
two, that would mean that those two were interchanged, in which
case they would form a 2-cycle and they could not be part of any
larger cycle. Therefore, we can only fix one element in this first
swap. After this swap, the cycle has length $k-1$ and, by
the inductive hypothesis, we will need $(k-1)-1$ moves to rearrange
all the elements. Thus, if we add the swap that we already performed,
we obtain the expected result of $k-1$ swaps.

To get the final formula, we observe that if there is a big cycle
that includes all elements, we would need $n-1$ swaps and 
every cycle that we introduce decreases the number of swaps 
required by one.
Therefore:
\[
		\text{\# Swaps} = n- \text{\# Components}
\]
To implement this formula we can construct the graph using undirected
edges and count the components applying UFDS

\cppcode[firstline=55,]{code/perm_inv.cpp}
\noindent \textbf{\boldmath Running time: $\mathcal{O}(n)$}

\subsection{Converting one permutation into another using adjacent swaps}
This is a very similar problem; however, now we can only swap elements
that are next to each other in the array. Furthermore, in this analysis,
we will reduce the problem to calculating the minimum number of adjacent
swaps required to sort a permutation. This is equivalent since we can use
a bijective application to \say{redefine} the order according to how the
elements are present in the first permutation.

The key observation in this case is the fact that the solution is the 
number of inversions in the permutation. We can define an inversion as
a pair of indices $(i,j)$ such that $i<j$ but $A_i > A_j$. We can easily
notice that (choosing optimally), each adjacent swap will fix exactly one 
inversion since it will fix the relative order between two elements.

Furthermore, this idea is surprisingly easy to implement since we can 
use a modified version of Merge Sort that counts the swaps that would
have been required to place an element in a specific position while
maintaining a log-linear complexity.

To do so, we can just count at each step how many position we had to move
the elements of the left half of the array to sort them.

\cppcode[firstline=21,]{code/perm_adj_inv.cpp}
\noindent \textbf{\boldmath Running time: $\mathcal{O}(n\log(n))$}