Merge branch 'cp-algorithms:main' into main

Proxihox · web-flow · commit 4bb7a0dc1e73 · 2025-04-26T15:59:59.000+05:30
diff --git a/src/algebra/fibonacci-numbers.md b/src/algebra/fibonacci-numbers.md
@@ -22,6 +22,8 @@ Fibonacci numbers possess a lot of interesting properties. Here are a few of the
   
 $$F_{n-1} F_{n+1} - F_n^2 = (-1)^n$$
 
+>This can be proved by induction. A one-line proof by Knuth comes from taking the determinant of the 2x2 matrix form below.
+
 * The "addition" rule:
   
 $$F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$$
@@ -116,11 +118,63 @@ In this way, we obtain a linear solution, $O(n)$ time, saving all the values pri
 
 ### Matrix form
 
-It is easy to prove the following relation:
+To go from $(F_n, F_{n-1})$ to $(F_{n+1}, F_n)$, we can express the linear recurrence as a 2x2 matrix multiplication:
 
-$$\begin{pmatrix} 1 & 1 \cr 1 & 0 \cr\end{pmatrix} ^ n = \begin{pmatrix} F_{n+1} & F_{n} \cr F_{n} & F_{n-1} \cr\end{pmatrix}$$
+$$
+\begin{pmatrix}
+1 & 1 \\
+1 & 0
+\end{pmatrix}
+\begin{pmatrix}
+F_n \\
+F_{n-1}
+\end{pmatrix}
+=
+\begin{pmatrix}
+F_n + F_{n-1}  \\
+F_{n}
+\end{pmatrix}
+=
+\begin{pmatrix}
+F_{n+1}  \\
+F_{n}
+\end{pmatrix}
+$$
+
+This lets us treat iterating the recurrence as repeated matrix multiplication, which has nice properties. In particular,
+
+$$
+\begin{pmatrix}
+1 & 1 \\
+1 & 0
+\end{pmatrix}^n
+\begin{pmatrix}
+F_1 \\
+F_0
+\end{pmatrix}
+=
+\begin{pmatrix}
+F_{n+1}  \\
+F_{n}
+\end{pmatrix}
+$$
+
+where $F_1 = 1, F_0 = 0$. 
+In fact, since 
+
+$$
+\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
+= \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}
+$$
+
+we can use the matrix directly:
+
+$$
+\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n
+= \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}
+$$
 
