10000 Merge branch 'main' into master · cp-algorithms/cp-algorithms@28db91b · GitHub
[go: up one dir, main page]
Skip to content

Commit 28db91b

Browse files
adamant-pwnadamant-pwn
authored
Merge branch 'main' into master
2 parents c278efa + 0bf15a6 commit 28db91b

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

50 files changed

+1012
-227
lines changed

‎.github/workflows/build.yml

Lines changed: 8 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,10 @@
11
name: Build
2-
on:
3-
push:
4-
branches:
5-
- 'master'
6-
pull_request:
2+
3+
on:
4+
workflow_call:
75

86
jobs:
9-
test:
7+
build:
108
runs-on: ubuntu-latest
119

1210
steps:
@@ -29,13 +27,13 @@ jobs:
2927
key: test-${{ github.event_name }}-github-users-v0.1
3028
- name: Build pages
3129
env:
32-
MKDOCS_GIT_COMMITTERS_APIKEY: ${{ secrets.PAT_API_KEY }}
33-
MKDOCS_ENABLE_GIT_REVISION_DATE: ${{ secrets.PAT_API_KEY && 'True' || 'False' }}
34-
MKDOCS_ENABLE_GIT_COMMITTERS: ${{ secrets.PAT_API_KEY && 'True' || 'False' }}
30+
MKDOCS_GIT_COMMITTERS_APIKEY: ${{ secrets.GITHUB_TOKEN }}
31+
MKDOCS_ENABLE_GIT_REVISION_DATE: ${{ secrets.GITHUB_TOKEN && 'True' || 'False' }}
32+
MKDOCS_ENABLE_GIT_COMMITTERS: ${{ secrets.GITHUB_TOKEN && 'True' || 'False' }}
3533
run: |
3634
mkdocs build --strict
3735
- name: Upload build pages as artifact
38-
uses: actions/upload-artifact@v2
36+
uses: actions/upload-artifact@v4
3937
with:
4038
name: page-build
4139
path: public/

‎.github/workflows/delete-preview.yml

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
name: Delete PR Preview
2+
3+
on:
4+
pull_request:
5+
types: [closed]
6+
7+
jobs:
8+
delete_pr_preview:
9+
runs-on: ubuntu-latest
10+
steps:
11+
- name: Checkout gh-pages branch
12+
uses: actions/checkout@v3
13+
with:
14+
ref: gh-pages
15+
16+
- name: Configure Git identity
17+
run: |
18+
git config --global user.name "github-actions[bot]"
19+
git config --global user.email "github-actions[bot]@users.noreply.github.com"
20+
21+
- name: Delete PR directory
22+
run: |
23+
PR_DIR=${{ github.event.pull_request.number }}
24+
git rm -r --ignore-unmatch "${PR_DIR}/" || echo "Directory not found"
25+
git commit -m "Delete preview for PR #${{ github.event.pull_request.number }}"
26+
git push origin gh-pages

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@ name: Deploy Cloud Function
33
on:
44
push:
55
branches:
6-
- master
6+
- main
77

88
jobs:
99
deploy_cloud_function:
@@ -20,7 +20,7 @@ jobs:
2020
- 'preview/**'
2121
2222
- id: 'auth'
23-
uses: 'google-github-actions/auth@v0'
23+
uses: 'google-github-actions/auth@v2.1.6'
2424
with:
2525
credentials_json: '${{ secrets.GCP_CREDENTIALS }}'
2626

‎.github/w F987 orkflows/deploy-prod.yml

Lines changed: 84 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -1,67 +1,48 @@
11
name: Deploy
22

3-
on:
4-
workflow_run:
5-
# `workflow_run` events have access to secrets
6-
workflows: [Build]
7-
types:
8-
- completed
3+
on:
4+
push:
5+
branches:
6+
- 'main'
7+
pull_request:
98

109
jobs:
10+
build:
11+
uses: ./.github/workflows/build.yml
12+
secrets: inherit
13+
1114
deploy_live_website:
1215
runs-on: ubuntu-latest
13-
if: >
14-
${{ github.event.workflow_run.event == 'pull_request' &&
15-
github.event.workflow_run.conclusion == 'success' }}
16+
needs: build
17+
if: github.event_name == 'push'
1618
steps:
17-
- name: "Get PR information"
19+
- name: Checkout
20+
uses: actions/checkout@v4
21+
22+
- name: Download pages
23+
uses: actions/download-artifact@v4
24+
with:
25+
name: page-build
26+
path: public
27+
28+
- name: Get PR information
1829
uses: potiuk/get-workflow-origin@751d47254ef9e8b5eef955e24e79305233702781
1930
id: source-run-info
2031
with:
2132
token: ${{ secrets.GITHUB_TOKEN }}
2233
sourceRunId: ${{ github.event.workflow_run.id }}
2334

