You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The goal of this project is to translate the wonderful resource
10
-
[http://e-maxx.ru/algo](http://e-maxx.ru/algo) which provides descriptions of many algorithms
10
+
[https://e-maxx.ru/algo](https://e-maxx.ru/algo) which provides descriptions of many algorithms
11
11
and data structures especially popular in field of competitive programming.
12
12
Moreover we want to improve the collected knowledge by extending the articles
13
13
and adding new articles to the collection.
@@ -16,6 +16,7 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
16
16
17
17
## Changelog
18
18
19
+
- June 26, 2023: Added automatic RSS feeds for [new articles](https://cp-algorithms.com/feed_rss_created.xml) and [updates in articles](https://cp-algorithms.com/feed_rss_updated.xml).
19
20
- December 20, 2022: The repository name and the owning organizations were renamed! Now the repo is located at [https://github.com/cp-algorithms/cp-algorithms](https://github.com/cp-algorithms/cp-algorithms). It is recommended to update the upstream link in your local repositories, if you have any.
20
21
- October 31, 2022: It is now possible to select and copy $\LaTeX$ source code of formulas within the articles.
21
22
- June 8, 2022: Tags are enabled. Each article is now marked whether it is translated or original, overall tag info is present in the [tag index](https://cp-algorithms.com/tags.html). For translated articles, clicking on `From: X` tag would lead to the original article.
@@ -25,6 +26,8 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
25
26
26
27
### New articles
27
28
29
+
- (10 September 2023) [Tortoise and Hare Algorithm](https://cp-algorithms.com/others/tortoise_and_hare.html)
30
+
- (12 July 2023) [Finding faces of a planar graph](https://cp-algorithms.com/geometry/planar.html)
28
31
- (18 April 2023) [Bit manipulation](https://cp-algorithms.com/algebra/bit-manipulation.html)
29
32
- (17 October 2022) [Binary Search](https://cp-algorithms.com/num_methods/binary_search.html)
30
33
- (17 October 2022) [MEX (Minimum Excluded element in an array)](https://cp-algorithms.com/sequences/mex.html)
Copy file name to clipboardExpand all lines: mkdocs.yml
+7-2Lines changed: 7 additions & 2 deletions
Original file line number
Diff line number
Diff line change
@@ -1,4 +1,6 @@
1
1
site_name: Algorithms for Competitive Programming
2
+
site_url: https://cp-algorithms.com
3
+
site_description: 'The goal of this project is to translate the wonderful resource http://e-maxx.ru/algo which provides descriptions of many algorithms and data structures especially popular in field of competitive programming. Moreover we want to improve the collected knowledge by extending the articles and adding new articles to the collection.'
Copy file name to clipboardExpand all lines: src/algebra/bit-manipulation.md
+2-2Lines changed: 2 additions & 2 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -116,7 +116,7 @@ $1 \ll x$ is a number with only the $x$-th bit set, while $\sim(1 \ll x)$ is a n
116
116
117
117
### Check if a bit is set
118
118
119
-
The value of the $x$-th bit can be by shifting the number $x$ positions to the right, the $x$-th bit is the units place, therefore we can extract it by performing a bitwise & with 1
119
+
The value of the $x$-th bit can be checked by shifting the number $x$ positions to the right, so that the $x$-th bit is at the unit place, after which we can extract it by performing a bitwise & with 1.
Copy file name to clipboardExpand all lines: src/algebra/discrete-log.md
+2-2Lines changed: 2 additions & 2 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -47,7 +47,7 @@ This problem can be solved using the meet-in-the-middle method as follows:
47
47
48
48
## Complexity
49
49
50
-
We can calculate $f_1(p)$ in $O(\log m)$ using the [binary exponentation algorithm](binary-exp.md). Similarly for $f_2(q)$.
50
+
We can calculate $f_1(p)$ in $O(\log m)$ using the [binary exponentiation algorithm](binary-exp.md). Similarly for $f_2(q)$.
51
51
52
52
In the first step of the algorithm, we need to calculate $f_1$ for every possible argument $p$ and then sort the values. Thus, this step has complexity:
53
53
@@ -107,7 +107,7 @@ Internally, `map` uses a red-black tree to store values.
107
107
Thus this code is a little bit slower than if we had used an array and binary searched, but is much easier to write.
108
108
109
109
Notice that our code assumes $0^0 = 1$, i.e. the code will compute $0$ as solution for the equation $0^x \equiv 1 \pmod m$ and also as solution for $0^x \equiv 0 \pmod 1$.
110
-
This is an often used convention in algebra, but it's also not univerally accepted in all areas.
110
+
This is an often used convention in algebra, but it's also not universally accepted in all areas.
111
111
Sometimes $0^0$ is simply undefined.
112
112
If you don't like our convention, then you need to handle the case $a=0$ separately:
Copy file name to clipboardExpand all lines: src/algebra/factorization.md
+1-1Lines changed: 1 addition & 1 deletion
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -271,7 +271,7 @@ In each iteration the first pointer advances to the next element, but the second
271
271
It's not hard to see, that if there exists a cycle, the second pointer will make at least one full cycle and then meet the first pointer during the next few cycle loops.
272
272
If the cycle length is $\lambda$ and the $\mu$ is the first index at which the cycle starts, then the algorithm will run in $O(\lambda + \mu)$ time.
273
273
274
-
This algorithm is also known as **tortoise and the hare algorithm**, based on the tale in which a tortoise (here a slow pointer) and a hare (here a faster pointer) make a race.
274
+
This algorithm is also known as the [Tortoise and Hare algorithm](../others/tortoise_and_hare.md), based on the tale in which a tortoise (here a slow pointer) and a hare (here a faster pointer) make a race.
275
275
276
276
It is actually possible to determine the parameter $\lambda$ and $\mu$ using this algorithm (also in $O(\lambda + \mu)$ time and $O(1)$ space), but here is just the simplified version for finding the cycle at all.
277
277
The algorithm and returns true as soon as it detects a cycle.
Copy file name to clipboardExpand all lines: src/algebra/garners-algorithm.md
+1-1Lines changed: 1 addition & 1 deletion
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -19,7 +19,7 @@ A mixed radix representation is a positional numeral system, that's a generaliza
19
19
For instance the decimal numeral system is a positional numeral system with the radix (or base) 10.
20
20
Every a number is represented as a string of digits $d_1 d_2 d_3 \dots d_n$ between $0$ and $9$, and
21
21
E.g. the string $415$ represents the number $4 \cdot 10^2 + 1 \cdot 10^1 + 5 \cdot 10^0$.
22
-
In general the string of digits $d_1 d_2 d_3 \dots d_n$ represents the number $d_1 b^{n-1} + d_2 b^{n-2} + \cdots + d_n b^0$ in the positional numberal system with radix $b$.
22
+
In general the string of digits $d_1 d_2 d_3 \dots d_n$ represents the number $d_1 b^{n-1} + d_2 b^{n-2} + \cdots + d_n b^0$ in the positional numeral system with radix $b$.
23
23
24
24
In a mixed radix system, we don't have one radix any more. The base varies from position to position.
Copy file name to clipboardExpand all lines: src/algebra/module-inverse.md
+20-15Lines changed: 20 additions & 15 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -16,7 +16,7 @@ $$a \cdot x \equiv 1 \mod m.$$
16
16
We will also denote $x$ simply with $a^{-1}$.
17
17
18
18
We should note that the modular inverse does not always exist. For example, let $m = 4$, $a = 2$.
19
-
By checking all possible values modulo $m$ is should become clear that we cannot find $a^{-1}$ satisfying the above equation.
19
+
By checking all possible values modulo $m$, it should become clear that we cannot find $a^{-1}$ satisfying the above equation.
20
20
It can be proven that the modular inverse exists if and only if $a$ and $m$ are relatively prime (i.e. $\gcd(a, m) = 1$).
21
21
22
22
In this article, we present two methods for finding the modular inverse in case it exists, and one method for finding the modular inverse for all numbers in linear time.
@@ -77,32 +77,37 @@ From these results, we can easily find the modular inverse using the [binary exp
77
77
78
78
Even though this method is easier to understand than the method described in previous paragraph, in the case when $m$ is not a prime number, we need to calculate Euler phi function, which involves factorization of $m$, which might be very hard. If the prime factorization of $m$ is known, then the complexity of this method is $O(\log m)$.
79
79
80
-
## Finding the modular inverse using Euclidean Division
## Finding the modular inverse for prime moduli using Euclidean Division
81
82
82
-
Given that $m > i$ (or we can modulo to make it smaller in 1 step), according to [Euclidean Division](https://en.wikipedia.org/wiki/Euclidean_division)
83
+
Given a prime modulus $m > a$ (or we can apply modulo to make it smaller in 1 step), according to [Euclidean Division](https://en.wikipedia.org/wiki/Euclidean_division)
83
84
84
-
$$m = k \cdot i + r$$
85
+
$$m = k \cdot a + r$$
85
86
86
-
where $k = \left\lfloor \frac{m}{i} \right\rfloor$ and $r = m \bmod i$, then
87
+
where $k = \left\lfloor \frac{m}{a} \right\rfloor$ and $r = m \bmod a$, then
87
88
88
89
$$
89
90
\begin{align*}
90
-
& \implies & 0 & \equiv k \cdot i + r & \mod m \\
91
-
& \iff & r & \equiv -k \cdot i & \mod m \\
92
-
& \iff & r \cdot i^{-1} & \equiv -k & \mod m \\
93
-
& \iff & i^{-1} & \equiv -k \cdot r^{-1} & \mod m
91
+
& \implies & 0 & \equiv k \cdot a + r & \mod m \\
92
+
& \iff & r & \equiv -k \cdot a & \mod m \\
93
+
& \iff & r \cdot a^{-1} & \equiv -k & \mod m \\
94
+
& \iff & a^{-1} & \equiv -k \cdot r^{-1} & \mod m
94
95
\end{align*}
95
96
$$
96
97
97
-
From there we can have the following recursive function (in C++) for computing the modular inverse for number $i$ with respect to module $m$
98
+
Note that this reasoning does not hold if $m$ is not prime, since the existence of $a^{-1}$ does not imply the existence of $r^{-1}$
99
+
in the general case. To see this, lets try to calculate $5^{-1}$ modulo $12$ with the above formula. We would like to arrive at $5$,
100
+
since $5 \cdot 5 \equiv 1 \bmod 12$. However, $12 = 2 \cdot 5 + 2$, and we have $k=2$ and $r=2$, with $2$ being not invertible modulo $12$.
101
+
102
+
If the modulus is prime however, all $a$ with $0 < a < m$ are invertible modulo $m$, and we can have the following recursive function (in C++) for computing the modular inverse for number $a$ with respect to $m$
98
103
99
104
```{.cpp file=modular_inverse_euclidean_division}
100
-
intinv(int i) {
101
-
return i <= 1 ? i : m - (long long)(m/i) * inv(m % i) % m;
105
+
intinv(int a) {
106
+
return a <= 1 ? a : m - (long long)(m/a) * inv(m % a) % m;
102
107
}
103
108
```
104
109
105
-
The exact time complexity of the this recursion is not known. It's is somewhere between $O(\frac{\log m}{\log\log m})$ and $O(n^{\frac{1}{3} - \frac{2}{177} + \epsilon})$.
110
+
The exact time complexity of the this recursion is not known. It's is somewhere between $O(\frac{\log m}{\log\log m})$ and $O(m^{\frac{1}{3} - \frac{2}{177} + \epsilon})$.
106
111
See [On the length of Pierce expansions](https://arxiv.org/abs/2211.08374).
107
112
In practice this implementation is fast, e.g. for the modulus $10^9 + 7$ it will always finish in less than 50 iterations.
108
113
@@ -111,8 +116,8 @@ Applying this formula, we can also precompute the modular inverse for every numb
0 commit comments