{"version": "https://jsonfeed.org/version/1", "title": "Algorithms for Competitive Programming", "home_page_url": "https://cp-algorithms.com/", "feed_url": "https://cp-algorithms.com/feed_json_updated.json", "description": "The goal of this project is to translate the wonderful resource http://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.", "icon": null, "authors": [], "language": "en", "items": [{"id": "https://cp-algorithms.com/graph/finding-negative-cycle-in-graph.html", "url": "https://cp-algorithms.com/graph/finding-negative-cycle-in-graph.html", "title": "Finding a Negative Cycle in the Graph", "content_html": "<h1>Finding a negative cycle in the graph</h1>\n<p>You are given a directed weighted graph $G$ with $N$ vertices and $M$ edges. Find any cycle of negative weight in it...</p>", "image": null, "date_modified": "2025-04-16T00:46:24+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/algebra/factorization.html", "url": "https://cp-algorithms.com/algebra/factorization.html", "title": "Integer factorization", "content_html": "<h1>Integer factorization</h1>\n<p>In this article we list several algorithms for the factorization of integers, each of which can be either fast or varying levels of ...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html", "url": "https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html", "title": "Sieve of Eratosthenes", "content_html": "<h1>Sieve of Eratosthenes</h1>\n<p>Sieve of Eratosthenes is an algorithm for finding all the prime numbers in a segment $[1;n]$ using $O(n \\log \\log n)$ operations.</p>\n<p>T...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/data_structures/fenwick.html", "url": "https://cp-algorithms.com/data_structures/fenwick.html", "title": "Fenwick Tree", "content_html": "<h1>Fenwick Tree</h1>\n<p>Let $f$ be some group operation (a binary associative function over a set with an identity element and inverse elements) and $A$ be an array ...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/basic-geometry.html", "url": "https://cp-algorithms.com/geometry/basic-geometry.html", "title": "Basic Geometry", "content_html": "<h1>Basic Geometry</h1>\n<p>In this article we will consider basic operations on points in Euclidean space which maintains the foundation of the whole analytical geome...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/convex_hull_trick.html", "url": "https://cp-algorithms.com/geometry/convex_hull_trick.html", "title": "Convex hull trick and Li Chao tree", "content_html": "<h1>Convex hull trick and Li Chao tree</h1>\n<p>Consider the following problem. There are $n$ cities. You want to travel from city $1$ to city $n$ by car. To do this y...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/delaunay.html", "url": "https://cp-algorithms.com/geometry/delaunay.html", "title": "Delaunay triangulation and Voronoi diagram", "content_html": "<h1>Delaunay triangulation and Voronoi diagram</h1>\n<p>Consider a set ${p_i}$ of points on the plane.\nA <strong>Voronoi diagram</strong> $V({p_i})$ of ${p_i}$ is a partition...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/intersecting_segments.html", "url": "https://cp-algorithms.com/geometry/intersecting_segments.html", "title": "Search for a pair of intersecting segments", "content_html": "<h1>Search for a pair of intersecting segments</h1>\n<p>Given $n$ line segments on the plane. It is required to check whether at least two of them intersect with each ...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/lattice-points.html", "url": "https://cp-algorithms.com/geometry/lattice-points.html", "title": "Lattice points of non-lattice polygon", "content_html": "<h1>Lattice points inside non-lattice polygon</h1>\n<p>For lattice polygons there is Pick's formula to enumerate the lattice points inside the polygon.\nWhat about poly...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/manhattan-distance.html", "url": "https://cp-algorithms.com/geometry/manhattan-distance.html", "title": "Manhattan Distance", "content_html": "<h1>Manhattan Distance</h1>\n<h2>Definition</h2>\n<p>For points $p$ and $q$ on a plane, we can define the distance between them as the sum of the differences between their $...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/minkowski.html", "url": "https://cp-algorithms.com/geometry/minkowski.html", "title": "Minkowski sum of convex polygons", "content_html": "<h1>Minkowski sum of convex polygons</h1>\n<h2>Definition</h2>\n<p>Consider two sets $A$ and $B$ of points on a plane. Minkowski sum $A + B$ is defined as ${a + b| a \\in A, ...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/planar.html", "url": "https://cp-algorithms.com/geometry/planar.html", "title": "Finding faces of a planar graph", "content_html": "<h1>Finding faces of a planar graph</h1>\n<p>Consider a graph $G$ with $n$ vertices and $m$ edges, which can be drawn on a plane in such a way that two edges intersect...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/point-location.html", "url": "https://cp-algorithms.com/geometry/point-location.html", "title": "Point location in O(log N)", "content_html": "<h1>Point location in $O(log n)$</h1>\n<p>Consider the following problem: you are given a [planar subdivision](https://en.wikipedia.org/wiki/Planar_straight-line_graph...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/tangents-to-two-circles.html", "url": "https://cp-algorithms.com/geometry/tangents-to-two-circles.html", "title": "Common tangents to two circles", "content_html": "<h1>Finding common tangents to two circles</h1>\n<p>Given two circles. It is required to find all their common tangents, i.e. all such lines that touch both circles si...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/vertical_decomposition.html", "url": "https://cp-algorithms.com/geometry/vertical_decomposition.html", "title": "Vertical decomposition", "content_html": "<h1>Vertical decomposition</h1>\n<h2>Overview</h2>\n<p>Vertical decomposition is a powerful technique used in various geometry problems. The general idea is to cut the plane ...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/graph/2SAT.html", "url": "https://cp-algorithms.com/graph/2SAT.html", "title": "2-SAT", "content_html": "<h1>2-SAT</h1>\n<p>SAT (Boolean satisfiability problem) is the problem of assigning Boolean values to variables to satisfy a given Boolean formula.\nThe Boolean formul...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/graph/edmonds_karp.html", "url": "https://cp-algorithms.com/graph/edmonds_karp.html", "title": "Maximum flow - Ford-Fulkerson and Edmonds-Karp", "content_html": "<h1>Maximum flow - Ford-Fulkerson and Edmonds-Karp</h1>\n<p>The Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing a maximal flow i...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/graph/hld.html", "url": "https://cp-algorithms.com/graph/hld.html", "title": "Heavy-light decomposition", "content_html": "<h1>Heavy-light decomposition</h1>\n<p><strong>Heavy-light decomposition</strong> is a fairly general technique that allows us to effectively solve many problems that come down to ...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/graph/lca.html", "url": "https://cp-algorithms.com/graph/lca.html", "title": "Lowest Common Ancestor", "content_html": "<h1>Lowest Common Ancestor - $O(\\sqrt{N})$ and $O(\\log N)$ with $O(N)$ preprocessing</h1>\n<p>Given a tree $G$. Given queries of the form $(v_1, v_2)$, for each query ...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/graph/lca_farachcoltonbender.html", "url": "https://cp-algorithms.com/graph/lca_farachcoltonbender.html", "title": "Lowest Common Ancestor - Farach-Colton and Bender algorithm", "content_html": "<h1>Lowest Common Ancestor - Farach-Colton and Bender Algorithm</h1>\n<p>Let $G$ be a tree.\nFor every query of the form $(u, v)$ we want to find the lowest common ance...</p>", "image": null, "date_modified": "2025-04-15T02:32:08+00:00", "authors": [], "tags": null}]}