adamant's blog

By adamant, history, 6 weeks 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}$$$
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.

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

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +45 Vote: I do not like it

most of them are too old ...

  • »
    »
    6 weeks 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.

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

    They are new to beginners

    • »
      »
      »
      6 weeks 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).

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice

»
6 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Good