SendThemToHell's blog

Taylor Formula in CP
By SendThemToHell, 4 months ago, In English

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

Full text and comments »

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

SNSS2020 R5
By SendThemToHell, history, 6 years ago, translation, In English

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?

Full text and comments »

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