8000 Temporary fix for image urls (#252) · cp-algorithms/cp-algorithms@f1ba66c · GitHub
[go: up one dir, main page]
Skip to content
8000

Commit f1ba66c

Browse files
jakobkoglerjakobkogler
committed
Temporary fix for image urls (#252)
1 parent c01d56b commit f1ba66c

File tree

13 files changed

+27
-27
lines changed

13 files changed

+27
-27
lines changed

‎src/combinatorics/inclusion-exclusion.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ $$\left|\bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq J\subseteq \\{1,2,\ld
2525

2626
Let the diagram show three sets $A$, $B$ and $C$:
2727

28-
![Venn diagram](&imgroot&/venn-inclusion-exclusion.png "Venn diagram")
28+
![Venn diagram](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/venn-inclusion-exclusion.png "Venn diagram")
2929

3030
Then the area of their union $A \cup B \cup C$ is equal to the sum of the areas $A$, $B$ and $C$ less double-covered areas $A \cap B$, $A \cap C$, $B \cap C$, but with the addition of the area covered by three sets $A \cap B \cap C$:
3131

‎src/data_structures/disjoint_set_union.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,7 @@ And the root of the tree will be the representative/leader of the set.
3232

3333
In the following image you can see the representation of such trees.
3434

35-
![Example-image of the set representation with trees](&imgroot&/DSU_example.png)
35+
![Example-image of the set representation with trees](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/DSU_example.png)
3636

3737
At the beginning every element starts as a single set, therefore each vertex is its own tree.
3838
Then we combine the set containing the element 1 and the set containing the element 2.
@@ -94,7 +94,7 @@ The trick is to make the paths for all those nodes shorter, by setting the paren
9494
You can see the operation in the following image.
9595
On the left there is a tree, and on the right side there is the compressed tree after calling `find_set(7)`, which shortens the paths for the visited nodes 7, 5, 3 and 2.
9696
97-
![Path compression of call `find_set(7)`](&imgroot&/DSU_path_compression.png)
97+
![Path compression of call `find_set(7)`](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/DSU_path_compression.png)
9898
9999
The new implementation of `find_set` is as follows:
100100

‎src/data_structures/segment_tree.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ This is why the data structure is called "Segment Tree", even though in most imp
4040

4141
Here is a visual representation of such a Segment Tree over the array $a = [1, 3, -2, 8, -7]$:
4242

43-
!["Sum Segment Tree"](&imgroot&/sum-segment-tree.png)
43+
!["Sum Segment Tree"](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/sum-segment-tree.png)
4444

4545
From this short description of the data structure, we can already conclude that a Segment Tree only requires a linear number of vertices.
4646
The first level of the tree contains a single note (the root), the second level will contain two vertices, in the third it will contain four vertices, until the number of vertices reaches $n$.
@@ -98,7 +98,7 @@ Again the array $a = [1, 3, -2, 8, -7]$ is used, and here we want to compute the
9898
The colored vertices will be visited, and we will use the precomputed values of the green vertices.
9999
This gives us the result $-2 + 1 = -1$.
100100

101-
!["Sum Segment Tree Query"](&imgroot&/sum-segment-tree-query.png)
101+
!["Sum Segment Tree Query"](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/sum-segment-tree-query.png)
102102

103103
Why is the complexity of this algorithm $O(\log n)$?
104104
To show this complexity we look at each level of the tree.
@@ -140,7 +140,7 @@ Again here is a visualization using the same array.
140140
Here we perform the update $a[2] = 3$.
141141
The green vertices are the vertices that we visit and update.
142142

143-
!["Sum Segment Tree Update"](&imgroot&/sum-segment-tree-update.png)
143+
!["Sum Segment Tree Update"](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/sum-segment-tree-update.png)
144144

145145
### Implementation ### {#implementation}
146146

‎src/demo-article.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,7 @@ $$E = mc^{2}$$
5151

5252
Small images could be pushed along with texts to the [/img](https://github.com/e-maxx-eng/e-maxx-eng/tree/master/img) subfolder. Let them be in `PNG` format and less than `200kb`. Then you can refer to them inside the article like this (see the source here):
5353

54-
![some image description](&imgroot&/search-bridge-formula.png)
54+
![some image description](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/search-bridge-formula.png)
5555

5656
Note that file name is prefixed with `imgroot` variable (in ampersands) which will expand to proper url prefix when shown at the site (so you need not know the precise prefix of github raw data). It would be good if you use it instead of full path urls.
5757

‎src/geometry/convex_hull_trick.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ Naive approach will give you $O(n^2)$ complexity which can be improved to $O(n \
1212

1313
Idea of this approach is to maintain a lower convex hull of linear functions. Actually it would be a bit more convenient to consider them not as linear functions but as points $(k;b)$ on the plane such that we will have to find the point which has the least dot product with a given point $(x;1)$, that is, for this point $kx+b$ is minimized which is the same as initial problem. Such minimum will necessarily be on lower convex envelope of these points as can be seen below:
1414

15-
<center> ![lower convex hull](&imgroot&/convex_hull_trick.png) </center>
15+
<center> ![lower convex hull](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/convex_hull_trick.png) </center>
1616

1717
One have to keep points in convex hull alongside with normal vectors of edges of convex hull. When you have $(x;1)$ query you'll have to find normal vector closest to it in terms of angles between them, then optimum linear function will correspond to one of its endpoints. To see that one should note that points having same dot product with $(x;1)$ lie on same line which is orthogonal to $(x;1)$ so optimum linear function will be the one in which tangent to convex hull which is collinear with normal to $(x;1)$ touches the hull. This point can be found as one such that normals of edges lying to the left and to the right of it are headed in different sides of $(x;1)$.
1818

@@ -72,7 +72,7 @@ Assume we're in some vertex corresponding to half-segment $[l;r)$ and the functi
7272
7373
Here is the illustration of what is going on in the vertex when we add new function:
7474
75-
<center>![Li Chao Tree vertex](&imgroot&/li_chao_vertex.png)</center>
75+
<center>![Li Chao Tree vertex](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/li_chao_vertex.png)</center>
7676
7777
Let's go to implementation now. Once again we will use complex numbers to keep linear functions.
7878

‎src/geometry/lattice-points.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,7 @@ Now we are interested only in points $(x;y)$ such that $\lfloor k \rfloor \cdot
3232
This amount is the same as the number of points such that $0 < y \leq (k - \lfloor k \rfloor) \cdot x + (b - \lfloor b \rfloor)$.
3333
So we reduced our problem to $k'= k - \lfloor k \rfloor$, $b' = b - \lfloor b \rfloor$ and both $k'$ and $b'$ less than $1$ now.
3434
Here is a picture, we just summed up blue points and subtracted the blue linear function from the black one to reduce problem to smaller values for $k$ and $b$:
35-
<center>![Subtracting floored linear function](&imgroot&/lattice.png)</center>
35+
<center>![Subtracting floored linear function](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/lattice.png)</center>
3636

3737
- $k < 1$ and $b < 1$.
3838
If $\lfloor k \cdot n + b\rfloor$ equals $0$, we can safely return $0$.
@@ -42,7 +42,7 @@ For this reference system we are interested in lattice points on the set
4242
$$\left\\{(x;y)~\bigg|~0 \leq x < \lfloor k \cdot n + b\rfloor,~ 0 < y \leq \dfrac{x+(k\cdot n+b)-\lfloor k\cdot n + b \rfloor}{k}\right\\}$$
4343
which returns us back to the case $k>1$.
4444
You can see new reference point $O'$ and axes $X'$ and $Y'$ in the picture below:
45-
<center>![New reference and axes](&imgroot&/mirror.png)</center>
45+
<center>![New reference and axes](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/mirror.png)</center>
4646
As you see, in new reference system linear function will have coefficient $\tfrac 1 k$ and its zero will be in the point $\lfloor k\cdot n + b \rfloor-(k\cdot n+b)$ which makes formula above correct.
4747

4848
## Complexity analysis

‎src/graph/2SAT.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ b \Rightarrow a & \lnot b \Rightarrow \lnot a & b \Rightarrow \lnot a & c \Right
3535

3636
You can see the implication graph in the following image:
3737

38-
<center>!["Implication Graph of 2-SAT example"](&imgroot&/2SAT.png)</center>
38+
<center>!["Implication Graph of 2-SAT example"](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/2SAT.png)</center>
3939

4040
It is worth paying attention to the property of the implication graph:
4141
if there is an edge $a \Rightarrow b$, then there also is an edge $\lnot b \Rightarrow \lnot a$.
@@ -55,7 +55,7 @@ The following image shows all strongly connected components for the example.
5555
As we can check easily, neither of the four components contain a vertex $x$ and its negation $\lnot x$, therefore the example has a solution.
5656
We will learn in the next paragraphs how to compute a valid assignment, but just for demonstration purposes the solution $a = \text{false}$, $b = \text{false}$, $c = \text{false}$ is given.
5757

58-
<center>!["Strongly Connected Components of the 2-SAT example"](&imgroot&/2SAT_SCC.png)</center>
58+
<center>!["Strongly Connected Components of the 2-SAT example"](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/2SAT_SCC.png)</center>
5959

6060
Now we construct the algorithm for finding the solution of the 2-SAT problem on the assumption that the solution exists.
6161

‎src/graph/edmonds_karp.md

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@ The source $s$ is origin of all the water, and the water can only drain in the s
3434

3535
The following image show a flow network.
3636
The first value of each edge represents the flow, which is initially 0, and the second value represents the capacity.
37-
<center>![Flow network](&imgroot&/Flow1.png)</center>
37+
<center>![Flow network](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow1.png)</center>
3838

3939
We value of a flow of a network is the sum of all flows that gets produced in source $s$, or equivalent or the flows that is consumed in the sink $t$.
4040
A **maximal flow** is a flow with the maximal possible value.
@@ -44,7 +44,7 @@ In the visualization with water pipes, the problem can be formulated in the foll
4444
how much water can we push through the pipes from the source to the sink.
4545

4646
The following image show the maximal flow in the flow network.
47-
<center>![Maximal flow](&imgroot&/Flow9.png)</center>
47+
<center>![Maximal flow](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow9.png)</center>
4848

4949
## Ford-Fulkerson method
5050

@@ -70,19 +70,19 @@ we update $f((u, v)) ~\text{+=}~ C$ and $f((v, u)) ~\text{-=}~ C$ for every edge
7070
Here is an example to demonstrate the method.
7171
We use the same flow network as above.
7272
Initially we start with a flow of 0.
73-
<center>![Flow network](&imgroot&/Flow1.png)</center>
73+
<center>![Flow network](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow1.png)</center>
7474

7575
We can find the path $s - A - B - t$ with the residual capacities 7, 5 and 8.
7676
Their minimum is 5, therefore we can increase the flow along this path by 5.
7777
This gives a flow of 5 for the network.
78-
<center>![First path](&imgroot&/Flow2.png) ![Network after first path](&imgroot&/Flow3.png)</center>
78+
<center>![First path](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow2.png) ![Network after first path](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow3.png)</center>
7979

8080
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.
8181
Therefore we can increase the flow by 3 and we get a flow of 8 for the network.
82-
<center>![Second path](&imgroot&/Flow4.png) ![Network after second path](&imgroot&/Flow5.png)</center>
82+
<center>![Second path](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow4.png) ![Network after second path](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow5.png)</center>
8383

8484
This time we find the path $s - D - C - B - t$ with the residual capacities 1, 2, 3 and 3, and we increase by 1.
85-
<center>![Third path](&imgroot&/Flow6.png) ![Network after third path](&imgroot&/Flow7.png)</center>
85+
<center>![Third path](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow6.png) ![Network after third path](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow7.png)</center>
8686

8787
This time we find the augmenting path $s - A - D - C - t$ with the residual capacities 2, 3, 1 and 2.
8888
We can increase by 1.
@@ -92,7 +92,7 @@ In the original flow network we are not allowed to send any flow from $A$ to $D$
9292
But because we already have a flow of 3 from $D$ to $A$ this is possible.
9393
The intuition of it is the following:
9494
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$.
95-
<center>![Fourth path](&imgroot&/Flow8.png) ![Network after fourth path](&imgroot&/Flow9.png)</center>
95+
<center>![Fourth path](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow8.png) ![Network after fourth path](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Flow9.png)</center>
9696

9797
Now it is impossible to find an augmenting path between $s$ and $t$, therefore this flow of $10$ is the maximal possible.
9898
We have found the maximal flow.
@@ -191,7 +191,7 @@ It says that the capacity of the maximum flow has to be equal to the capacity of
191191
In the following image you can see the minimum cut of the flow network we used earlier.
192192
It shows that the capacity of the cut $\\{s, A, D\\}$ and $\\{B, C, t\\}$ is $5 + 3 + 2 = 10$, which is equal to the maximum flow that we found.
193193
Other cuts will have a bigger capacity, like the capacity between $\\{s, A\\}$ and $\\{B, C, D, t\\}$ is $4 + 3 + 5 = 12$.
194-
<center>![Minimum cut](&imgroot&/Cut.png)</center>
194+
<center>![Minimum cut](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/Cut.png)</center>
195195
196196
A minimum cut can be found after performing a maximum flow computation using the Ford-Fulkerson method.
197197
One possible minimum cut is the following:

‎src/graph/lca.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ So the $\text{LCA}(v_1, v_2)$ can be uniquely determined by finding the vertex w
2727

2828
Let's illustrate this idea.
2929
Consider the following graph and the Euler tour with the corresponding heights:
30-
<center>![LCA_Euler_Tour](&imgroot&/LCA_Euler.png)</center>
30+
<center>![LCA_Euler_Tour](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/LCA_Euler.png)</center>
3131
$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|}
3232
\hline
3333
\text{Vertices:} & 1 & 2 & 5 & 2 & 6 & 2 & 1 & 3 & 1 & 4 & 7 & 4 & 1 \\\\ \hline

‎src/graph/lca_farachcoltonbender.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,7 @@ The LCA of two nodes $u$ and $v$ is the node between the occurrences of $u$ and
1717

1818
In the following picture you can see a possible Euler-Tour of a graph and in the list below you can see the visited nodes and their heights.
1919

20-
<center>![LCA_Euler_Tour](&imgroot&/LCA_Euler.png)</center>
20+
<center>![LCA_Euler_Tour](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/LCA_Euler.png)</center>
2121
$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|}
2222
\hline
2323
\text{Nodes:} & 1 & 2 & 5 & 2 & 6 & 2 & 1 & 3 & 1 & 4 & 7 & 4 & 1 \\\\ \hline

‎src/graph/mst_kruskal.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ This spanning tree is called a minimum spanning tree.
88

99
In the left image you can see a weighted undirected graph, and in the right image you can see the corresponding minimum spanning tree.
1010

11-
![Random graph](&imgroot&/MST_before.png) ![MST of this graph](&imgroot&/MST_after.png)
11+
![Random graph](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/MST_before.png) ![MST of this graph](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/MST_after.png)
1212

1313
This article will discuss few important facts associated with minimum spanning trees, and then will give the simplest implementation of Kruskal's algorithm for finding minimum spanning tree.
1414

‎src/graph/mst_prim.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ The spanning tree with the least weight is called a minimum spanning tree.
88

99
In the left image you can see a weighted undirected graph, and in the right image you can see the corresponding minimum spanning tree.
1010

11-
<center>![Random graph](&imgroot&/MST_before.png) ![MST of this graph](&imgroot&/MST_after.png)</center>
11+
<center>![Random graph](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/MST_before.png) ![MST of this graph](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/MST_after.png)</center>
1212

1313
It is easy to see that any spanning tree will necessarily contain $n-1$ edges.
1414

‎src/graph/rmq_linear.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ The array `A` will be partitioned into 3 parts: the prefix of the array up to th
1919
The root of the tree will be a node corresponding to the minimum element of the array `A`, the left subtree will be the Cartesian tree of the prefix, and the right subtree will be a Cartesian tree of the suffix.
2020

2121
In the following image you can see one array of length 10 and the corresponding Cartesian tree.
22-
<center>![Image of Cartesian Tree](&imgroot&/CartesianTree.png)</center>
22+
<center>![Image of Cartesian Tree](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/CartesianTree.png)</center>
2323

2424
The range minimum query `[l, r]` is equivalent to the lowest common ancestor query `[l', r']`, where `l'` is the node corresponding to the element `A[l]` and `r'` the node corresponding to the element `A[r]`.
2525
Indeed the node corresponding to the smallest element in the range has to be an ancestor of all nodes in the range, therefor also from `l'` and `r'`.
@@ -28,7 +28,7 @@ And is also has to be the lowest ancestor, because otherwise `l'` and `r'` would
2828

2929
In the following image you can see the LCA queries for the RMQ queries `[1, 3]` and `[5, 9]`.
3030
In the first query the LCA of the nodes `A[1]` and `A[3]` is the node corresponding to `A[2]` which has the value 2, and in the second query the LCA of `A[5]` and `A[9]` is the node corresponding to `A[8]` which has the value 3.
31-
<center>![LCA queries in the Cartesian Tree](&imgroot&/CartesianTreeLCA.png)</center>
31+
<center>![LCA queries in the Cartesian Tree](https://raw.githubusercontent.com/e-maxx-eng/e-maxx-eng/master/img/CartesianTreeLCA.png)</center>
3232

3333
Such a tree can be built in $O(N)$ time and the Farach-Colton and Benders algorithm can preprocess the tree in $O(N)$ and find the LCA in $O(1)$.
3434

0 commit comments

Comments
 (0)
0