adamant's blog

By adamant, history, 17 months ago, In English

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}$$$

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:


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.

  • Vote: I like it
  • +214
  • Vote: I do not like it

| Write comment?
17 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the great blog! Just an observation: point 7 can be looked at in a different way through Möbius Inversion on Posets.

17 months ago, # |
  Vote: I like it +45 Vote: I do not like it

most of them are too old ...

  • »
    17 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    True... I just felt like it makes sense to document folklore stuff from time to time.

  • »
    17 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    They are new to beginners

    • »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think what they meant is that the example problems given in the blog are relatively old (mostly pre-2018 era).

17 months ago, # |
  Vote: I like it +42 Vote: I do not like it

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.

8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you give some sample problems for the 11-nth idea?

8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this paper that describes an $$$O(n \log^2 n)$$$ simple and elegant method to compute subset sums (cyclical or non-cyclical) also complements your list pretty nicely.

8 months ago, # |
  Vote: I like it 0 Vote: I do not like it


  • »
    8 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Fear not the man who knows 10000 algorithms, fear the man who has practiced Binary Search 10000 times