Skip to content

Commit 8f52f11

Browse files
adamant-pwnadamant-pwn
authored
Merge branch 'main' into patch-2
2 parents 7099351 + e357737 commit 8f52f11

File tree

86 files changed

+2069
-454
lines changed

Some content is hidden

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

86 files changed

+2069
-454
lines changed

‎.github/workflows/build.yml‎

Lines changed: 10 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,13 @@
11
name: Build
2+
23
on:
34
push:
45
branches:
5-
- 'master'
6+
- main
67
pull_request:
78

89
jobs:
9-
test:
10+
build:
1011
runs-on: ubuntu-latest
1112

1213
steps:
@@ -29,13 +30,14 @@ jobs:
2930
key: test-${{ github.event_name }}-github-users-v0.1
3031
- name: Build pages
3132
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' }}
33+
MKDOCS_GIT_COMMITTERS_BRANCH: ${{ github.ref_name }}
34+
MKDOCS_GIT_COMMITTERS_APIKEY: ${{ github.token }}
35+
MKDOCS_ENABLE_GIT_REVISION_DATE: ${{ github.token && 'True' || 'False' }}
36+
MKDOCS_ENABLE_GIT_COMMITTERS: ${{ github.token && 'True' || 'False' }}
3537
run: |
3638
mkdocs build --strict
37-
- name: Upload build pages as artifact
38-
uses: actions/upload-artifact@v2
39+
- name: Upload pages as an artifact
40+
uses: actions/upload-artifact@v4
3941
with:
40-
name: page-build
42+
name: ${{ github.event.number || 'main' }}
4143
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/workflows/deploy-prod.yml‎

Lines changed: 52 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -2,97 +2,85 @@ name: Deploy
22

33
on:
44
workflow_run:
5-
# `workflow_run` events have access to secrets
65
workflows: [Build]
76
types:
87
- completed
98

109
jobs:
1110
deploy_live_website:
1211
runs-on: ubuntu-latest
13-
if: >
14-
${{ github.event.workflow_run.event == 'pull_request' &&
15-
github.event.workflow_run.conclusion == 'success' }}
12+
if: github.event.workflow_run.conclusion == 'success' && github.event.workflow_run.event == 'push'
1613
steps:
17-
- name: "Get PR information"
18-
uses: potiuk/get-workflow-origin@751d47254ef9e8b5eef955e24e79305233702781
19-
id: source-run-info
20-
with:
21-
token: ${{ secrets.GITHUB_TOKEN }}
22-
sourceRunId: ${{ github.event.workflow_run.id }}
23-
2414
- name: Checkout repository
2515
uses: actions/checkout@v3
2616

27-
- name: 'Download artifact'
28-
uses: actions/github-script@v6
17+
- name: Download pages
18+
uses: actions/download-artifact@v4
2919
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
20+
run-id: ${{ github.event.workflow_run.id }}
21+
github-token: ${{ github.token }}
22+
merge-multiple: true
23+
path: public
5024

