Блог пользователя SendThemToHell

Taylor Formula in CP
Автор SendThemToHell, 4 месяца назад, По-английски

This blog appeared due to the competition from cadmiumky. Many thanks to him for the initiative.

Preliminaries: Taylor formula.

Let us start with a reminder. Consider a function $$$f$$$ that is $$$n + 1$$$ times differentiable. Then it is known (from the calculus course) that

$$$ f(x_0 + h) = \sum_{i = 0}^{n} \frac{f^{(i)}(x_0)}{i!}h^i + \varepsilon_n(h), $$$

where $$$\varepsilon_n(h) = \frac{f^{(n + 1)}(x_0 + \xi)}{(n+1)!}h^{n + 1}$$$ for some $$$\xi \in [0, h]$$$.

Ok, that's nice, but how on earth is this applicable to competitive programming? Let's see an example.

Counting probabilities

I couldn't find the exact statement of the problem, so I will write it in a way I remember it. If you know the exact contest it comes from, please, share it with me.

Petrozavodsk Winter Programming camp, 2017

Consider $$$n$$$ slot machines in a row. Each of these machines has a number $$$p_i$$$ which indicates the probability of a win while using this machine. You need to process $$$q$$$ queries of two types:

  1. You multiply all $$$p_i, l \leq i \leq r$$$ by some constant $$$c$$$. It is guaranteed that all $$$p_i$$$ will never exceed $$$1/10$$$ and will always be at least $$$10^{-6}$$$.

  2. You calculate the probability of losing all the games if you play each of the machines on segment $$$[l,r]$$$ one time. As this number may be very small, you need to output the logarithm of this value instead.

Both $$$n$$$ and $$$q$$$ are big (say, $$$10^5$$$).

Solution

If you have seen a decent number of CP problems before, you should immediately suspect that this problem is about some kind of segment tree/BIT tree. Ok, let's try to plug the segment tree here. The answer to the second query is

$$$\log(\prod_{i = l}^{r}(1-p_i)) = \sum_{i = l}^{r}\log(1 - p_i),$$$

so we just need to maintain $$$\log(1 - p_i)$$$ in leaves and use a standard segment tree for sum, right? Well, not so fast! It is not so easy to maintain these values, as they change in a random manner during the first type of queries.

How to deal with this problem? Well, let's try to spot something strange in the statement, maybe it will help us (shoutout to this blog). Well, there are two things that definitely stand out. First, there are some strange guaranties about $$$p_i$$$ and second, we are asked to calculate the probabilities in real numbers. The second thing is really suspicious nowadays (maybe it was not so suspicious at the time this problem was introduced): why not just ask to calculate everything modulo some big prime? Well, that is because we won't calculate this number exactly!

Indeed, let us replace each $$$\log(1 - p_i)$$$ with its Taylor expansion. As $$$\log(1-x)^{(j)} = \frac{(j-1)!}{(1-x)^{j}}$$$, we can write

$$$ \log(1 - p_i) = -\sum_{j = 1}^{k}\frac{1}{j}p_i^j + \varepsilon_k(p_i) \approx -\sum_{j = 1}^{k}\frac{1}{j}p_i^j. $$$

This is much better, as we can now rewrite

$$$ \sum_{i = l}^{r} \log(1 - p_i) \approx -\sum_{j = 1}^{k} \sum_{i = l}^{r} \frac{1}{j}p_i^j $$$

and do both update and sum queries by using $$$k$$$ segment trees, one for each power of $$$p_i$$$.

The only thing that remains is the following question: how to estimate $$$k$$$? This is easy, since we know the formula for $$$\varepsilon_k$$$. Using this formula we can give the following estimate:

$$$ |\varepsilon_k(p_i)| = \left| \frac{1}{(k + 1)(1-\xi)^{k + 1}}p_i^{k + 1} \right| \leq \left| \frac{1}{k + 1}\left(\frac{p_i}{1 - p_i}\right)^{k + 1} \right| \leq \frac{1}{k + 1}\left(\frac{0.1}{0.9}\right)^{k + 1} \lt \frac{1}{9^{k+1}}, $$$

so if we need to have an error of at most $$$\delta$$$, we can just take $$$k = \left[\log_{9}\left(n/\delta\right)\right]$$$.

Exercise for the reader

I strongly believe that there is little to no use in learning different topics if you don't learn how to solve problems on this topic. Unfortunately, I'm only aware of one other problem using the same technique. Here it is.

An exercise

Полный текст и комментарии »

  • Проголосовать: нравится
  • +143
  • Проголосовать: не нравится

О дискретном логарифмировании
Автор SendThemToHell, история, 5 лет назад, По-русски

Прочтение замечательного текста от peltorator https://mirror.codeforces.com/blog/entry/91258 натолкнуло меня на мысль о том, что мне не известно ни одного ресурса по спортивному программированию, где было бы изложено то, что известно про структуру группы $$$(\mathbb{Z}/m\mathbb{Z})^*$$$ (группа остатков по модулю $$$m$$$, взаимнопростых с $$$m$$$). Поскольку звучит это очень математично и бесполезно, то приведу пример, когда такое знание может быть полезно. Например, мы хотим решать такую задачу: дано число $$$m$$$ и много запросов вида $$$a, b$$$, где $$$(a, m) = (b, m) = 1$$$, и мы хотим решать уравнение вида $$$a^x = b \mod m$$$. Для некоторых $$$m$$$ (для которых существует первообразный корень) задача решается при помощи baby-step-giant-step, подробнее можно прочитать по ссылке выше. По сути мы пользуемся тем, что в этих случаях $$$(\mathbb{Z}/m\mathbb{Z})^* \cong \mathbb{Z}_{\varphi(m)}$$$. Однако, оказывается, что и для других $$$m$$$ нам известна структура этой группы, и мы можем применить это знание для решения нашей задачи!

