Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

A bit more of general ideas

Revision en7, by adamant, 2022-07-03 16:04:31

Hi everyone!

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

1. Evaluating polynomial modulo small prime p. Given a polynomial q(x), you may evaluate it modulo p in all possible arguments. To do this, compute q(0) separately and use chirp Z-transform to compute q(g0),q(g1),,q(gp2), 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>log2m. 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.

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.

5. Knapsack on segments. You're given a_1, \dots, a_n and need to 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]).

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.

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

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.

Tags tutorial, i love tags

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en23 English adamant 2022-07-03 20:43:38 82
en22 English adamant 2022-07-03 20:40:31 134
en21 English adamant 2022-07-03 20:37:28 1210
en20 English adamant 2022-07-03 20:19:36 1
en19 English adamant 2022-07-03 20:19:06 412
en18 English adamant 2022-07-03 18:18:14 1141
en17 English adamant 2022-07-03 17:04:12 6
en16 English adamant 2022-07-03 17:00:10 38
en15 English adamant 2022-07-03 16:51:22 616
en14 English adamant 2022-07-03 16:42:16 132
en13 English adamant 2022-07-03 16:30:11 14
en12 English adamant 2022-07-03 16:29:39 95
en11 English adamant 2022-07-03 16:28:28 13
en10 English adamant 2022-07-03 16:27:46 60
en9 English adamant 2022-07-03 16:22:40 0 (published)
en8 English adamant 2022-07-03 16:22:25 1096
en7 English adamant 2022-07-03 16:04:31 55
en6 English adamant 2022-07-03 15:52:24 46
en5 English adamant 2022-07-03 15:15:04 9278
en4 English adamant 2022-07-03 06:00:44 2099
en3 English adamant 2022-07-03 05:29:53 956
en2 English adamant 2022-07-03 05:02:53 2774 Tiny change: 'e with $m$ and $k > ' -> 'e with $m$, and $k > '
en1 English adamant 2022-07-03 02:59:55 412 Initial revision (saved to drafts)