cp-algorithms · chriskanten · Oct 18, 2024 · Oct 19, 2024 · Oct 19, 2024 · Oct 21, 2024
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
@@ -19,7 +19,7 @@ Follow these steps to start contributing:
 4. **Preview your changes** using the [preview page](preview.md) to ensure they look correct.
 5. **Commit your changes** by clicking the _Propose changes_ button.
 6. **Create a Pull Request (PR)** by clicking _Compare & pull request_.
-7. **Review process**: Someone from the core team will review your changes. This may take a few hours to a few days.
+7. **Review process**: Someone from the core team will review your changes. This may take a few days to a few weeks.
 
 ### Making Larger Changes
 

diff --git a/README.md b/README.md
@@ -16,6 +16,8 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
 
 ## Changelog
 
+- August, 2025: Overhaul of CP-Algorithms [donation system](https://github.com/sponsors/cp-algorithms). Please consider supporting us, so that we can grow!
+- August, 2025: Launched a [Discord server](https://discord.gg/HZ5AecN3KX)!
 - October, 2024: Welcome new maintainers: [jxu](https://github.com/jxu), [mhayter](https://github.com/mhayter) and [kostero](https://github.com/kostero)!
 - October, 15, 2024: GitHub pages based mirror is now served at [https://gh.cp-algorithms.com/](https://gh.cp-algorithms.com/), and an auxiliary competitive programming library is available at [https://lib.cp-algorithms.com/](https://lib.cp-algorithms.com/).
 - July 16, 2024: Major overhaul of the [Finding strongly connected components / Building condensation graph](https://cp-algorithms.com/graph/strongly-connected-components.html) article.
@@ -29,6 +31,8 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
 
 ### New articles
 
+- (19 August 2025) [Minimum Enclosing Circle](https://cp-algorithms.com/geometry/enclosing-circle.html)
+- (21 May 2025) [Simulated Annealing](https://cp-algorithms.com/num_methods/simulated_annealing.html)
 - (12 July 2024) [Manhattan distance](https://cp-algorithms.com/geometry/manhattan-distance.html)
 - (8 June 2024) [Knapsack Problem](https://cp-algorithms.com/dynamic_programming/knapsack.html)
 - (28 January 2024) [Introduction to Dynamic Programming](https://cp-algorithms.com/dynamic_programming/intro-to-dp.html)

diff --git a/mkdocs.yml b/mkdocs.yml
@@ -31,6 +31,7 @@ edit_uri: edit/main/src/
 copyright: Text is available under the <a href="https://github.com/cp-algorithms/cp-algorithms/blob/main/LICENSE">Creative Commons Attribution Share Alike 4.0 International</a> License<br/>Copyright &copy; 2014 - 2025 by <a href="https://github.com/cp-algorithms/cp-algorithms/graphs/contributors">cp-algorithms contributors</a>
 extra_javascript:
   - javascript/config.js
+  - javascript/donation-banner.js
   - https://cdnjs.cloudflare.com/polyfill/v3/polyfill.min.js?features=es6
   - https://unpkg.com/mathjax@3/es5/tex-mml-chtml.js
 extra_css:
@@ -79,6 +80,13 @@ plugins:
   - rss
 
 extra:
+  social:
+    - icon: fontawesome/brands/github
+      link: https://github.com/cp-algorithms/cp-algorithms
+    - icon: fontawesome/brands/discord
+      link: https://discord.gg/HZ5AecN3KX
+    - icon: fontawesome/solid/circle-dollar-to-slot
+      link: https://github.com/sponsors/cp-algorithms
   analytics:
     provider: google
     property: G-7FLS2HCYHH
diff --git a/src/algebra/big-integer.md b/src/algebra/big-integer.md
@@ -30,7 +30,7 @@ To improve performance we'll use $10^9$ as the base, so that each "digit" of the
 const int base = 1000*1000*1000;
 ```
 
-Digits will be stored in order from least to most significant. All operations will be implemented so that after each of them the result doesn't have any leading zeros, as long as operands didn't have any leading zeros either. All operations which might result in a number with leading zeros should be followed by code which removes them. Note that in this representation there are two valid notations for number zero: and empty vector, and a vector with a single zero digit.
+Digits will be stored in order from least to most significant. All operations will be implemented so that after each of them the result doesn't have any leading zeros, as long as operands didn't have any leading zeros either. All operations which might result in a number with leading zeros should be followed by code which removes them. Note that in this representation there are two valid notations for number zero: an empty vector, and a vector with a single zero digit.
 
 ### Output
 

diff --git a/src/algebra/binary-exp.md b/src/algebra/binary-exp.md
@@ -177,7 +177,7 @@ a_{31} & a_ {32} & a_ {33} & a_ {34} \\
 a_{41} & a_ {42} & a_ {43} & a_ {44}
 \end{pmatrix}$$
 
-that, when multiplied by a vector with the old coordinates and an unit gives a new vector with the new coordinates and an unit:
+that, when multiplied by a vector with the old coordinates and a unit gives a new vector with the new coordinates and a unit:
 
 $$\begin{pmatrix} x & y & z & 1 \end{pmatrix} \cdot
 \begin{pmatrix}

diff --git a/src/algebra/chinese-remainder-theorem.md b/src/algebra/chinese-remainder-theorem.md
@@ -154,7 +154,7 @@ $$\left\{\begin{align}
     a & \equiv 2 \pmod{6}
 \end{align}\right.$$
 
-It is pretty simple to determine is a system has a solution.
+It is pretty simple to determine if a system has a solution.
 And if it has one, we can use the original algorithm to solve a slightly modified system of congruences.
 
 A single congruence $a \equiv a_i \pmod{m_i}$ is equivalent to the system of congruences $a \equiv a_i \pmod{p_j^{n_j}}$ where $p_1^{n_1} p_2^{n_2}\cdots p_k^{n_k}$ is the prime factorization of $m_i$.

diff --git a/src/algebra/discrete-log.md b/src/algebra/discrete-log.md
@@ -129,7 +129,7 @@ With this change, the complexity of the algorithm is still the same, but now the
 Instead of a `map`, we can also use a hash table (`unordered_map` in C++) which has the average time complexity $O(1)$ for inserting and searching.
 
 Problems often ask for the minimum $x$ which satisfies the solution.  
-It is possible to get all answers and take the minimum, or reduce the first found answer using [Euler's theorem](phi-function.md#toc-tgt-2), but we can be smart about the order in which we calculate values and ensure the first answer we find is the minimum.
+It is possible to get all answers and take the minimum, or reduce the first found answer using [Euler's theorem](phi-function.md#application), but we can be smart about the order in which we calculate values and ensure the first answer we find is the minimum.
 
 ```{.cpp file=discrete_log}
 // Returns minimum x for which a ^ x % m = b % m, a and m are coprime.

diff --git a/src/algebra/factorization.md b/src/algebra/factorization.md
@@ -159,11 +159,10 @@ By looking at the squares $a^2$ modulo a fixed small number, it can be observed
 
 ## Pollard's $p - 1$ method { data-toc-label="Pollard's <script type='math/tex'>p - 1</script> method" }
 
-It is very likely that at least one factor of a number is $B$**-powersmooth** for small $B$.
-$B$-powersmooth means that every prime power $d^k$ that divides $p-1$ is at most $B$.
+It is very likely that a number $n$ has at least one prime factor $p$ such that $p - 1$ is $\mathrm{B}$**-powersmooth** for small $\mathrm{B}$. An integer $m$ is said to be $\mathrm{B}$-powersmooth if every prime power dividing $m$ is at most $\mathrm{B}$. Formally, let $\mathrm{B} \geqslant 1$ and let $m$ be any positive integer. Suppose the prime factorization of $m$ is $m = \prod {q_i}^{e_i}$, where each $q_i$ is a prime and $e_i \geqslant 1$. Then $m$ is $\mathrm{B}$-powersmooth if, for all $i$, ${q_i}^{e_i} \leqslant \mathrm{B}$. 
 E.g. the prime factorization of $4817191$ is $1303 \cdot 3697$.
-And the factors are $31$-powersmooth and $16$-powersmooth respectably, because $1303 - 1 = 2 \cdot 3 \cdot 7 \cdot 31$ and $3697 - 1 = 2^4 \cdot 3 \cdot 7 \cdot 11$.
-In 1974 John Pollard invented a method to extracts $B$-powersmooth factors from a composite number.
+And the values, $1303 - 1$ and $3697 - 1$, are $31$-powersmooth and $16$-powersmooth respectively, because $1303 - 1 = 2 \cdot 3 \cdot 7 \cdot 31$ and $3697 - 1 = 2^4 \cdot 3 \cdot 7 \cdot 11$.
+In 1974 John Pollard invented a method to extract factors $p$, s.t. $p-1$ is $\mathrm{B}$-powersmooth, from a composite number.
 
 The idea comes from [Fermat's little theorem](phi-function.md#application).
 Let a factorization of $n$ be $n = p \cdot q$.
@@ -180,7 +179,7 @@ This means that $a^M - 1 = p \cdot r$, and because of that also $p ~|~ \gcd(a^M
 
 Therefore, if $p - 1$ for a factor $p$ of $n$ divides $M$, we can extract a factor using [Euclid's algorithm](euclid-algorithm.md).
 
-It is clear, that the smallest $M$ that is a multiple of every $B$-powersmooth number is $\text{lcm}(1,~2~,3~,4~,~\dots,~B)$.
+It is clear, that the smallest $M$ that is a multiple of every $\mathrm{B}$-powersmooth number is $\text{lcm}(1,~2~,3~,4~,~\dots,~B)$.
 Or alternatively:
 
 $$M = \prod_{\text{prime } q \le B} q^{\lfloor \log_q B \rfloor}$$
@@ -189,11 +188,11 @@ Notice, if $p-1$ divides $M$ for all prime factors $p$ of $n$, then $\gcd(a^M -
 In this case we don't receive a factor.
 Therefore, we will try to perform the $\gcd$ multiple times, while we compute $M$.
 
-Some composite numbers don't have $B$-powersmooth factors for small $B$.
-For example, the factors of the composite number $100~000~000~000~000~493 = 763~013 \cdot 131~059~365~961$ are $190~753$-powersmooth and $1~092~161~383$-powersmooth.
-We will have to choose $B >= 190~753$ to factorize the number.
+Some composite numbers don't have factors $p$ s.t. $p-1$ is $\mathrm{B}$-powersmooth for small $\mathrm{B}$.
+For example, for the composite number $100~000~000~000~000~493 = 763~013 \cdot 131~059~365~961$, values $p-1$ are $190~753$-powersmooth and $1~092~161~383$-powersmooth correspondingly.
+We will have to choose $B \geq 190~753$ to factorize the number.
 
-In the following implementation we start with $B = 10$ and increase $B$ after each each iteration.
+In the following implementation we start with $\mathrm{B} = 10$ and increase $\mathrm{B}$ after each each iteration.
 
 ```{.cpp file=factorization_p_minus_1}
 long long pollards_p_minus_1(long long n) {

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/algebra/linear-diophantine-equation.md b/src/algebra/linear-diophantine-equation.md
@@ -63,7 +63,7 @@ $$a x_g + b y_g = g$$
 
 If $c$ is divisible by $g = \gcd(a, b)$, then the given Diophantine equation has a solution, otherwise it does not have any solution. The proof is straight-forward: a linear combination of two numbers is divisible by their common divisor.
 
-Now supposed that $c$ is divisible by $g$, then we have:
+Now suppose that $c$ is divisible by $g$, then we have:
 
 $$a \cdot x_g \cdot \frac{c}{g} + b \cdot y_g \cdot \frac{c}{g} = c$$
 

diff --git a/src/algebra/polynomial.md b/src/algebra/polynomial.md
@@ -192,7 +192,7 @@ This algorithm was mentioned in [Schönhage's article](http://algo.inria.fr/semi
 
 $$A^{-1}(x) \equiv \frac{1}{A(x)} \equiv \frac{A(-x)}{A(x)A(-x)} \equiv \frac{A(-x)}{T(x^2)} \pmod{x^k}$$
 
-Note that $T(x)$ can be computed with a single multiplication, after which we're only interested in the first half of coefficients of its inverse series. This effectively reduces the initial problem of computing $A^{-1} \pmod{x^k}$ to computing $T^{-1} \pmod{x^{\lfloor k / 2 \rfloor}}$.
+Note that $T(x)$ can be computed with a single multiplication, after which we're only interested in the first half of coefficients of its inverse series. This effectively reduces the initial problem of computing $A^{-1} \pmod{x^k}$ to computing $T^{-1} \pmod{x^{\lceil k / 2 \rceil}}$.
 
 The complexity of this method can be estimated as
 

diff --git a/src/combinatorics/burnside.md b/src/combinatorics/burnside.md
@@ -271,3 +271,12 @@ int solve(int n, int m) {
 * [CSES - Counting Grids](https://cses.fi/problemset/task/2210)
 * [Codeforces - Buildings](https://codeforces.com/gym/101873/problem/B)
 * [CS Academy - Cube Coloring](https://csacademy.com/contest/beta-round-8/task/cube-coloring/)
+* [Codeforces - Side Transmutations](https://codeforces.com/contest/1065/problem/E)
+* [LightOJ - Necklace](https://vjudge.net/problem/LightOJ-1419)
+* [POJ - Necklace of Beads](http://poj.org/problem?id=1286)
+* [CodeChef - Lucy and Flowers](https://www.codechef.com/problems/DECORATE)
+* [HackerRank - Count the Necklaces](https://www.hackerrank.com/contests/infinitum12/challenges/count-the-necklaces)
+* [POJ - Magic Bracelet](http://poj.org/problem?id=2888)
+* [SPOJ - Sorting Machine](https://www.spoj.com/problems/SRTMACH/)
+* [Project Euler - Pizza Toppings](https://projecteuler.net/problem=281)
+* [ICPC 2011 SERCP - Alphabet Soup](https://basecamp.eolymp.com/tr/problems/3064)
diff --git a/src/data_structures/stack_queue_modification.md b/src/data_structures/stack_queue_modification.md
@@ -11,7 +11,7 @@ first we will modify a stack in a way that allows us to find the smallest elemen
 
 ## Stack modification
 
-We want to modify the stack data structure in such a way, that it possible to find the smallest element in the stack in $O(1)$ time, while maintaining the same asymptotic behavior for adding and removing elements from the stack.
+We want to modify the stack data structure in such a way, that it is possible to find the smallest element in the stack in $O(1)$ time, while maintaining the same asymptotic behavior for adding and removing elements from the stack.
 Quick reminder, on a stack we only add and remove elements on one end.
 
 To do this, we will not only store the elements in the stack, but we will store them in pairs: the element itself and the minimum in the stack starting from this element and below.
@@ -187,5 +187,6 @@ Since all operations with the queue are performed in constant time on average, t
 
 ## Practice Problems
 * [Queries with Fixed Length](https://www.hackerrank.com/challenges/queries-with-fixed-length/problem)
+* [Sliding Window Minimum](https://cses.fi/problemset/task/3221)
 * [Binary Land](https://www.codechef.com/MAY20A/problems/BINLAND)
 
diff --git a/src/data_structures/treap.md b/src/data_structures/treap.md
@@ -92,7 +92,7 @@ Alternatively, insert can be done by splitting the initial treap on $X$ and doin
 <img src="https://upload.wikimedia.org/wikipedia/commons/6/62/Treap_erase.svg" width="500px"/>
 </center>
 
-Implementation of **Erase ($X$)** is also clear. First we descend in the tree (as in a regular binary search tree by $X$), looking for the element we want to delete. Once the node is found, we call **Merge** on it children and put the return value of the operation in the place of the element we're deleting.
+Implementation of **Erase ($X$)** is also clear. First we descend in the tree (as in a regular binary search tree by $X$), looking for the element we want to delete. Once the node is found, we call **Merge** on its children and put the return value of the operation in the place of the element we're deleting.
 
 Alternatively, we can factor out the subtree holding $X$ with $2$ split operations and merge the remaining treaps (see the picture).
 

diff --git a/src/geometry/basic-geometry.md b/src/geometry/basic-geometry.md
@@ -180,7 +180,7 @@ double angle(point2d a, point2d b) {
 ```
 
 To see the next important property we should take a look at the set of points $\mathbf r$ for which $\mathbf r\cdot \mathbf a = C$ for some fixed constant $C$.
-You can see that this set of points is exactly the set of points for which the projection onto $\mathbf a$ is the point $C \cdot \dfrac{\mathbf a}{|\mathbf a|}$ and they form a hyperplane orthogonal to $\mathbf a$.
+You can see that this set of points is exactly the set of points for which the projection onto $\mathbf a$ is the point $C \cdot \dfrac{\mathbf a}{|\mathbf a| ^ 2}$ and they form a hyperplane orthogonal to $\mathbf a$.
 You can see the vector $\mathbf a$ alongside with several such vectors having same dot product with it in 2D on the picture below:
 
 <div style="text-align: center;">