8000 Merge branch 'main' into patch-1 · cp-algorithms/cp-algorithms@38982cb · GitHub
[go: up one dir, main page]
Skip to content
8000

Commit 38982cb

Browse files
adamant-pwnadamant-pwn
authored
Merge branch 'main' into patch-1
2 parents cbb7b39 + 9a0a87b commit 38982cb

File tree

8 files changed

+38
-20
lines changed

8 files changed

+38
-20
lines changed

‎.github/workflows/build.yml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ jobs:
1212

1313
steps:
1414
- name: Checkout repository
15-
uses: actions/checkout@v3
15+
uses: actions/checkout@v4
1616
with:
1717
fetch-depth: 0
1818
submodules: recursive

‎.github/workflows/delete-preview.yml

Lines changed: 2 additions & 2 deletions
8000
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,15 @@
11
name: Delete PR Preview
22

33
on:
4-
pull_request:
4+
pull_request_target:
55
types: [closed]
66

77
jobs:
88
delete_pr_preview:
99
runs-on: ubuntu-latest
1010
steps:
1111
- name: Checkout gh-pages branch
12-
uses: actions/checkout@v3
12+
uses: actions/checkout@v4
1313
with:
1414
ref: gh-pages
1515

‎.github/workflows/deploy-cloud-function.yml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@ jobs:
1010
runs-on: ubuntu-latest
1111
steps:
1212
- name: Checkout repository
13-
uses: actions/checkout@v3
13+
uses: actions/checkout@v4
1414

1515
- uses: dorny/paths-filter@v2
1616
id: changes

‎.github/workflows/deploy-prod.yml

Lines changed: 14 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ jobs:
1212
if: github.event.workflow_run.conclusion == 'success' && github.event.workflow_run.event == 'push'
1313
steps:
1414
- name: Checkout repository
15-
uses: actions/checkout@v3
15+
uses: actions/checkout@v4
1616

1717
- name: Download pages
1818
uses: actions/download-artifact@v4
@@ -49,7 +49,7 @@ jobs:
4949
if: github.event.workflow_run.conclusion == 'success'
5050
steps:
5151
- name: Checkout repository
52-
uses: actions/checkout@v3
52+
uses: actions/checkout@v4
5353

5454
- name: Download pages
5555
uses: actions/download-artifact@v4
@@ -75,13 +75,19 @@ jobs:
7575
publish_branch: gh-pages
7676
destination_dir: ${{ steps.get-pr-number.outputs.pr_number }}
7777

78-
78+
- name: Find PR comment
79+
uses: peter-evans/find-comment@v3
80+
id: fc
81+
with:
82+
issue-number: ${{ steps.get-pr-number.outputs.pr_number }}
83+
comment-author: github-actions[bot]
84+
body-includes: Preview the changes for PR
85+
7986
- name: Create or update PR comment
8087
if: steps.get-pr-number.outputs.pr_number != 'main'
81-
uses: peter-evans/create-or-update-comment@v3
88+
uses: peter-evans/create-or-update-comment@v4
8289
with:
83-
token: ${{ github.token }}
90+
comment-id: ${{ steps.fc.outputs.comment-id }}
8491
issue-number: ${{ steps.get-pr-number.outputs.pr_number }}
85-
body: 'Preview the changes for PR #${{ steps.get-pr-number.outputs.pr_number }} (${{ github.event.workflow_run.head_sha }}) [here](https://gh.cp-algorithms.com/${{ steps.get-pr-number.outputs.pr_number }}/).'
86-
body-includes: 'Preview the changes for PR'
87-
mode: replace
92+
b 6D40 ody: 'Preview the changes for PR #${{ steps.get-pr-number.outputs.pr_number }} (for commit ${{ github.event.workflow_run.head_sha }}) at https://gh.cp-algorithms.com/${{ steps.get-pr-number.outputs.pr_number }}/.'
93+
edit-mode: replace

