By adamant, history, 6 weeks ago,

Hi everyone!

Here's another collection of little tricks and general ideas that might make your life better (or maybe worse).

Most of them are somewhat well-known, but perhaps would still be useful to someone.

1. Evaluating polynomial modulo small prime $p$. Given a polynomial $q(x)$, it may be evaluated in all possible $a \in \mathbb Z_p$ in $O(p \log p)$. To do this, compute $q(0)$ separately and use chirp Z-transform to compute $q(g^0), q(g^1), \dots, q(g^{p-2})$, where $g$ is a primitive root modulo $p$.

This method can be used to solve 1054H - Epic Convolution.

2. Generalized Euler theorem. Let $a$ be a number, not necessarily co-prime with $m$, and $k > \log_2 m$. Then

$a^k \equiv a^{\phi(m) + k \mod \phi(m)} \pmod m,$

where $\phi(m)$ is Euler's totient. This follows from the Chinese remainder theorem, as it trivially holds for $m=p^d$.

This fact can be used in 906D - Power Tower.

3. Range add/range sum in 2D. Fenwick tree, generally, allows for range sum/point add queries.

Let $s_{xy}$ be a sum on $[1,x] \times [1,y]$. If we add $c$ on $[a, +\infty) \times [b, +\infty)$, the sum $s_{xy}$ would change as

$s_{xy} \mapsto s_{xy} + (x-a+1)(y-b+1)c,$

for $x \geq a$ and $y \geq b$. To track these changes, we may represent $s_{xy}$ as

$s_{xy} = s_{xy}^{(0)}+ x \cdot s_{xy}^{(x)} + y \cdot s_{xy}^{(y)} + xy \cdot s_{xy}^{(xy)},$

which allows us to split the addition of $c$ on $[a,+\infty) \times [b,+\infty)$ into additions in $(a;b)$:

\begin{align} s_{xy}^{(0)} &\mapsto s_{xy}^{(0)} + (a-1)(b-1)c, \\ s_{xy}^{(x)} &\mapsto s_{xy}^{(x)} - (b-1)c, \\ s_{xy}^{(y)} &\mapsto s_{xy}^{(y)} - (a-1)c, \\ s_{xy}^{(xy)} &\mapsto s_{xy}^{(xy)} + c. \end{align}
code

The solution generalizes 1-dimensional Fenwick tree range updates idea from Petr blog from 2013.

You can check your implementation on eolymp — Чипполино.

4. DP on convex subsets. You want to compute something related to convex subsets of a given set of points in 2D space.

You sort points over bottom-left point $O$, then over point $B$ and go through all pairs $(A, C)$ with two pointers

This can be done with dynamic programming, which generally goes as follows:

1. Iterate over possible bottom left point $O$ of the convex subset;
2. Ignore points below it and sort points above it by angle that they form with $O$;
3. Iterate over possible point $B$ to be the "last" in the convex subset. It may only be preceded by a point that was sorted before it and succeeded by a points that was sorted after it when the points were sorted around $O$;
4. Sort considered points around $B$, separately in "yellow" and "green" areas (see picture);
5. Iterate over possible point $C$ which will succeed $B$ in the convex subset;
6. Set of points that may precede $B$ with a next point $C$ form a contiguous prefix of points before $B$;
7. The second pointer $A$ to the end of the prefix is maintained;
8. Eventually, for every $B$, all valid pairs of $A$ and $C$ are iterated with two pointers.

This allows to consider in $O(n^3)$ all the convex subsets of a given set of points, assuming that sorting around every point $B$ was computed beforehand in $O(n^2 \log n)$ and is now used to avoid actual second sorting of points around $B$.

The method may probably be used to solve AtCoder — ConvexScore.

5. Subset sum on segments. Given $a_1, \dots, a_n$, answer $q$ queries. Each query is whether $a_l, a_{l+1}, \dots, a_r$ has a subset of sum $w$. This can be done with dynamic programming $L[r][w]$ being the right-most $l$ such that $a_l, \dots, a_r$ has a subset with sum $w$:

$L[r][w] = \max(L[r-1][w], L[r-1][w-a_r]).$

This allows to solve the problem in $O(nw + q)$.

Unfortunately, I forgot the original problem on which I saw this approach.

6. Data structure with co-primality info. There is a structure that supports following queries:

1. Add/remove element $x$ from the set, all prime divisors of $x$ are known;
2. Count the number of elements in the structure that are co-prime with $x$.

Without loss of generality, we may assume that the numbers are square-free.

Let $w(x)$ be the number of distinct prime divisors of $x$ and $N_x$ be the amount of numbers divisible by $x$ in the structure. When $x$ is added or removed from the structure, you need to update $2^{w(x)}$ values of $N_x$. Now, having $N_x$, how to count numbers co-prime with $x$?

