- name: Set up Python

uses: actions/setup-python@v5.2.0

with:

- name: Install mkdocs-material

run: |

icon:

repo: fontawesome/brands/github

features:

- toc.integrate

- search.suggest

- content.code.copy

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

repo_name: cp-algorithms/cp-algorithms

edit_uri: edit/main/src/

extra_javascript:

- javascript/config.js

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

permalink: true

plugins:

- mkdocs-simple-hooks:

hooks:

on_env: "hooks:on_env"

- search

- literate-nav:

nav_file: navigation.md

- git-revision-date-localized:

pip install \

"mkdocs-material>=9.0.2" \

mkdocs-macros-plugin \

mkdocs-literate-nav \

mkdocs-git-authors-plugin \

Here is a visualization of such a sequence $\{x_i \bmod p\}$ with $n = 2206637$, $p = 317$, $x_0 = 2$ and $f(x) = x^2 + 1$.

From the form of the sequence you can see very clearly why the algorithm is called Pollard's $\rho$ algorithm.

Yet, there is still an open question.

How can we exploit the properties of the sequence $\{x_i \bmod p\}$ to our advantage without even knowing the number $p$ itself?

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.

In the following image you can see a visualization of the algorithm for computing all prime numbers in the range $[1; 16]$. It can be seen, that quite often we mark numbers as composite multiple times.

The idea behind is this:

A number is prime, if none of the smaller prime numbers divides it.

return sum / s.size();

}

The following image shows a possible interpretation of the Fenwick tree as tree.

The nodes of the tree show the ranges they cover.

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).

**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.

int f(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.

const int MAXN = 100;

The grouping is made more efficient by using binary grouping.

Through the above splitting method, it is possible to obtain any sum of $\leq k_i$ items by selecting a few $A_{i, j}$'s. After splitting each item in the described way, it is sufficient to use 0-1 knapsack method to solve the new formulation of the problem.

Geometrically it is product of the length of the first vector by the length of the projection of the second vector onto the first one.

As you may see from the image below this projection is nothing but $|\mathbf a| \cos \theta$ where $\theta$ is the angle between $\mathbf a$ and $\mathbf b$. Thus $\mathbf a\cdot \mathbf b = |\mathbf a| \cos \theta \cdot |\mathbf b|$.

The dot product holds some notable properties:

You can see that this set of points is exactly the set of points for which the projection onto $\mathbf a$ is the point $C \cdot \dfrac{\mathbf a}{|\mathbf a|}$ and they form a hyperplane orthogonal to $\mathbf a$.

You can see the vector $\mathbf a$ alongside with several such vectors having same dot product with it in 2D on the picture below:

In 2D these vectors will form a line, in 3D they will form a plane.

Note that this result allows us to define a line in 2D as $\mathbf r\cdot \mathbf n=C$ or $(\mathbf r - \mathbf r_0)\cdot \mathbf n=0$ where $\mathbf n$ is vector orthogonal to the line and $\mathbf r_0$ is any vector already present on the line and $C = \mathbf r_0\cdot \mathbf n$.

Assume you have three vectors $\mathbf a$, $\mathbf b$ and $\mathbf c$ in 3D space joined in a parallelepiped as in the picture below:

How would you calculate its volume?

From school we know that we should multiply the area of the base with the height, which is projection of $\mathbf a$ onto direction orthogonal to base.

That means that if we define $\mathbf b \times \mathbf c$ as the vector which is orthogonal to both $\mathbf b$ and $\mathbf c$ and which length is equal to the area of the parallelogram formed by $\mathbf b$ and $\mathbf c$ then $|\mathbf a\cdot (\mathbf b\times\mathbf c)|$ will be equal to the volume of the parallelepiped.

For integrity we will say that $\mathbf b\times \mathbf c$ will be always directed in such way that the rotation from the vector $\mathbf b$ to the vector $\mathbf c$ from the point of $\mathbf b\times \mathbf c$ is always counter-clockwise (see the picture below).

This defines the cross (or vector) product $\mathbf b\times \mathbf c$ of the vectors $\mathbf b$ and $\mathbf c$ and the triple product $\mathbf a\cdot(\mathbf b\times \mathbf c)$ of the vectors $\mathbf a$, $\mathbf b$ and $\mathbf c$.

Actually it would be a bit more convenient to consider them not as linear functions, but as points $(k;b)$ on the plane such that we will have to find the point which has the least dot product with a given point $(x;1)$, that is, for this point $kx+b$ is minimized which is the same as initial problem.

Such minimum will necessarily be on lower convex envelope of these points as can be seen below:

One has to keep points on the convex hull and normal vectors of the hull's edges.

When you have a $(x;1)$ query you'll have to find the normal vector closest to it in terms of angles between them, then the optimum linear function will correspond to one of its endpoints.

During the algorithm $D$ will be stored inside the quad-edge data structure. This structure is described in the picture:

In the algorithm we will use the following functions on edges:

Let's draw a vertical line $x = -\infty$ mentally and start moving this line to the right.

In the course of its movement, this line will meet with segments, and at each time a segment intersect with our line it intersects in exactly one point (we will assume that there are no vertical segments).

Thus, for each segment, at some point in time, its point will appear on the sweep line, then with the movement of the line, this point will move, and finally, at some point, the segment will disappear from the line.

We are interested in the **relative order of the segments** along the vertical.

Namely, we will store a list of segments crossing the sweep line at a given time, where the segments will be sorted by their $y$-coordinate on the sweep line.

This order is interesting because intersecting segments will have the same $y$-coordinate at least at one time:

We formulate key statements: