Fype's blog

DP complex
By Fype, 5 years ago, In English

It's one of the most beautiful dp I ever used. I'm going to explain it with an example.

Problem: 1265E

Solution: suppose $$$e_i$$$ equals the expected number of days that we stop if starting of i-th mirror.
$$$e_i = p_i * e_{i + 1} + (1 - p_i) * e_1 + 1$$$
$$$e_n = (1 - p_i) * e_1 + 1$$$

So how to update $$$e$$$?! :D
We will change how we show numbers. You know how we show complex numbers (if you don't learn it here), we are going to use the same idea.
Each number consists a part that is $$$e_1$$$ and another part that is a Real number(in this problem you can change it to integer when using modulo).
We show each number with $$$x$$$ and $$$y$$$ such that the number is equal to $$$x * e_1 + y$$$. So we use this idea and start updating $$$e$$$ backward.
Then we will get $$$e_1 = x * e_1 + y$$$ and now we can get $$$e_1$$$ as an intiger.
$$$e_1 = y / (1 - x)$$$

Any other problem that uses the same idea, please mention. :D

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

»
21 month(s) ago, # |
← Rev. 4   Vote: I like it +12 Vote: I do not like it

Last day, a similar problem was questioned in the contest Codeforces Round 848 (Div. 2) (problem D).

Here is my solution for the problem mentioned in the blog:

Let $$$F_i$$$ denotes the expected number of times until we are able to go to the next mirror when we are at the mirror $$$i$$$. For the sake of simplicity, call $$$P_i$$$ the probability of being beautiful at the mirror $$$i$$$. Now the mirror either tells us we are beautiful with probability $$$P_i$$$ and allows us to switch to the other mirror, or we start again with the first mirror with probability $$$(1 - P_i)$$$. With these observations, we can write the general formula

$$$F_i = 1*P_i + (1 - P_i) * (1 + F_1 + F_2 + F_3 + ... + F_i)$$$

If we rearrange the formula and use a variable named $$$sum_i$$$ that keeps the prefix sum of F, we get

$$$F_i = (1 + (1-P_i) * sum_{i-1}) / P_i$$$

We can compute all F_i one by one now.

By definition, $$$F_i$$$ gives us the expected number of times to switch $$$(i+1)$$$ th mirror from $$$i$$$ th mirror. To get the answer, we must jump from the first mirror to the second, from the second mirror to the third, and so on. So in conclusion, we can express the equation

$$$answer = F_1 + F_2 + F_3 + ... + F_n$$$

The code I wrote
→ Reply