$A_x = \sum\limits_{d | x} (-1)^{w(d)} N_d = \sum\limits_{d | x} \mu(d) N_d,$

where $\mu(d)$ is the Möbius function. This formula essentially uses inclusion-exclusion principle, as $N_d$ counts numbers divisible by $d$ and we need to count numbers that are not divisible by any divisor of $x$.

The method was used in 102354B - Yet Another Convolution.

7. Generalized inclusion-exclusion. Let $A_1, \dots, A_n$ be some subsets of a larger set $S$. Let $\overline{A_i} = S \setminus A_i$.

With the inclusion-exclusion principle, we count the number of points from $S$ that lie in neither of $A_i$:

$\left|\bigcap\limits_{i=1}^n \overline{A_i}\right| = \sum\limits_{m=0}^n (-1)^m \sum\limits_{|X|=m} \left|\bigcap\limits_{i \in X} A_i\right|,$

assuming the empty intersection to be the full set $S$. We may split the formula half-way as

$\left|\bigcup\limits_{|Y|=r} \left( \bigcap\limits_{i \in Y} A_i \bigcap\limits_{j \in Y} \overline{A_j} \right)\right| = \sum\limits_{m=r}^n (-1)^{m-r} \binom{m}{r} \sum\limits_{|X|=m} \left|\bigcap\limits_{i \in X} A_i\right|.$

This way, we're able to count the number of points from $S$ that lie in exactly $r$ set among $A_1, \dots, A_n$.

Explanation lies in the fact that for a fixed $Y$, we may use PIE directly:

$\left|\bigcap\limits_{i \in Y} A_i \bigcap\limits_{j \in Y} \overline{A_j}\right| = \sum\limits_{m=r}^n (-1)^{m-r} \sum\limits_{\substack{|X| = m \\ Y \subset X}} \left|\bigcap\limits_{i \in X} A_i\right|,$

then if summing up over all possible $Y$, each set $X$ will always have $(-1)^{m-r}$ coefficient and will occur for $\binom{m}{r}$ sets $Y$.

8. Finding roots of polynomials over $\mathbb Z_p$. You're given $q(x)$. You want to find all $a \in \mathbb Z_p$, such that $q(a)=0$.

This is done in two steps. First, you compute

$h(x) = \gcd(q(x), x^{p}-x)$

to get rid of non-linear or repeated linear factors of $q(x)$, as

$x^p - x \equiv \prod\limits_{a=0}^{p-1} (x - a) \pmod p.$

Second, you pick random $a$ and compute

$\gcd(h(x), (x+a)^{\frac{p-1}{2}}-1).$

This will filter roots of $h(x)$ by whether they're quadratic residues if $a$ is added to them or not.

Quadratic residues make up $\frac{p-1}{2}$ of numbers in $\mathbb Z_p$ and are distributed uniformly, so you'll have at least $\frac{1}{2}$ chance to get non-trivial divisor of $h(x)$. This is particularly useful when you want to solve e.g. $x^2 \equiv a \pmod p$, which can be done in $O(\log p)$ with this algorithm:

code

Generally, the probability of getting a divisor of $h(x)$ of degree $k$ for $\deg h = n$ can be expressed as $2^{-n}\binom{n}{k}$, thus on average this method nearly halves the degree of $h(x)$ in a single iteration. From this follows that the expected complexity of the algorithm is $O(n^2 \log p)$ if naive multiplication is used or $O(n \log^2 n \log np)$ if one uses FFT-based multiplication and half-GCD.

The method is called Berlekamp–Rabin algorithm and can be generalized to find all factors of $q(x)$ over $\mathbb Z_p$ (see this comment).

You can check your implementation on Library Judge — Sqrt Mod.

9. Matching divisible by $m$. You're given a weighted bipartite graph and you need to check if there exists a perfect matching that sums up to the number that is divisible by $m$. In other words, whether there exists a permutation $\sigma_1, \dots, \sigma_n$ such that

$A_{1 \sigma_1} + \dots + A_{n \sigma_n} \equiv 0 \pmod m.$

For this, we introduce matrices $R^{(0)}, \dots, R^{(m-1)}$ such that

$R^{(k)}_{ij} = x_{ij} \omega^{k A_{ij}},$

where $A_{ij}$ is weight between $i$ in the first part and $j$ in the second part, $x_{ij}$ is a random number when there is an edge between $i$ and $j$ or $0$ otherwise, and $\omega$ is a root of unity of degree $m$. The determinants of such matrices is then

$\det R^{(k)} = \sum\limits_{\sigma \in S_n} \left( (-1)^{N(\sigma)} \prod\limits_{i=1}^n x_{i \sigma_i}\right) (\omega^k)^{\sum\limits_{i=1}^n A_{i \sigma_i}},$

