A bit more of general ideas

Revision en4, by adamant, 2022-07-03 06:00:44

Hi everyone!

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

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(g^0), q(g^1), \dots, q(g^{p-2})$$$, where $$$g$$$ is a primitive root modulo $$$p$$$.

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

Range add/range sum on a plane. 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 range updates idea from Petr blog from 2013.

DP on convex subsets.

Assume you want to compute something related to convex subsets of a given set of points in 2D space.

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

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