repo_url:https://github.com/cp-algorithms/cp-algorithms

repo_name:cp-algorithms/cp-algorithms

edit_uri:edit/main/src/

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>

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 -2025 by <a href="https://github.com/cp-algorithms/cp-algorithms/graphs/contributors">cp-algorithms contributors</a>

extra_javascript:

-javascript/config.js

-https://cdnjs.cloudflare.com/polyfill/v3/polyfill.min.js?features=es6

hooks:

on_env:"hooks:on_env"

-search

-tags:

tags_file:tags.md

-tags

-literate-nav:

nav_file:navigation.md

-git-revision-date-localized:

The polynomials $A_0$ and $A_1$are only half asmuch coefficients as the polynomial $A$.

The polynomials $A_0$ and $A_1$have only half asmany coefficients as the polynomial $A$.

If we can compute the $\text{DFT}(A)$ in linear time using $\text{DFT}(A_0)$ and $\text{DFT}(A_1)$, then we get the recurrence $T_{\text{DFT}}(n) = 2 T_{\text{DFT}}\left(\frac{n}{2}\right) + O(n)$ for the time complexity, which results in $T_{\text{DFT}}(n) = O(n \log n)$ by the**master theorem**.

Let's learn how we can accomplish that.

}

During a normal sqrt decomposition, we have to precompute the answers for each block, and merge them during answering queries.

In some problems this merging step can be quite problematic.

E.g. when each queries asks to find the**mode** of its range (the number that appears the most often).

For this each block would have to store the count of each number in it in some sort of data structure, and wecannot longer perform the merge step fast enough any more.

For this each block would have to store the count of each number in it in some sort of data structure, and wecan no longer perform the merge step fast enough any more.

**Mo's algorithm** uses a completely different approach, that can answer these kind of queries fast, because it only keeps track of one data structure, and the only operations with it are easy and fast.

The idea is to answer the queries in a special order based on the indices.

The essence of dynamic programming is to avoid repeated calculation. Often, dynamic programming problems are naturally solvable by recursion. In such cases, it's easiest to write the recursive solution, then save repeated states in a lookup table. This process is known as top-down dynamic programming with memoization. That's read "memoization" (like we are writing in a memo pad) not memorization.

One of the most basic, classic examples of this process is the fibonacci sequence.It's recursive formulation is $f(n) = f(n-1) + f(n-2)$ where $n \ge 2$ and $f(0)=0$ and $f(1)=1$. In C++, this would be expressed as:

One of the most basic, classic examples of this process is the fibonacci sequence.Its recursive formulation is $f(n) = f(n-1) + f(n-2)$ where $n \ge 2$ and $f(0)=0$ and $f(1)=1$. In C++, this would be expressed as:

intf(int n) {

Until now you've only seen top-down dynamic programming with memoization. However, we can also solve problems with bottom-up dynamic programming.

Bottom-up is exactly the opposite of top-down, you start at the bottom (base cases of the recursion), and extend it to more and more values.

To create a bottom-up approach for fibonacci numbers, weinitilize the base cases in an array. Then, we simply use the recursive definition on array:

To create a bottom-up approach for fibonacci numbers, weinitialize the base cases in an array. Then, we simply use the recursive definition on array:

constint MAXN =100;

e = e1;

}

std::reverse(face.begin(), face.end());

int sign = 0;

for (size_t j = 0; j < face.size(); j++) {

size_t j1 = (j + 1) % face.size();

size_t j2 = (j + 2) % face.size();

int64_t val = vertices[face[j]].cross(vertices[face[j1]], vertices[face[j2]]);

if (val > 0) {

sign = 1;

break;

} else if (val < 0) {

sign = -1;

break;

}

Point p1 = vertices[face[0]];

__int128 sum = 0;

for (int j = 0; j < face.size(); ++j) {

Point p2 = vertices[face[j]];

Point p3 = vertices[face[(j + 1) % face.size()]];

sum += (p2 - p1).cross(p3 - p2);

}

if (sign <= 0) {

if (sum <= 0) {

faces.insert(faces.begin(), face);

} else {

faces.emplace_back(face);

The**Whitney inequalities** (1932) gives a relation between the edge connectivity $\lambda$, the vertex connectivity $\kappa$ and thesmallest degree of thevertices $\delta$:

The**Whitney inequalities** (1932) gives a relation between the edge connectivity $\lambda$, the vertex connectivity $\kappa$, and theminimum degree ofany vertex inthegraph $\delta$:

The task of finding the edge connectivityif equal to the task of finding the**global minimum cut**.

The task of finding the edge connectivityis equal to the task of finding the**global minimum cut**.

Special algorithms have been developed for this task.

One of them is the Stoer-Wagner algorithm, which works in $O(V^3)$ or $O(V E)$ time.