Skip to content

Commit bdee148

Browse files
ProxihoxProxihox
committed
2 parents bee2358 + 4bb7a0d commit bdee148

40 files changed

Lines changed: 345 additions & 95 deletions

‎.github/workflows/build.yml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ jobs:
1919
- name: Set up Python
2020
uses: actions/setup-python@v5.2.0
2121
with:
22-
python-version: '3.8'
22+
python-version: '3.11'
2323
- name: Install mkdocs-material
2424
run: |
2525
scripts/install-mkdocs.sh

‎mkdocs.yml‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,6 @@ theme:
2222
icon:
2323
repo: fontawesome/brands/github
2424
features:
25-
- navigation.tabs
2625
- toc.integrate
2726
- search.suggest
2827
- content.code.copy
@@ -57,12 +56,13 @@ markdown_extensions:
5756
permalink: true
5857

5958
plugins:
59+
- toggle-sidebar:
60+
toggle_button: all
6061
- mkdocs-simple-hooks:
6162
hooks:
6263
on_env: "hooks:on_env"
6364
- search
64-
- tags:
65-
tags_file: tags.md
65+
- tags
6666
- literate-nav:
6767
nav_file: navigation.md
6868
- git-revision-date-localized:

‎scripts/install-mkdocs.sh‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
pip install \
44
"mkdocs-material>=9.0.2" \
5+
mkdocs-toggle-sidebar-plugin \
56
mkdocs-macros-plugin \
67
mkdocs-literate-nav \
78
mkdocs-git-authors-plugin \

