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
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
for $$$x \geq a$$$ and $$$y \geq b$$$. To track these changes, we may represent $$$s_{xy}$$$ as
which allows us to split the addition of $$$c$$$ on $$$[a,+\infty) \times [b,+\infty)$$$ into additions in $$$(a;b)$$$:
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:
- Iterate over possible bottom left point $$$O$$$ of the convex subset;
- Ignore points below it and sort points above it by angle that they form with $$$O$$$;
- 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$$$;
- Sort considered points around $$$B$$$, separately in "yellow" and "green" areas (see picture);
- Iterate over possible point $$$C$$$ which will succeed $$$B$$$ in the convex subset;
- Set of points that may precede $$$B$$$ with a next point $$$C$$$ form a contiguous prefix of points before $$$B$$$;
- The second pointer $$$A$$$ to the end of the prefix is maintained;
- 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$$$:
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:
- Add/remove element $$$x$$$ from the set, all prime divisors of $$$x$$$ are known;
- 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$$$?
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$$$:
assuming the empty intersection to be the full set $$$S$$$. We may split the formula half-way as
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:
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
to get rid of non-linear or repeated linear factors of $$$q(x)$$$, as
Second, you pick random $$$a$$$ and compute
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
For this, we introduce matrices $$$R^{(0)}, \dots, R^{(m-1)}$$$ such that
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
where $$$N(\sigma)$$$ is a parity of $$$\sigma$$$. If you sum them up, you get
But at the same time,
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
where $$$\omega$$$ is an $$$n$$$-th root of unity. Correspondingly, $$$k$$$-th eigenvector is of form
In particular it means that the determinant of such matrix is
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
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
such that
where $$$B^\top$$$ is reversed string $$$B$$$. To check this, one may use operation $$$\operatorname{mix}(S, T)$$$ such that
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.
Thanks for the great blog! Just an observation: point 7 can be looked at in a different way through Möbius Inversion on Posets.
most of them are too old ...
True... I just felt like it makes sense to document folklore stuff from time to time.
They are new to beginners
I think what they meant is that the example problems given in the blog are relatively old (mostly pre-2018 era).
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.
Could you give some sample problems for the 11-nth idea?
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.
KEEP IT UP, ONE DAY YOU WILL BECOME GRANDMASTER
Fear not the man who knows 10000 algorithms, fear the man who has practiced Binary Search 10000 times