WeakForge/cp-algorithms
Watch
1
0
Fork
You've already forked cp-algorithms
 0
mirror of https://github.com/cp-algorithms/cp-algorithms.git synced 2026-10-06 01:53:02 +02:00
Code Issues Projects Releases Packages Wiki Activity
Algorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru) https://cp-algorithms.com/
2,728 commits 8 branches 0 tags 118 MiB
  • C++ 73.4%
  • HTML 8.1%
  • C 6%
  • JavaScript 4.2%
  • Python 2.9%
  • Other 5.4%
Find a file
Exact
Repository files (latest commit first)
Filename Latest commit message Latest commit date
Oleksandr Kulkov f06f7d5e56
 Fix the complexity argument for merging sets small to large (#1706) 
The article justified the O(n log^2 n) bound by saying a number is added
to a set at most O(log n) times. That reason does not hold, because
these sets hold distinct numbers. Merging a set of size k into a larger
one produces the union, which can be no bigger than the destination
already was, so the set holding a moved number need not double.

Measured on random trees with 4000 vertices, counting moves whose
destination is not at least twice the source:

  2 distinct values      1648 of  2647 moves   62%
  8 distinct values      2264 of  4251 moves   53%
  64 distinct values     2746 of  7070 moves   39%
  100000 values          1702 of 10417 moves   16%

The bound itself is correct; only the reason was wrong. The text now
counts insertion attempts, since a duplicate still costs a lookup, and
moves the doubling step onto vertices, where it does hold:

- a subtree's set has at most as many elements as the subtree has
  vertices
- merging into the child with the most distinct numbers costs no more
  than merging into the child with the largest subtree
- for that rule a vertex lies in the smaller subtree at most O(log n)
  times, since the combined subtree at least doubles

Checked: attempts divided by n log2 n stays bounded and in fact falls as
n grows from 1000 to 64000, and the exchange step never cost more than
the largest-subtree rule across 300 random trees.

Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
2026-09-19 14:39:39 +02:00
.devin Devin config 2025-11-19 15:07:38 +01:00
.github Stop CI from failing runs that were never going to do anything (#1705) 2026-09-19 13:31:16 +02:00
plugins update submodule 2022-06-09 03:50:34 +02:00
preview Add literate-nav plugin 2022-06-05 23:59:44 +02:00
scripts Remove navigation tabs, add toggle to hide sidebar (#1440) 2025-04-08 11:45:34 +02:00
src Fix the complexity argument for merging sets small to large (#1706) 2026-09-19 14:39:39 +02:00
test Add a parallel binary search section (#1700) 2026-09-19 13:59:27 +02:00
.firebaserc add firebase deploy infos 2021-08-14 15:45:57 +02:00
.gitignore improve .gitignore (#1668) 2026-09-18 15:24:49 +02:00
.gitmodules Fix incorrect usernames 2022-06-09 02:27:22 +02:00
CONTRIBUTING.md Update CONTRIBUTING.md 2025-05-07 17:57:39 -04:00
firebase.json add firebase deploy infos 2021-08-14 15:45:57 +02:00
hooks.py Track github logins and contribution percentage 2022-06-07 21:56:28 +02:00
LICENSE Add CC BY-SA license to the project 2016-11-27 23:30:46 -08:00
mkdocs.yml Revert "Add Coddy sponsorship placement (#1658)" 2026-08-15 03:36:21 +02:00
README.md Revert "Add Coddy sponsorship placement (#1658)" 2026-08-15 03:36:21 +02:00
SECURITY.md Create SECURITY.md 2024-10-15 19:47:18 +02:00

README.md

Algorithms for Competitive Programming

Contributors Pull Requests Closed Pull Requests Build Translation Progress

The goal of this project is to translate the wonderful resource https://e-maxx.ru/algo which provides descriptions of many algorithms and data structures especially popular in field of competitive programming. Moreover we want to improve the collected knowledge by extending the articles and adding new articles to the collection.

We're an ad-free, volunteer-run website that's free for everyone. Users can contribute articles or help sponsor bounties on articles for greater algorithmic coverage. Your help is greatly appreciated.

Compiled pages are published at https://cp-algorithms.com/.

Become a Contributor

Sponsor Us

Changelog

  • August, 2025: Overhaul of CP-Algorithms donation system. Please consider supporting us, so that we can grow!
  • August, 2025: Launched a Discord server!
  • October, 2024: Welcome new maintainers: jxu, mhayter and kostero!
  • October, 15, 2024: GitHub pages based mirror is now served at https://gh.cp-algorithms.com/, and an auxiliary competitive programming library is available at https://lib.cp-algorithms.com/.
  • July 16, 2024: Major overhaul of the Finding strongly connected components / Building condensation graph article.
  • June 26, 2023: Added automatic RSS feeds for new articles and updates in articles.
  • 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. It is recommended to update the upstream link in your local repositories, if you have any.
  • October 31, 2022: It is now possible to select and copy \LaTeX source code of formulas within the articles.
  • 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. For translated articles, clicking on From: X tag would lead to the original article.
  • June 7, 2022: Date of last commit and author list with contribution percentage is tracked for each page.
  • June 5, 2022: Enabled content tabs and sidebar navigation. The navigation is moved to a separate page and its structure should be adjusted in navigation.md whenever a new article is created or an old one is moved.
  • January 16, 2022: Switched to the MkDocs site generator with the Material for MkDocs 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.

New articles

Full list of updates: Commit History

Full list of articles: Navigation