‎src/algebra/factorization.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -246,7 +246,9 @@ If $p$ is smaller than $\sqrt{n}$, the repetition will likely start in $O(\sqrt[
246246
Here is a visualization of such a sequence $\{x_i \bmod p\}$ with $n = 2206637$, $p = 317$, $x_0 = 2$ and $f(x) = x^2 + 1$.
247247
From the form of the sequence you can see very clearly why the algorithm is called Pollard's $\rho$ algorithm.
248248

249-
<center>![Pollard's rho visualization](pollard_rho.png)</center>
249+
<div style="text-align: center;">
250+
<img src="pollard_rho.png" alt="Pollard's rho visualization">
251+
</div>
250252

251253
Yet, there is still an open question.
252254
How can we exploit the properties of the sequence $\{x_i \bmod p\}$ to our advantage without even knowing the number $p$ itself?

‎src/algebra/fibonacci-numbers.md‎

Lines changed: 57 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,8 @@ Fibonacci numbers possess a lot of interesting properties. Here are a few of the
2222

2323
$$F_{n-1} F_{n+1} - F_n^2 = (-1)^n$$
2424

25+
>This can be proved by induction. A one-line proof by Knuth comes from taking the determinant of the 2x2 matrix form below.
26+
2527
* The "addition" rule:
2628

2729
$$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
116118
117119
### Matrix form
118120
119-
It is easy to prove the following relation:
121+
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:
120122
121-
$$\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}$$
123+
$$
124+
\begin{pmatrix}
125+
1 & 1 \\
126+
1 & 0
127+
\end{pmatrix}
128+
\begin{pmatrix}
129+
F_n \\
130+
F_{n-1}
131+
\end{pmatrix}
132+
=
133+
\begin{pmatrix}
134+
F_n + F_{n-1} \\
135+
F_{n}
136+
\end{pmatrix}
137+
=
138+
\begin{pmatrix}
139+
F_{n+1} \\
140+
F_{n}
141+
\end{pmatrix}
142+
$$
143+
144+
This lets us treat iterating the recurrence as repeated matrix multiplication, which has nice properties. In particular,
145+
146+
$$
147+
\begin{pmatrix}
148+
1 & 1 \\
149+
1 & 0
150+
\end{pmatrix}^n
151+
\begin{pmatrix}
152+
F_1 \\
153+
F_0
154+
\end{pmatrix}
155+
=
156+
\begin{pmatrix}
157+
F_{n+1} \\
158+
F_{n}
159+
\end{pmatrix}
160+
$$
161+
162+
where $F_1 = 1, F_0 = 0$.
163+
In fact, since
164+
165+
$$
166+
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
167+
= \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}
168+
$$
169+
170+
we can use the matrix directly:
171+
172+
$$
173+
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n
174+
= \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}
175+
$$
122176
123-
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))
177+
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))
124178
125179
```{.cpp file=fibonacci_matrix}
126180
struct matrix {

‎src/algebra/sieve-of-eratosthenes.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,9 @@ And we continue this procedure until we have processed all numbers in the row.
1919

2020
In the following image you can see a visualization of the algorithm for computing all prime numbers in the range $[1; 16]$. It can be seen, that quite often we mark numbers as composite multiple times.
2121

22-
<center>![Sieve of Eratosthenes](sieve_eratosthenes.png)</center>
22+
<div style="text-align: center;">
23+
<img src="sieve_eratosthenes.png" alt="Sieve of Eratosthenes">
24+
</div>
2325

2426
The idea behind is this:
2527
A number is prime, if none of the smaller prime numbers divides it.

‎src/combinatorics/burnside.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -266,3 +266,8 @@ int solve(int n, int m) {
266266
return sum / s.size();
267267
}
268268
```
269+
## Practice Problems
270+
* [CSES - Counting Necklaces](https://cses.fi/problemset/task/2209)
271+
* [CSES - Counting Grids](https://cses.fi/problemset/task/2210)
272+
* [Codeforces - Buildings](https://codeforces.com/gym/101873/problem/B)
273+
* [CS Academy - Cube Coloring](https://csacademy.com/contest/beta-round-8/task/cube-coloring/)

‎src/data_structures/fenwick.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -128,7 +128,9 @@ where $|$ is the bitwise OR operator.
128128
The following image shows a possible interpretation of the Fenwick tree as tree.
129129
The nodes of the tree show the ranges they cover.
130130

131-
<center>![Binary Indexed Tree](binary_indexed_tree.png)</center>
131+
<div style="text-align: center;">
132+
<img src="binary_indexed_tree.png" alt="Binary Indexed Tree">
133+
</div>
132134

133135
## Implementation
134136

‎src/dynamic_programming/divide-and-conquer-dp.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -113,7 +113,7 @@ both!
113113
- [SPOJ - LARMY](https://www.spoj.com/problems/LARMY/)
114114
- [SPOJ - NKLEAVES](https://www.spoj.com/problems/NKLEAVES/)
115115
- [Timus - Bicolored Horses](https://acm.timus.ru/problem.aspx?space=1&num=1167)
116-
- [USACO - Circular Barn](http://www.usaco.org/index.php?page=viewproblem2&cpid=616)
116+
- [USACO - Circular Barn](https://usaco.org/index.php?page=viewproblem2&cpid=626)
117117
- [UVA - Arranging Heaps](https://onlinejudge.org/external/125/12524.pdf)
118118
- [UVA - Naming Babies](https://onlinejudge.org/external/125/12594.pdf)
119119

‎src/dynamic_programming/knuth-optimization.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -77,7 +77,7 @@ $$
7777
\sum\limits_{i=1}^N \sum\limits_{j=i}^{N-1} [opt(i+1,j+1)-opt(i,j)].
7878
$$
7979

80-
As you see, most of the terms in this expression cancel each other out, except for positive terms with $j=N$ and negative terms with $i=1$. Thus, the whole sum can be estimated as
80+
As you see, most of the terms in this expression cancel each other out, except for positive terms with $j=N-1$ and negative terms with $i=1$. Thus, the whole sum can be estimated as
8181

8282
$$
8383
\sum\limits_{k=1}^N[opt(k,N)-opt(1,k)] = O(n^2),

0 commit comments

Comments
 (0)