5125
- name: change URLs for large files
52-
if: ${{ steps.source-run-info.outputs.sourceEvent == 'push' && steps.source-run-info.outputs.targetBranch == 'master'}}
5326
shell: bash
54-
run: |
55-
sed -i 's|search/search_index.json|https://storage.googleapis.com/cp-algorithms/search_index.json|g' public/assets/javascripts/*.js
27+
run: sed -i 's|search/search_index.json|https://storage.googleapis.com/cp-algorithms/search_index.json|g' public/assets/javascripts/*.js
5628

57-
- 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'
29+
- id: auth
30+
uses: google-github-actions/[email protected]
6031
with:
6132
credentials_json: '${{ secrets.GCP_CREDENTIALS }}'
6233

63-
- uses: 'google-github-actions/upload-cloud-storage@v1'
64-
if: ${{ steps.source-run-info.outputs.sourceEvent == 'push' && steps.source-run-info.outputs.targetBranch == 'master'}}
34+
- uses: google-github-actions/upload-cloud-storage@v1
6535
with:
66-
path: 'public/search/search_index.json'
67-
destination: 'cp-algorithms'
36+
path: public/search/search_index.json
37+
destination: cp-algorithms
6838

6939
- uses: FirebaseExtended/action-hosting-deploy@v0
7040
id: firebase-deploy
71-
if: env.FIREBASE_SERVICE_ACCOUNT
72-
env:
73-
PREVIEW_NAME: "preview-${{ steps.source-run-info.outputs.pullRequestNumber }}"
74-
LIVE_NAME: "live"
75-
FIREBASE_SERVICE_ACCOUNT: ${{ secrets.FIREBASE_SERVICE_ACCOUNT }}
7641
with:
77-
repoToken: "${{ secrets.GITHUB_TOKEN }}"
78-
firebaseServiceAccount: "${{ secrets.FIREBASE_SERVICE_ACCOUNT }}"
42+
repoToken: ${{ github.token }}
43+
firebaseServiceAccount: ${{ secrets.FIREBASE_SERVICE_ACCOUNT }}
7944
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 }}
45+
channelId: live
46+
47+
deploy_github_pages:
48+
runs-on: ubuntu-latest
49+
if: github.event.workflow_run.conclusion == 'success'
50+
steps:
51+
- name: Checkout repository
52+
uses: actions/checkout@v3
8153

82-
- name: comment URL to PR
83-
if: ${{ steps.source-run-info.outputs.sourceEvent == 'pull_request' }}
84-
uses: actions/github-script@v6
54+
- name: Download pages
55+
uses: actions/download-artifact@v4
8556
with:
86-
script: |
87-
const body = `Visit the preview URL for this PR (for commit ${{ steps.source-run-info.outputs.sourceHeadSha }}):
57+
run-id: ${{ github.event.workflow_run.id }}
58+
github-token: ${{ github.token }}
59+
path: public
8860

89-
${{ steps.firebase-deploy.outputs.details_url }}
61+
- name: Get PR number from artifact
62+
id: get-pr-number
63+
run: echo "pr_number=$(ls public)" >> $GITHUB_OUTPUT
9064

91-
(expires ${{ steps.firebase-deploy.outputs.expire_time }})`;
65+
- name: Configure git
66+
run: |
67+
git config --global user.name "github-actions[bot]"
68+
git config --global user.email "github-actions[bot]@users.noreply.github.com"
69+
70+
- name: Deploy to gh-pages
71+
uses: peaceiris/actions-gh-pages@v3
72+
with:
73+
github_token: ${{ github.token }}
74+
publish_dir: public/${{ steps.get-pr-number.outputs.pr_number }}
75+
publish_branch: gh-pages
76+
destination_dir: ${{ steps.get-pr-number.outputs.pr_number }}
9277

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-
})
78+
- name: Create or update PR comment
79+
if: steps.get-pr-number.outputs.pr_number != 'main'
80+
uses: peter-evans/create-or-update-comment@v3
81+
with:
82+
token: ${{ github.token }}
83+
issue-number: ${{ steps.get-pr-number.outputs.pr_number }}
84+
body: 'Preview the changes for PR #${{ steps.get-pr-number.outputs.pr_number }} at https://gh.cp-algorithms.com/${{ steps.get-pr-number.outputs.pr_number }}/ (current version: ${{ github.event.workflow_run.head_sha }}).'
85+
body-includes: 'Preview the changes for PR'
86+
mode: replace

‎.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: 8 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/translation_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,21 @@ 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)
31+
- (8 June 2024) [Knapsack Problem](https://cp-algorithms.com/dynamic_programming/knapsack.html)
32+
- (28 January 2024) [Introduction to Dynamic Programming](https://cp-algorithms.com/dynamic_programming/intro-to-dp.html)
33+
- (8 December 2023) [Hungarian Algorithm](https://cp-algorithms.com/graph/hungarian-algorithm.html)
2934
- (10 September 2023) [Tortoise and Hare Algorithm](https://cp-algorithms.com/others/tortoise_and_hare.html)
3035
- (12 July 2023) [Finding faces of a planar graph](https://cp-algorithms.com/geometry/planar.html)
3136
- (18 April 2023) [Bit manipulation](https://cp-algorithms.com/algebra/bit-manipulation.html)
@@ -35,7 +40,7 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
3540
- (7 May 2022) [Knuth's Optimization](https://cp-algorithms.com/dynamic_programming/knuth-optimization.html)
3641
- (31 March 2022) [Continued fractions](https://cp-algorithms.com/algebra/continued-fractions.html)
3742

38-
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)
3944

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

‎mkdocs.yml‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -25,13 +25,14 @@ theme:
2525
- navigation.tabs
2626
- toc.integrate
2727
- search.suggest
28+
- content.code.copy
2829
repo_url: https://github.com/cp-algorithms/cp-algorithms
2930
repo_name: cp-algorithms/cp-algorithms
30-
edit_uri: edit/master/src/
31-
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 - 2022 by <a href="https://github.com/cp-algorithms">https://github.com/cp-algorithms</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>
3233
extra_javascript:
3334
- javascript/config.js
34-
- https://polyfill.io/v3/polyfill.min.js?features=es6
35+
- https://cdnjs.cloudflare.com/polyfill/v3/polyfill.min.js?features=es6
3536
- https://unpkg.com/mathjax@3/es5/tex-mml-chtml.js
3637
extra_css:
3738
- stylesheets/extra.css
@@ -73,6 +74,7 @@ plugins:
7374
docs_path: src/
7475
token: !ENV MKDOCS_GIT_COMMITTERS_APIKEY
7576
enabled: !ENV [MKDOCS_ENABLE_GIT_COMMITTERS, False]
77+
branch: !ENV [MKDOCS_GIT_COMMITERS_BRANCH, main]
7678
- macros
7779
- rss
7880

‎src/algebra/big-integer.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -166,7 +166,7 @@ This method is often used for calculations modulo non-prime number M; in this ca
166166

167167
The idea is to choose a set of prime numbers (typically they are small enough to fit into standard integer data type) and to store an integer as a vector of remainders from division of the integer by each of those primes.
168168

169-
Chinese remainder theorem states that this representation is sufficient to uniquely restore any number from 0 to product of these primes minus one. [Garner algorithm](chinese-remainder-theorem.md) allows to restore the number from such representation to normal integer.
169+
Chinese remainder theorem states that this representation is sufficient to uniquely restore any number from 0 to product of these primes minus one. [Garner algorithm](garners-algorithm.md) allows to restore the number from such representation to normal integer.
170170

171171
This method allows to save memory compared to the classical approach (though the savings are not as dramatic as in factorization representation). Besides, it allows to perform fast addition, subtraction and multiplication in time proportional to the number of prime numbers used as modulos (see [Chinese remainder theorem](chinese-remainder-theorem.md) article for implementation).
172172

‎src/algebra/bit-manipulation.md‎

Lines changed: 39 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -152,7 +152,7 @@ bool isPowerOfTwo(unsigned int n) {
152152
}
153153
```
154154
155-
### Clear the most-right set bit
155+
### Clear the right-most set bit
156156
157157
The expression $n ~\&~ (n-1)$ can be used to turn off the rightmost set bit of a number $n$.
158158
This works because the expression $n-1$ flips all bits after the rightmost set bit of $n$, including the rightmost set bit.
@@ -186,6 +186,44 @@ int countSetBits(int n)
186186
}
187187
```
188188

189+
### Count set bits upto $n$
190+
To count the number of set bits of all numbers upto the number $n$ (inclusive), we can run the Brian Kernighan's algorithm on all numbers upto $n$. But this will result in a "Time Limit Exceeded" in contest submissions.
191+
192+
We can use the fact that for numbers upto $2^x$ (i.e. from $1$ to $2^x - 1$) there are $x \cdot 2^{x-1}$ set bits. This can be visualised as follows.
193+
```
194+
0 -> 0 0 0 0
195+
1 -> 0 0 0 1
196+
2 -> 0 0 1 0
197+
3 -> 0 0 1 1
198+
4 -> 0 1 0 0
199+
5 -> 0 1 0 1
200+
6 -> 0 1 1 0
201+
7 -> 0 1 1 1
202+
8 -> 1 0 0 0
203+
```
204+
205+
We can see that the all the columns except the leftmost have $4$ (i.e. $2^2$) set bits each, i.e. upto the number $2^3 - 1$, the number of set bits is $3 \cdot 2^{3-1}$.
206+
207+
With the new knowledge in hand we can come up with the following algorithm:
208+
209+
- Find the highest power of $2$ that is lesser than or equal to the given number. Let this number be $x$.
210+
- Calculate the number of set bits from $1$ to $2^x - 1$ by using the formua $x \cdot 2^{x-1}$.
211+
- Count the no. of set bits in the most significant bit from $2^x$ to $n$ and add it.
212+
- Subtract $2^x$ from $n$ and repeat the above steps using the new $n$.
213+
214+
```cpp
215+
int countSetBits(int n) {
216+
int count = 0;
217+
while (n > 0) {
218+
int x = std::bit_width(n) - 1;
219+
count += x << (x - 1);
220+
n -= 1 << x;
221+
count += n + 1;
222+
}
223+
return count;
224+
}
225+
```
226+
189227
### Additional tricks
190228
191229
- $n ~\&~ (n + 1)$ clears all trailing ones: $0011~0111_2 \rightarrow 0011~0000_2$.

0 commit comments

Comments
 (0)