-Thus, in order to find $F_n$ in $O(log  n)$ time, we must raise the matrix to n. (See [Binary exponentiation](binary-exp.md))
+Thus, in order to find $F_n$ in $O(\log  n)$ time, we must raise the matrix to n. (See [Binary exponentiation](binary-exp.md))
 
 ```{.cpp file=fibonacci_matrix}
 struct matrix {
diff --git a/src/geometry/manhattan-distance.md b/src/geometry/manhattan-distance.md
@@ -88,17 +88,19 @@ Here's an image to help visualizing the transformation:
 The Manhattan MST problem consists of, given some points in the plane, find the edges that connect all the points and have a minimum total sum of weights. The weight of an edge that connects two points is their Manhattan distance. For simplicity, we assume that all points have different locations.
 Here we show a way of finding the MST in $O(n \log{n})$ by finding for each point its nearest neighbor in each octant, as represented by the image below. This will give us $O(n)$ candidate edges, which, as we show below, will guarantee that they contain the MST. The final step is then using some standard MST, for example, [Kruskal algorithm using disjoint set union](https://cp-algorithms.com/graph/mst_kruskal_with_dsu.html).
 
-<center>![8 octants picture](manhattan-mst-octants.png)
-
-*The 8 octants relative to a point S*</center>
+<div style="text-align: center;">
+  <img src="manhattan-mst-octants.png" alt="8 octants picture">
+  *The 8 octants relative to a point S*
+</div>
 
 The algorithm shown here was first presented in a paper from [H. Zhou, N. Shenoy, and W. Nichollos (2002)](https://ieeexplore.ieee.org/document/913303). There is also another know algorithm that uses a Divide and conquer approach by [J. Stolfi](https://www.academia.edu/15667173/On_computing_all_north_east_nearest_neighbors_in_the_L1_metric), which is also very interesting and only differ in the way they find the nearest neighbor in each octant. They both have the same complexity, but the one presented here is easier to implement and has a lower constant factor.
 
 First, let's understand why it is enough to consider only the nearest neighbor in each octant. The idea is to show that for a point $s$ and any two other points $p$ and $q$ in the same octant, $d(p, q) < \max(d(s, p), d(s, q))$. This is important, because it shows that if there was a MST where $s$ is connected to both $p$ and $q$, we could erase one of these edges and add the edge $(p,q)$, which would decrease the total cost. To prove this, we assume without loss of generality that $p$ and $q$ are in the octanct $R_1$, which is defined by: $x_s \leq x$ and $x_s - y_s > x -  y$, and then do some casework. The image below give some intuition on why this is true.
 
-<center>![unique nearest neighbor](manhattan-mst-uniqueness.png)
-
-*Intuitively, the limitation of the octant makes it impossible that $p$ and $q$ are both closer to $s$ than to each other*</center>
+<div style="text-align: center;">
+  <img src="manhattan-mst-uniqueness.png" alt="unique nearest neighbor">
+  *Intuitively, the limitation of the octant makes it impossible that $p$ and $q$ are both closer to $s$ than to each other*
+</div>
 
 
 Therefore, the main question is how to find the nearest neighbor in each octant for every single of the $n$ points.
@@ -109,13 +111,15 @@ For simplicity we focus on the NNE octant ($R_1$ in the image above). All other
 
 We will use a sweep-line approach. We process the points from south-west to north-east, that is, by non-decreasing $x + y$. We also keep a set of points which don't have their nearest neighbor yet, which we call "active set". We add the images below to help visualize the algorithm.
 
-<center>![manhattan-mst-sweep](manhattan-mst-sweep-line-1.png)
-
-*In black with an arrow you can see the direction of the line-sweep. All the points below this lines are in the active set, and the points above are still not processed. In green we see the points which are in the octant of the processed point. In red the points that are not in the searched octant.*</center>
-
-<center>![manhattan-mst-sweep](manhattan-mst-sweep-line-2.png)
+<div style="text-align: center;">
+  <img src="manhattan-mst-sweep-line-1.png" alt="manhattan-mst-sweep">
+  *In black with an arrow you can see the direction of the line-sweep. All the points below this lines are in the active set, and the points above are still not processed. In green we see the points which are in the octant of the processed point. In red the points that are not in the searched octant.*
+</div>
 
-*In this image we see the active set after processing the point $p$. Note that the $2$ green points of the previous image had $p$ in its north-north-east octant and are not in the active set anymore, because they already found their nearest neighbor.*</center>
+<div style="text-align: center;">
+  <img src="manhattan-mst-sweep-line-2.png" alt="manhattan-mst-sweep">
+  *In this image we see the active set after processing the point $p$. Note that the $2$ green points of the previous image had $p$ in its north-north-east octant and are not in the active set anymore, because they already found their nearest neighbor.*
+</div>
 
 When we add a new point point $p$, for every point $s$ that has it in its octant we can safely assign $p$ as the nearest neighbor. This is true because their distance is $d(p,s) = |x_p - x_s| + |y_p - y_s| = (x_p + y_p) - (x_s + y_s)$, because $p$ is in the north-north-east octant. As all the next points will not have a smaller value of $x + y$ because of the sorting step, $p$ is guaranteed to have the smaller distance. We can then remove all such points from the active set, and finally add $p$ to the active set.
 
diff --git a/src/graph/edmonds_karp.md b/src/graph/edmonds_karp.md
@@ -90,14 +90,23 @@ Initially we start with a flow of 0.
 We can find the path $s - A - B - t$ with the residual capacities 7, 5, and 8.
 Their minimum is 5, therefore we can increase the flow along this path by 5.
 This gives a flow of 5 for the network.
-<center>![First path](Flow2.png) ![Network after first path](Flow3.png)</center>
+<div style="text-align: center;">
+  <img src="Flow2.png" alt="First path">
+  <img src="Flow3.png" alt="Network after first path">
+</div>
 
 Again we look for an augmenting path, this time we find $s - D - A - C - t$ with the residual capacities 4, 3, 3, and 5.
 Therefore we can increase the flow by 3 and we get a flow of 8 for the network.
-<center>![Second path](Flow4.png) ![Network after second path](Flow5.png)</center>
+<div style="text-align: center;">
+  <img src="Flow4.png" alt="Second path">
+  <img src="Flow5.png" alt="Network after second path">
+</div>
 
 This time we find the path $s - D - C - B - t$ with the residual capacities 1, 2, 3, and 3, and hence, we increase the flow by 1.
-<center>![Third path](Flow6.png) ![Network after third path](Flow7.png)</center>
+<div style="text-align: center;">
+  <img src="Flow6.png" alt="Third path">
+  <img src="Flow7.png" alt="Network after third path">
+</div>
 
 This time we find the augmenting path $s - A - D - C - t$ with the residual capacities 2, 3, 1, and 2.
 We can increase the flow by 1.
@@ -107,7 +116,10 @@ In the original flow network, we are not allowed to send any flow from $A$ to $D
 But because we already have a flow of 3 from $D$ to $A$, this is possible.
 The intuition of it is the following:
 Instead of sending a flow of 3 from $D$ to $A$, we only send 2 and compensate this by sending an additional flow of 1 from $s$ to $A$, which allows us to send an additional flow of 1 along the path $D - C - t$.
-<center>![Fourth path](Flow8.png) ![Network after fourth path](Flow9.png)</center>
+<div style="text-align: center;">
+  <img src="Flow8.png" alt="Fourth path">
+  <img src="Flow9.png" alt="Network after fourth path">
+</div>
 
 Now, it is impossible to find an augmenting path between $s$ and $t$, therefore this flow of $10$ is the maximal possible.
 We have found the maximal flow.
diff --git a/src/graph/mst_prim.md b/src/graph/mst_prim.md
@@ -13,7 +13,10 @@ The spanning tree with the least weight is called a minimum spanning tree.
 
 In the left image you can see a weighted undirected graph, and in the right image you can see the corresponding minimum spanning tree.
 
-<center>![Random graph](MST_before.png) ![MST of this graph](MST_after.png)</center>
+<div style="text-align: center;">
+  <img src="MST_before.png" alt="Random graph">
+  <img src="MST_after.png" alt="MST of this graph">
+</div>
 
 It is easy to see that any spanning tree will necessarily contain $n-1$ edges.
 
diff --git a/src/graph/second_best_mst.md b/src/graph/second_best_mst.md
@@ -53,10 +53,13 @@ The final time complexity of this approach is $O(E \log V)$.
 
 For example:
 
-<center>![MST](second_best_mst_1.png) ![Second best MST](second_best_mst_2.png) <br>
+<div style="text-align: center;">
+  <img src="second_best_mst_1.png" alt="MST">
+  <img src="second_best_mst_2.png" alt="Second best MST">
+  <br />
 
 *In the image left is the MST and right is the second best MST.*
-</center>
+</div>
 
 
 In the given graph suppose we root the MST at the blue vertex on the top, and then run our algorithm by start picking the edges not in MST.
diff --git a/src/graph/topological-sort.md b/src/graph/topological-sort.md
@@ -13,10 +13,10 @@ In other words, you want to find a permutation of the vertices (**topological or
 
 Here is one given graph together with its topological order:
 
-<center>
-![example directed graph](topological_1.png)
-![one topological order](topological_2.png)
-</center>
+<div style="text-align: center;">
+  <img src="topological_1.png" alt="example directed graph">
+  <img src="topological_2.png" alt="one topological order">
+</div>
 
 Topological order can be **non-unique** (for example, if there exist three vertices $a$, $b$, $c$ for which there exist paths from $a$ to $b$ and from $a$ to $c$ but not paths from $b$ to $c$ or from $c$ to $b$).
 The example graph also has multiple topological orders, a second topological order is the following:
diff --git a/src/string/aho_corasick.md b/src/string/aho_corasick.md
@@ -209,7 +209,7 @@ Assume that at the moment we stand in a vertex $v$ and consider a character $c$.
 1. $go[v][c] = -1$. In this case, we may assign $go[v][c] = go[u][c]$, which is already known by the induction hypothesis;
 2. $go[v][c] = w \neq -1$. In this case, we may assign $link[w] = go[u][c]$.
 
-In this way, we spend $O(1)$ time per each pair of a vertex and a character, making the running time $O(mk)$. The major overhead here is that we copy a lot of transitions from $u$ in the first case, while the transitions of the second case form the trie and sum up to $m$ over all vertices. To avoid the copying of $go[u][c]$, we may use a persistent array data structure, using which we initially copy $go[u]$ into $go[v]$ and then only update values for characters in which the transition would differ. This leads to the $O(n \log k)$ algorithm.
+In this way, we spend $O(1)$ time per each pair of a vertex and a character, making the running time $O(nk)$. The major overhead here is that we copy a lot of transitions from $u$ in the first case, while the transitions of the second case form the trie and sum up to $n$ over all vertices. To avoid the copying of $go[u][c]$, we may use a persistent array data structure, using which we initially copy $go[u]$ into $go[v]$ and then only update values for characters in which the transition would differ. This leads to the $O(n \log k)$ algorithm.
 
 ## Applications
 