24-
- name: Checkout repository
25-
uses: actions/checkout@v3
26-
27-
- name: 'Download artifact'
28-
uses: actions/github-script@v6
29-
with:
30-
script: |
31-
let allArtifacts = await github.rest.actions.listWorkflowRunArtifacts({
32-
owner: context.repo.owner,
33-
repo: context.repo.repo,
34-
run_id: context.payload.workflow_run.id,
35-
});
36-
let matchArtifact = allArtifacts.data.artifacts.filter((artifact) => {
37-
return artifact.name == "page-build"
38-
})[0];
39-
let download = await github.rest.actions.downloadArtifact({
40-
owner: context.repo.owner,
41-
repo: context.repo.repo,
42-
artifact_id: matchArtifact.id,
43-
archive_format: 'zip',
44-
});
45-
let fs = require('fs');
46-
fs.writeFileSync(`${process.env.GITHUB_WORKSPACE}/page-build.zip`, Buffer.from(download.data));
47-
48-
- run: |
49-
unzip page-build.zip -d public
50-
5135
- name: change URLs for large files
52-
if: ${{ steps.source-run-info.outputs.sourceEvent == 'push' && steps.source-run-info.outputs.targetBranch == 'master'}}
5336
shell: bash
5437
run: |
5538
sed -i 's|search/search_index.json|https://storage.googleapis.com/cp-algorithms/search_index.json|g' public/assets/javascripts/*.js
5639
5740
- id: 'auth'
58-
if: ${{ steps.source-run-info.outputs.sourceEvent == 'push' && steps.source-run-info.outputs.targetBranch == 'master'}}
59-
uses: 'google-github-actions/auth@v0'
41+
uses: 'google-github-actions/auth@v2.1.6'
6042
with:
6143
credentials_json: '${{ secrets.GCP_CREDENTIALS }}'
6244

6345
- uses: 'google-github-actions/upload-cloud-storage@v1'
64-
if: ${{ steps.source-run-info.outputs.sourceEvent == 'push' && steps.source-run-info.outputs.targetBranch == 'master'}}
6546
with:
6647
path: 'public/search/search_index.json'
6748
destination: 'cp-algorithms'
@@ -70,29 +51,77 @@ jobs:
7051
id: firebase-deploy
7152
if: env.FIREBASE_SERVICE_ACCOUNT
7253
env:
73-
PREVIEW_NAME: "preview-${{ steps.source-run-info.outputs.pullRequestNumber }}"
7454
LIVE_NAME: "live"
7555
FIREBASE_SERVICE_ACCOUNT: ${{ secrets.FIREBASE_SERVICE_ACCOUNT }}
7656
with:
7757
repoToken: "${{ secrets.GITHUB_TOKEN }}"
7858
firebaseServiceAccount: "${{ secrets.FIREBASE_SERVICE_ACCOUNT }}"
7959
projectId: cp-algorithms
80-
channelId: ${{ steps.source-run-info.outputs.sourceEvent == 'push' && steps.source-run-info.outputs.targetBranch == 'master' && env.LIVE_NAME || env.PREVIEW_NAME }}
60+
channelId: ${{ env.LIVE_NAME }}
8161

82-
- name: comment URL to PR
83-
if: ${{ steps.source-run-info.outputs.sourceEvent == 'pull_request' }}
62+
deploy_github_pages:
63+
runs-on: ubuntu-latest
64+
needs: build
65+
steps:
66+
- name: Checkout repository
67+
uses: actions/checkout@v3
68+
69+
- name: Download artifact
70+
uses: actions/download-artifact@v4
71+
with:
72+
name: page-build
73+
path: public
74+
75+
- name: Configure git
76+
run: |
77+
git config --global user.name "github-actions[bot]"
78+
git config --global user.email "github-actions[bot]@users.noreply.github.com"
79+
80+
- name: Deploy to gh-pages
81+
uses: peaceiris/actions-gh-pages@v3
82+
with:
83+
github_token: ${{ secrets.GITHUB_TOKEN }}
84+
publish_dir: ./public
85+
publish_branch: gh-pages
86+
destination_dir: ${{ github.event.pull_request.number || 'main' }}/
87+
88+
- name: Update or create preview comment
89+
if: github.event_name == 'pull_request'
8490
uses: actions/github-script@v6
8591
with:
8692
script: |
87-
const body = `Visit the preview URL for this PR (for commit ${{ steps.source-run-info.outputs.sourceHeadSha }}):
88-
89-
${{ steps.firebase-deploy.outputs.details_url }}
93+
const prNumber = ${{ github.event.pull_request.number }};
94+
const repo = context.repo.repo;
95+
const owner = context.repo.owner;
96+
const commitSha = context.payload.pull_request.head.sha;
97+
const baseUrl = `https://${owner}.github.io/${repo}/`;
98+
const previewUrl = `${baseUrl}${prNumber}/`;
99+
const body = `Preview the changes for PR #${prNumber} (${commitSha}) here: [${previewUrl}](${previewUrl})`;
100+
101+
// Retrieve comments for the PR to check if the comment already exists
102+
const { data: comments } = await github.rest.issues.listComments({
103+
owner: owner,
104+
repo: repo,
105+
issue_number: prNumber,
106+
});
90107

91-
(expires ${{ steps.firebase-deploy.outputs.expire_time }})`;
108+
// Look for an existing comment with the preview link
109+
const existingComment = comments.find(comment => comment.body.includes('Preview the changes for PR'));
92110

93-
github.rest.issues.createComment({
94-
issue_number: ${{ steps.source-run-info.outputs.pullRequestNumber }},
95-
owner: context.repo.owner,
96-
repo: context.repo.repo,
97-
body: body
98-
})
111+
if (existingComment) {
112+
// Update the existing comment
113+
await github.rest.issues.updateComment({
114+
owner: owner,
115+
repo: repo,
116+
comment_id: existingComment.id,
117+
body: body,
118+
});
119+
} else {
120+
// Create a new comment
121+
await github.rest.issues.createComment({
122+
issue_number: prNumber,
123+
owner: owner,
124+
repo: repo,
125+
body: body,
126+
});
127+
}

‎.github/workflows/test.yml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@ name: Test
22
on:
33
push:
44
branches:
5-
- 'master'
5+
- 'main'
66
pull_request:
77

88
jobs:

‎CONTRIBUTING.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -25,8 +25,8 @@ If you are unfamiliar with the workflow, read [Step-by-step guide to contributin
2525

2626
If you're making a new article or moving existing one to a different place, please make sure that your changes are reflected in
2727

28-
- The list of all articles in [navigation.md](https://github.com/cp-algorithms/cp-algorithms/blob/master/src/navigation.md);
29-
- The list of new articles in [README.md](https://github.com/cp-algorithms/cp-algorithms/blob/master/README.md) (if it is a new article).
28+
- The list of all articles in [navigation.md](https://github.com/cp-algorithms/cp-algorithms/blob/main/src/navigation.md);
29+
- The list of new articles in [README.md](https://github.com/cp-algorithms/cp-algorithms/blob/main/README.md) (if it is a new article).
3030

3131
## Syntax
3232

‎README.md

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
[![Contributors](https://img.shields.io/github/contributors/cp-algorithms/cp-algorithms.svg)](https://github.com/cp-algorithms/cp-algorithms/graphs/contributors)
44
[![Pull Requests](https://img.shields.io/github/issues-pr/cp-algorithms/cp-algorithms.svg)](https://github.com/cp-algorithms/cp-algorithms/pulls)
55
[![Closed Pull Requests](https://img.shields.io/github/issues-pr-closed/cp-algorithms/cp-algorithms.svg)](https://github.com/cp-algorithms/cp-algorithms/pulls?q=is%3Apr+is%3Aclosed)
6-
[![Build](https://img.shields.io/github/actions/workflow/status/cp-algorithms/cp-algorithms/test.yml)](https://github.com/cp-algorithms/cp-algorithms/actions?query=branch%3Amaster+workflow%3Atest)
6+
[![Build](https://img.shields.io/github/actions/workflow/status/cp-algorithms/cp-algorithms/test.yml)](https://github.com/cp-algorithms/cp-algorithms/actions?query=branch%3Amain+workflow%3Atest)
77
[![Translation Progress](https://img.shields.io/badge/trans C2EE lation_progress-85.2%25-yellowgreen.svg)](https://github.com/cp-algorithms/cp-algorithms/wiki/Translation-Progress)
88

99
The goal of this project is to translate the wonderful resource
@@ -16,16 +16,18 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
1616

1717
## Changelog
1818

19+
- July 16, 2024: Major overhaul of the [Finding strongly connected components / Building condensation graph](https://cp-algorithms.com/graph/strongly-connected-components.html) article.
1920
- 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).
2021
- 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.
2122
- October 31, 2022: It is now possible to select and copy $\LaTeX$ source code of formulas within the articles.
2223
- 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.
2324
- June 7, 2022: Date of last commit and author list with contribution percentage is tracked for each page.
24-
- June 5, 2022: Enabled content tabs and sidebar navigation. The navigation is moved to a [separate page](https://cp-algorithms.com/navigation.html) and its structure should be adjusted in [navigation.md](https://github.com/cp-algorithms/cp-algorithms/blob/master/src/navigation.md) whenever a new article is created or an old one is moved.
25+
- June 5, 2022: Enabled content tabs and sidebar navigation. The navigation is moved to a [separate page](https://cp-algorithms.com/navigation.html) and its structure should be adjusted in [navigation.md](https://github.com/cp-algorithms/cp-algorithms/blob/main/src/navigation.md) whenever a new article is created or an old one is moved.
2526
- January 16, 2022: Switched to the [MkDocs](https://www.mkdocs.org/) site generator with the [Material for MkDocs](https://squidfunk.github.io/mkdocs-material/) theme, which give the website a more modern look, brings a couple of new features (dark mode, better search, ...), makes the website more stable (in terms of rendering math formulas), and makes it easier to contribute.
2627

2728
### New articles
2829

30+
- (12 July 2024) [Manhattan distance](https://cp-algorithms.com/geometry/manhattan-distance.html)
2931
- (8 June 2024) [Knapsack Problem](https://cp-algorithms.com/dynamic_programming/knapsack.html)
3032
- (28 January 2024) [Introduction to Dynamic Programming](https://cp-algorithms.com/dynamic_programming/intro-to-dp.html)
3133
- (8 December 2023) [Hungarian Algorithm](https://cp-algorithms.com/graph/hungarian-algorithm.html)
@@ -38,7 +40,7 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
3840
- (7 May 2022) [Knuth's Optimization](https://cp-algorithms.com/dynamic_programming/knuth-optimization.html)
3941
- (31 March 2022) [Continued fractions](https://cp-algorithms.com/algebra/continued-fractions.html)
4042

41-
Full list of updates: [Commit History](https://github.com/cp-algorithms/cp-algorithms/commits/master)
43+
Full list of updates: [Commit History](https://github.com/cp-algorithms/cp-algorithms/commits/main)
4244

4345
Full list of articles: [Navigation](https://cp-algorithms.com/navigation.html)
4446

‎mkdocs.yml

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -28,8 +28,8 @@ theme:
2828
- content.code.copy
2929
repo_url: https://github.com/cp-algorithms/cp-algorithms
3030
repo_name: cp-algorithms/cp-algorithms
31-
edit_uri: edit/master/src/
32-
copyright: Text is available under the <a href="https://github.com/cp-algorithms/cp-algorithms/blob/master/LICENSE">Creative Commons Attribution Share Alike 4.0 International</a> License<br/>Copyright &copy; 2014 - 2024 by <a href="https://github.com/cp-algorithms/cp-algorithms/graphs/contributors">cp-algorithms contributors</a>
31+
edit_uri: edit/main/src/
32+
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 - 2024 by <a href="https://github.com/cp-algorithms/cp-algorithms/graphs/contributors">cp-algorithms contributors</a>
3333
extra_javascript:
3434
- javascript/config.js
3535
- https://cdnjs.cloudflare.com/polyfill/v3/polyfill.min.js?features=es6
@@ -74,6 +74,7 @@ plugins:
7474
docs_path: src/
7575
token: !ENV MKDOCS_GIT_COMMITTERS_APIKEY
7676
enabled: !ENV [MKDOCS_ENABLE_GIT_COMMITTERS, False]
77+
branch: main
7778
- macros
7879
- rss
7980

‎src/algebra/euclid-algorithm.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -126,3 +126,4 @@ E.g. C++17 has such a function `std::gcd` in the `numeric` header.
126126
## Practice Problems
127127
128128
- [CSAcademy - Greatest Common Divisor](https://csacademy.com/contest/archive/task/gcd/)
129+
- [Codeforces 1916B - Two Divisors](https://codeforces.com/contest/1916/problem/B)

‎src/algebra/extended-euclid-algorithm.md

Lines changed: 26 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -95,9 +95,32 @@ int gcd(int a, int b, int& x, int& y) {
9595

9696
If you look closely at the variables `a1` and `b1`, you can notice that they take exactly the same values as in the iterative version of the normal [Euclidean algorithm](euclid-algorithm.md). So the algorithm will at least compute the correct GCD.
9797

98-
To see why the algorithm also computes the correct coefficients, you can check that the following invariants will hold at any time (before the while loop, and at the end of each iteration): $x \cdot a + y \cdot b = a_1$ and $x_1 \cdot a + y_1 \cdot b = b_1$.
99-
It's trivial to see, that these two equations are satisfied at the beginning.
100-
And you can check that the update in the loop iteration will still keep those equalities valid.
98+
To see why the algorithm computes the correct coefficients, consider that the following invariants hold at any given time (before the while loop begins and at the end of each iteration):
99+
100+
$$x \cdot a + y \cdot b = a_1$$
101+
102+
$$x_1 \cdot a + y_1 \cdot b = b_1$$
103+
104+
Let the values at the end of an iteration be denoted by a prime ($'$), and assume $q = \frac{a_1}{b_1}$. From the [Euclidean algorithm](euclid-algorithm.md), we have:
105+
106+
$$a_1' = b_1$$
107+
108+
$$b_1' = a_1 - q \cdot b_1$$
109+
110+
For the first invariant to hold, the following should be true:
111+
112+
$$x' \cdot a + y' \cdot b = a_1' = b_1$$
113+
114+
$$x' \cdot a + y' \cdot b = x_1 \cdot a + y_1 \cdot b$$
115+
116+
Similarly for the second invariant, the following should hold:
117+
118+
$$x_1' \cdot a + y_1' \cdot b = a_1 - q \cdot b_1$$
119+
120+
$$x_1' \cdot a + y_1' \cdot b = (x - q \cdot x_1) \cdot a + (y - q \cdot y_1) \cdot b$$
121+
122+
By comparing the coefficients of $a$ and $b$, the update equations for each variable can be derived, ensuring that the invariants are maintained throughout the algorithm.
123+
101124

102125
At the end we know that $a_1$ contains the GCD, so $x \cdot a + y \cdot b = g$.
103126
Which means that we have found the required coefficients.

‎src/algebra/factorial-modulo.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@ Otherwise $p!$ and subsequent terms will reduce to zero.
1414
But in fractions the factors of $p$ can cancel, and the resulting expression will be non-zero modulo $p$.
1515

1616
Thus, formally the task is: You want to calculate $n! \bmod p$, without taking all the multiple factors of $p$ into account that appear in the factorial.
17-
Imaging you write down the prime factorization of $n!$, remove all factors $p$, and compute the product modulo $p$.
17+
Imagine you write down the prime factorization of $n!$, remove all factors $p$, and compute the product modulo $p$.
1818
We will denote this *modified* factorial with $n!_{\%p}$.
1919
For instance $7!_{\%p} \equiv 1 \cdot 2 \cdot \underbrace{1}_{3} \cdot 4 \cdot 5 \underbrace{2}_{6} \cdot 7 \equiv 2 \bmod 3$.
2020

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,7 @@ $$\sum_{\substack{p \le n, \\\ p \text{ prime}}} \frac n p = n \cdot \sum_{\subs
6161
Let's recall two known facts.
6262
6363
- The number of prime numbers less than or equal to $n$ is approximately $\frac n {\ln n}$.
64-
- The $k$-th prime number approximately equals $k \ln k$ (this follows immediately from the previous fact).
64+
- The $k$-th prime number approximately equals $k \ln k$ (this follows from the previous fact).
6565
6666
Thus we can write down the sum in the following way:
6767

0 commit comments

Comments
 (0)
0