‎.github/workflows/test.yml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ jobs:
1111

1212
steps:
1313
- name: Checkout repository
14-
uses: actions/checkout@v3
14+
uses: actions/checkout@v4
1515
- name: Set up Python
1616
uses: actions/setup-python@v2
1717
with:

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,8 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
1616

1717
## Changelog
1818

19+
- October, 2024: Welcome new maintainers: [jxu](https://github.com/jxu), [mhayter](https://github.com/mhayter) and [kostero](https://github.com/kostero)!
20+
- 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/).
1921
- July 16, 2024: Major overhaul of the [Finding strongly connected components / Building condensation graph](https://cp-algorithms.com/graph/strongly-connected-components.html) article.
2022
- 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).
2123
- 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.

‎src/algebra/linear-diophantine-equation.md

Lines changed: 11 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -27,10 +27,10 @@ A degenerate case that need to be taken care of is when $a = b = 0$. It is easy
2727

2828
When $a \neq 0$ and $b \neq 0$, the equation $ax+by=c$ can be equivalently treated as either of the following:
2929

30-
\begin{gather}
31-
ax \equiv c \pmod b,\newline
32-
by \equiv c \pmod a.
33-
\end{gather}
30+
\begin{align}
31+
ax &\equiv c \pmod b \\
32+
by &\equiv c \pmod a
33+
\end{align}
3434

3535
Without loss of generality, assume that $b \neq 0$ and consider the first equation. When $a$ and $b$ are co-prime, the solution to it is given as
3636

@@ -51,6 +51,12 @@ y = \frac{c-ax}{b}.
5151

5252
## Algorithmic solution
5353

54+
**Bézout's lemma** (also called Bézout's identity) is a useful result that can be used to understand the following solution.
55+
56+
> Let $g = \gcd(a,b)$. Then there exist integers $x,y$ such that $ax + by = g$.
57+
>
58+
> Moreover, $g$ is the least such positive integer that can be written as $ax + by$; all integers of the form $ax + by$ are multiples of $g$.
59+
5460
To find one solution of the Diophantine equation with 2 unknowns, you can use the [Extended Euclidean algorithm](extended-euclid-algorithm.md). First, assume that $a$ and $b$ are non-negative. When we apply Extended Euclidean algorithm for $a$ and $b$, we can find their greatest common divisor $g$ and 2 numbers $x_g$ and $y_g$ such that:
5561

5662
$$a x_g + b y_g = g$$
@@ -119,7 +125,7 @@ $$y = y_0 - k \cdot \frac{a}{g}$$
119125
120126
are solutions of the given Diophantine equation.
121127
122-
Moreover, this is the set of all possible solutions of the given Diophantine equation.
128+
Since the equation is linear, all solutions lie on the same line, and by the definition of $g$ this is the set of all possible solutions of the given Diophantine equation.
123129
124130
## Finding the number of solutions and the solutions in a given interval
125131

‎src/graph/dinic.md

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -106,7 +106,7 @@ struct Dinic {
106106
int v = q.front();
107107
q.pop();
108108
for (int id : adj[v]) {
109-
if (edges[id].cap - edges[id].flow < 1)
109+
if (edges[id].cap == edges[id].flow)
110110
continue;
111111
if (level[edges[id].u] != -1)
112112
continue;
@@ -125,7 +125,7 @@ struct Dinic {
125125
for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
126126
int id = adj[v][cid];
127127
int u = edges[id].u;
128-
if (level[v] + 1 != level[u] || edges[id].cap - edges[id].flow < 1)
128+
if (level[v] + 1 != level[u])
129129
continue;
130130
long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
131131
if (tr == 0)
@@ -154,3 +154,7 @@ struct Dinic {
154154
}
155155
};
156156
```
157+
158+
## Practice Problems
159+
160+
* [SPOJ: FASTFLOW](https://www.spoj.com/problems/FASTFLOW/)

0 commit comments

Comments
 (0)
0