PROBLEM LINK:Setter Bogdan Ciobanu DIFFICULTY:MEDIUMHARD PREREQUISITES:Segment Tree with Lazy Propagation , Taylor Series , Logarithmic Functions, Basic Calculus PROBLEM:There are $N$ food stalls. After eating food from food stall $i,$ there is a $P_i$ probability of you getting food poisoning initially. We have to support 2 queries
QUICK EXPLANATION:What we have to actually find is, $(1P_L)*(1P_{L+1})...*(1P_R)$, which itself is easy, but the update operation makes it complicated. We use the property of $Log$ which says ${e}^{Log_e a}=a$ to express $Ans=(1P_L)*(1P_{L+1})...*(1P_R)={e}^{Log_e [(1P_L)*(1P_{L+1})...*(1P_R)]} ={e}^{Log_e(1P_L)+Log_e(1P_{L+1})...+Log_e(1P_R)} $. Now, each of the $Log_e(1P_i)$ can be easily calculated by using its Taylor series, which says that $Log_e(1x)=(x+\frac{{x}^{2}}{2}+\frac{{x}^{3}}{3}.....\infty)$ . With this, we can easily support update operations using Lazy Propagation. EXPLANATION:The setter, tester and editorialist have majorly used the same approach. Hence, that will be discussed in this editorial, along with few common mistakes, setter's note of precision of Taylor's series in the bonus section. :) Setter/Tester/Editorialist's Solution 1. What to store in Node? For our approaches, we decided to store the first $100$ terms of Taylor Series. Because $0\le P_i \le 0.9$, then the $100'th$ term of the series, $\Large \frac{{x}^{100}}{100}$, will be at most of magnitude $2.6*{10}^{7}$ and will have an effect of $\approx {10}^{7}$ on the final answer. Hence, taking first $100$ terms should do. We didnt experiment for the exact amount, you need at least $8890$ terms, as any less will definitely not do. 2. How to handle updates? For convenience, let me denote $P_i$ by $x$ from henceforth. Note that we are storing $\Large \sum_{i=1}^{100} \frac{{x}^{i}}{i}$ in the node. For each update, all we have to do is to change $\Large \sum_{i=1}^{100} \frac{{x}^{i}}{i}$ to $\Large \sum_{i=1}^{100} \frac{{(t*x)}^{i}}{i}$. This can be easily done by multiplying $\Large \frac{{x}^{i}}{i}*{t}^{i}$. A single $for$ loop suffices for that, and we can update a node after reaching to it in $100$ operations. We must make sure to use Lazy propagation here, so that the latter part of tree, which may not be needed right now, is updated efficiently only when needed. If we keep on updating the entire tree every time (i.e. if we dont use lazy propagation) then our update will take $100*NlogN$ (worstcase) operations, which will time out! What is the ParentChild relationship? The parent child relationship for this tree is actually simple!! Say Taylor series of left child is $\Large \sum_{i=1}^{100} \frac{{x}^{i}}{i}$ and that of right child is $\Large \sum_{i=1}^{100} \frac{{y}^{i}}{i}$. Then Taylor series of parent is given by $\Large \sum_{i=1}^{100} (\frac{{x}^{i}}{i}+\frac{{y}^{i}}{i})$. Can you think a bit on why is this so? (Hint: $Log_e(ab)=Log_ea+Log_eb$). Proof is in Chef Vijju's corner. 4. How to get the answer For getting the answer, we query for the nodes in range $[L,R]$ to get the sum of Taylor series of each of them. Lets call this as $Sum$. Note that this $Sum$ represents nothing but $Log_e(1P_L)+Log_e(1P_{L+1})...Log_e(1P_R)=Log_e [(1P_L)*(1P_{L+1})...*(1P_R)]$. Our answer, hence, is ${e}^{sum}$ by using the ${e}^{Log_e a}=a$ property of $Log$. For this, we used the $expl()$ function of $C++$ because of its high accuracy. You can refer to my commented solution for implementation (I tried my best to explain tester's solution there as well, so do give it a shot :D ) And thats it, we are done with one of the hardest problems of this long :) . Were you expecting a $3000$ word editorial here? Sorry :p xD SOLUTION:Author's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here. $Time$ $Complexity$ $O(K*(N+Q)LogN)$ where $K=100$ (Number of terms of Taylor Series) CHEF VIJJU'S CORNER1. Dont open the tab below! Please no! Its empty, really!! 2.Proof of why $\Large \sum_{i=1}^{\infty} \frac{{x}^{i}}{i}$ $=Log_e(1x)$ 3. Reverse proof of how we correlated $Ans=(1P_L)*(1P_{L+1})...*(1P_R)={e}^{ \sum_{L}^{R}Log(1P_i)}$ and how we arrived at the Taylor Series is clearly outlined in the quick explanation section. Please refer there for derivation :). 4.Setter's Note of precision of Taylor's series method 5.Proof of ParentChild Relationship 6.Common errors
7.Some resources for Segment tree with lazy propagation
This question is marked "community wiki".
asked 13 Apr '18, 15:42
