{"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/num_methods/binary_search.html", "url": "https://cp-algorithms.com/num_methods/binary_search.html", "title": "Binary Search", "content_html": "<h1>Binary search</h1>\n<p><strong>Binary search</strong> is a method that allows for quicker search of something by splitting the search interval into two. Its most common applica...</p>", "image": null, "date_modified": "2024-10-27T03:15:34+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/dynamic_programming/intro-to-dp.html", "url": "https://cp-algorithms.com/dynamic_programming/intro-to-dp.html", "title": "Introduction to Dynamic Programming", "content_html": "<h1>Introduction to Dynamic Programming</h1>\n<p>The essence of dynamic programming is to avoid repeated calculation. Often, dynamic programming problems are naturall...</p>", "image": null, "date_modified": "2024-10-24T15:02:51+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": "2024-10-23T02:39:29+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/combinatorics/binomial-coefficients.html", "url": "https://cp-algorithms.com/combinatorics/binomial-coefficients.html", "title": "Binomial Coefficients", "content_html": "<h1>Binomial Coefficients</h1>\n<p>Binomial coefficients $\\binom n k$ are the number of ways to select a set of $k$ elements from $n$ different elements without taking...</p>", "image": null, "date_modified": "2024-10-22T23:31:25+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/combinatorics/inclusion-exclusion.html", "url": "https://cp-algorithms.com/combinatorics/inclusion-exclusion.html", "title": "The Inclusion-Exclusion Principle", "content_html": "<h1>The Inclusion-Exclusion Principle</h1>\n<p>The inclusion-exclusion principle is an important combinatorial way to compute the size of a set or the probability of c...</p>", "image": null, "date_modified": "2024-10-22T23:31:25+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/graph/strongly-connected-components.html", "url": "https://cp-algorithms.com/graph/strongly-connected-components.html", "title": "Strongly Connected Components and Condensation Graph", "content_html": "<h1>Strongly connected components and the condensation graph</h1>\n<h2>Definitions</h2>\n<p>Let $G=(V,E)$ be a directed graph with vertices $V$ and edges $E \\subseteq V \\time...</p>", "image": null, "date_modified": "2024-10-22T23:31:25+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/nearest_points.html", "url": "https://cp-algorithms.com/geometry/nearest_points.html", "title": "Finding the nearest pair of points", "content_html": "<h1>Finding the nearest pair of points</h1>\n<h2>Problem statement</h2>\n<p>Given $n$ points on the plane. Each point $p_i$ is defined by its coordinates $(x_i,y_i)$. It is ...</p>", "image": null, "date_modified": "2024-10-22T23:26:15+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/sequences/k-th.html", "url": "https://cp-algorithms.com/sequences/k-th.html", "title": "K-th order statistic in O(N)", "content_html": "<h1>$K$th order statistic in $O(N)$</h1>\n<p>Given an array $A$ of size $N$ and a number $K$. The problem is to find $K$-th largest number in the array, i.e., $K$-th o...</p>", "image": null, "date_modified": "2024-10-20T18:33:37+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/algebra/euclid-algorithm.html", "url": "https://cp-algorithms.com/algebra/euclid-algorithm.html", "title": "Euclidean algorithm for computing the greatest common divisor", "content_html": "<h1>Euclidean algorithm for computing the greatest common divisor</h1>\n<p>Given two non-negative integers $a$ and $b$, we have to find their <strong>GCD</strong> (greatest common ...</p>", "image": null, "date_modified": "2024-10-15T10:56:28+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/algebra/linear-diophantine-equation.html", "url": "https://cp-algorithms.com/algebra/linear-diophantine-equation.html", "title": "Linear Diophantine Equations", "content_html": "<h1>Linear Diophantine Equation</h1>\n<p>A Linear Diophantine Equation (in two variables) is an equation of the general form:</p>\n<p>$$ax + by = c$$</p>\n<p>where $a$, $b$, $c$ are...</p>", "image": null, "date_modified": "2024-10-15T09:57:28+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/graph/dinic.html", "url": "https://cp-algorithms.com/graph/dinic.html", "title": "Maximum flow - Dinic's algorithm", "content_html": "<h1>Maximum flow - Dinic's algorithm</h1>\n<p>Dinic's algorithm solves the maximum flow problem in $O(V^2E)$. The maximum flow problem is defined in this article [Maxi...</p>", "image": null, "date_modified": "2024-10-15T09:40:14+00:00", "authors": [], "tags": null}, {"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": "2024-10-14T07:14:57+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/geometry/convex-hull.html", "url": "https://cp-algorithms.com/geometry/convex-hull.html", "title": "Convex hull construction", "content_html": "<h1>Convex Hull construction</h1>\n<p>In this article we will discuss the problem of constructing a convex hull from a set of points.</p>\n<p>Consider $N$ points given on a p...</p>", "image": null, "date_modified": "2024-10-13T23:38:15+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/num_methods/simpson-integration.html", "url": "https://cp-algorithms.com/num_methods/simpson-integration.html", "title": "Integration by Simpson's formula", "content_html": "<h1>Integration by Simpson's formula</h1>\n<p>We are going to calculate the value of a definite integral</p>\n<p>$$\\int_a ^ b f (x) dx$$</p>\n<p>The solution described here was publ...</p>", "image": null, "date_modified": "2024-10-13T23:38:15+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": "2024-10-13T09:24:36+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/graph/breadth-first-search.html", "url": "https://cp-algorithms.com/graph/breadth-first-search.html", "title": "Breadth First Search", "content_html": "<h1>Breadth-first search</h1>\n<p>Breadth first search is one of the basic and essential searching algorithms on graphs.</p>\n<p>As a result of how the algorithm works, the p...</p>", "image": null, "date_modified": "2024-10-13T09:02:39+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": "2024-10-12T14:55:01+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/data_structures/disjoint_set_union.html", "url": "https://cp-algorithms.com/data_structures/disjoint_set_union.html", "title": "Disjoint Set Union", "content_html": "<h1>Disjoint Set Union</h1>\n<p>This article discusses the data structure <strong>Disjoint Set Union</strong> or <strong>DSU</strong>.\nOften it is also called <strong>Union Find</strong> because of its two ...</p>", "image": null, "date_modified": "2024-10-12T10:13:20+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/others/stern_brocot_tree_farey_sequences.html", "url": "https://cp-algorithms.com/others/stern_brocot_tree_farey_sequences.html", "title": "The Stern-Brocot Tree and Farey Sequences", "content_html": "<h1>The Stern-Brocot tree and Farey sequences</h1>\n<h2>Stern-Brocot tree</h2>\n<p>The Stern-Brocot tree is an elegant construction to represent the set of all positive frac...</p>", "image": null, "date_modified": "2024-10-12T10:12:15+00:00", "authors": [], "tags": null}, {"id": "https://cp-algorithms.com/game_theory/sprague-grundy-nim.html", "url": "https://cp-algorithms.com/game_theory/sprague-grundy-nim.html", "title": "Sprague-Grundy theorem. Nim", "content_html": "<h1>Sprague-Grundy theorem. Nim</h1>\n<h2>Introduction</h2>\n<p>This theorem describes the so-called <strong>impartial</strong> two-player game,\ni.e. those in which the available moves a...</p>", "image": null, "date_modified": "2024-10-12T00:42:54+00:00", "authors": [], "tags": null}]}