where $N(\sigma)$ is a parity of $\sigma$. If you sum them up, you get

$\sum\limits_{k=0}^{m-1} \det R^{(k)} = \sum\limits_{\sigma \in S_n} \left( (-1)^{N(\sigma)} \prod\limits_{i=1}^n x_{i \sigma_i}\right) \sum\limits_{k=0}^{m-1} (\omega^k)^{\sum\limits_{i=1}^n A_{i \sigma_i}}.$

But at the same time,

$\sum\limits_{k=0}^{m-1} \omega^{kx} = \begin{cases} m &, x \equiv 0 \pmod m,\\ 0&, x \not\equiv 0 \pmod m. \end{cases}$

Thus, a summand near $\sigma_1, \dots, \sigma_n$ will be non-zero only if $A_{1\sigma_1} + \dots + A_{n \sigma_n}$ sums up to the number divisible by $m$.

Therefore, the property can be checked in $O(mn^3)$.

The method was used in CSAcademy — Divisible Matching.

10. Eigenvectors of circulant matrix. Let $A$ be a matrix such that each of its rows is a cyclic shift of the previous one (see circulant matrix). Let the first column be $a_0, \dots, a_{n-1}$ and $A(x) = a_0 + a_1 x + \dots + a_{n-1} x^{n-1}$. Then the eigenvalues of $A$ are

$A(1), A(\omega), \dots, A(\omega^{n-1}),$

where $\omega$ is an $n$-th root of unity. Correspondingly, $k$-th eigenvector is of form

$\begin{pmatrix}1 & \omega^k & \omega^{2k} & \dots & \omega^{k(n-1)}\end{pmatrix}^\top.$

In particular it means that the determinant of such matrix is

$\det A = A(1) A(\omega) \dots A(\omega^{n-1})$

and multiplication by its inverse may be found with pointwise division after DFT of degree $n$.

These facts may be used to solve 102129G - Permutant and 901E - Cyclic Cipher.

11. Knapsack with repetitions. You have $n$ item types, there are $a_i$ items of type $i$, having weight $b_i$ and cost $c_i$. What is the maximum cost you may get with having total weight at most $w$? This is solvable in $O(nw)$. The transition formula looks like

$d[i][w] = \max\limits_{t=0}^{a_i} (d[i-1][w-t\cdot b_i] + c_i \cdot t)$

To compute it quickly enough, you should divide $d[i-1]$ into groups having the same remainder modulo $b_i$, after which the maximum is taken on contiguous segments of the same width rather than with steps of $b_i$, and can be computed with monotonic queue.

12. Reverses and palindromes. Given strings $S$ and $T$, is it possible to reverse some non-intersecting substrings of $S$ to obtain $T$?

In other words, we need to check if $S$ may be represented as

$S = A_0 B_1 A_1 B_2 A_2 \dots B_n A_n,$

such that

$T = A_0 B_1^\top A_1 B_2^\top \dots B_n^\top A_n,$

where $B^\top$ is reversed string $B$. To check this, one may use operation $\operatorname{mix}(S, T)$ such that

$\operatorname{mix}(s_1 s_2 \dots s_n, t_1 t_2 \dots t_n) = s_1 t_1 s_2 t_2 \dots s_n t_n.$

Key fact here is that $\operatorname{mix}(A, A^\top)$ gives a palindrome of even length and is invertible operation.

Correspondingly, $\operatorname{mix}(A, A)$ may be perceived as a concatenation of $|A|$ palindromes of length $2$.

That being said, checking that $T$ is obtained from $S$ by reversing some of its substrings is equivalent to checking whether $\operatorname{mix}(S, T)$ can be split in palindromes of even length, which is doable in $O(n \log n)$ with palindromic tree.

This method was used in 906E - Reverses.

• +214

 » 6 weeks ago, # |   +8 Thanks for the great blog! Just an observation: point 7 can be looked at in a different way through Möbius Inversion on Posets.
 » 6 weeks ago, # |   0 Thanks for you blog. I have learned a lot.By the way, Subset sum on segments. Maybe it is like this blog. Subset Sum Speedup 2
 » 6 weeks ago, # |   +45 most of them are too old ...
•  » » 6 weeks ago, # ^ |   +26 True... I just felt like it makes sense to document folklore stuff from time to time.
•  » » 6 weeks ago, # ^ |   +18 They are new to beginners
•  » » » 6 weeks ago, # ^ |   0 I think what they meant is that the example problems given in the blog are relatively old (mostly pre-2018 era).
 » 6 weeks ago, # |   +42 These will be added to my list of "interesting ideas to be kept in mind".I am rooting for you to keep making this kind of blog.
 » 6 weeks ago, # |   0 Nice
 » 6 weeks ago, # |   -8 Good