Disclaimer: на этом страшные слова про группы закончились, дальнейший текст я постарался сделать максимально простым и не использующим всякие ругательства. В частности это означает, что доказательств в тексте ниже не будет.

Итак, мы хотим быстро решать задачи вида $$$a^x = b \mod m$$$, где $$$(a, m) = (b, m) = 1$$$, но само $$$m$$$ не является простым, причем отвечать нам придется на много запросов вида $$$a, b$$$, а $$$m$$$ будет фиксированным. Для того, чтобы сделать это, давайте сначала факторизуем $$$m$$$. Итак, пусть $$$m = 2^{\alpha_0}p_1^{\alpha_1}\dotsc p_{n}^{\alpha_n}$$$. Для удобства, иногда мы будем использовать обозначение $$$p_0 = 2$$$ (Как будет видно ниже, оно существенно отличается от остальных простых. Это связано с тем, что по модулю $$$2^{\alpha}$$$ при $$$\alpha \gt 2$$$ не существует первообразных корней). Введем также обозначения $$$q_i = m / p_i^{\alpha_i}$$$. Оказывается, что если взять

  1. $$$g_{-1} = -1 \mod 2^{\alpha_0}, g_{-1} = 1 \mod q_0$$$;
  2. $$$g_{0} = 5 \mod 2^{\alpha_0}, g_{0} = 1 \mod q_0$$$;
  3. $$$\forall \; i \gt 0: g_{i}$$$ — первообразный корень по модулю $$$p_i^{\alpha_i}, g_{i} = 1 \mod q_i$$$,

то любой взаимнопростой с $$$m$$$ остаток будет иметь вид $$$g_{-1}^{\beta_{-1}}g_{0}^{\beta_{0}}\dotsc g_{n}^{\beta_n}$$$, причем будут выполняться неравенства $$$\beta_i \in [0, m_i)$$$, где $$$m_i = p_{i}^{\alpha_i - 1}(p_{i} - 1), i \gt 0$$$, $$$m_{-1} = 1 + \chi(\alpha_0 \gt 1)$$$, $$$m_0 = \max(1, 2^{\alpha_0 - 2})$$$. Более того, можно доказать, что такое представление будет единственным!

Теперь попытаемся научиться раскладывать элемент по нашему базису. Конечно, мы будем делать это при помощи meet-in-the-middle, однако нам придется несколько модифицировать алгоритм. Давайте зафиксируем некоторое $$$K$$$ и посмотрим на минимальное такое $$$i$$$, что $$$m_{-1}\dotsc m_{i} \geq K$$$. Тогда, очевидно, есть такое число $$$L$$$, что $$$m_{-1}\dotsc m_{i - 1}\lfloor m_i / L\rfloor \in [K/2, K]$$$. Давайте теперь предподсчитаем все числа вида $$$g_{-1}^{\beta_{-1}}g_{0}^{\beta_{0}}\dotsc g_{i - 1}^{\beta_{i-1}}g_i^{\beta_{i}}$$$ с условиями $$$\beta_{j} \in [0, m_j), L \vert \beta_{i}$$$. Таких чисел будет порядка $$$K$$$. Теперь на запрос нам достаточно перебрать все числа вида $$$p_i^{\beta_i}\dotsc p_n^{\beta_n}$$$ с условиями $$$\forall \; j \gt i: \beta_{j} \in [0, m_j), \beta_{i} \in [0, L)$$$ и проверить, что среди предподсчитаных чисел есть то, которое в произведении с этим дает $$$a$$$. Очевидно, что такое решение работает за $$$O(K\log K)$$$ предподсчета и $$$O(\varphi(m)\log K / K)$$$ на запрос.

Осталось понять, как по разложению в таком базисе двух чисел понять, в какую степень надо возвести первое, чтобы получить второе. Это не очень сложно, поскольку возведение в степень в таком представлении просто умножает коэффициенты по модулю. Другими словами, если разложение $$$a$$$ имеет вид $$$(a_{-1}, \dotsc, a_n)$$$, то разложение $$$a^x$$$ будет иметь вид $$$(a_{-1}x \mod m_{-1}, \dotsc, a_nx \mod m_n)$$$. Таким образом, получаем систему $$$x = b_i / a_i \mod m_i$$$. Решая ее (или понимая, что она не имеет решения) при помощи КТО, получаем ответ на запрос.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

SNSS2020 R5
Автор SendThemToHell, история, 6 лет назад, По-русски

Today I have discovered a strange fact about problem D from SNSS round 5.

I believe, most of the accepted solutions were something like "do ternary search over the angle/x-coordinate". It was somewhat hard for me to squeeze it into TL, so I had to do only 20 iterations to get accepted. Today I decided to find out, what is the minimum number of iterations of ternary search required to get AC. Turned out that this number is equal to... 0. The code which gives AC is listed below.

Spoiler

I believe that this code takes the intersection of the bisector of AB and the circle as optimum, which is definitely wrong. Am I missing something?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится