Instruction
I recommend this blog also for red users. Read the theory and problems below, try to solve them. For solutions and extra insight/tips, watch my stream on Monday or watch the video later. If you aren't familiar with EV or summing problems, see part 1 first: http://codeforces.me/blog/entry/62690.
I will stream a lecture on Monday at 14:00 CEST — https://www.youtube.com/watch?v=HDk6zQw0Rdo (also Twitch). I will go through theory and problems from this blog.
Expected Value theory, part 2
We roll a 6-sided die. Remember, EV of square of the number of pips is something different than square of EV:
Two events are independent if the result of one doesn't affect the distribution of p-bilities of the other. Results of throwing two dice (or throwing one die twice) are independent, but the amount of rain and the strength of wind are dependent. The linearity is always true:
The other important formula is E(X·Y) = E(X)·E(Y) but it's true only for INDEPENDENT events. So the EV of the product of numbers of pips on two dice is 3.52, but we can't use E(X·X) = E(X)·E(X), because X and X are not independent.
Ordered pairs (super interpretation of square)
The square of the size of a set is equal to the number of ordered pairs of elements in the set. So we iterate over pairs and for each we compute the contribution to the answer.
Similarly, the k-th power is equal to the number of sequences (tuples) of length k.
Bonus: powers technique
If you want to maintain the sum of k-th powers, it might help to also maintain the sum of smaller powers. For example, if the sum of 0-th, 1-th and 2-nd powers is S0, S1 and S2, and we increase every element by x, the new sums are S0, S1 + S0·x and S2 + 2·x·S1 + x2·S0. We will focus on the "ordered pairs" technique, though.
Problems
Inflation 2 The price of a tv is 1000$. Each of the next N days, the prices goes up by 1% or 2% (each with p-bility 50%). Find EV of the final price.
Square of wins You bought N (N ≤ 105) lottery tickets. The i-th of them is winning with p-bility pi. The event are independent (important!). Find EV of the square of the number of winning tickets.
Cube of wins Same but find EV of the 3-rd or 4-th power.
Bulbs There are N (N ≤ 50) light bulbs and M (M ≤ 50) switches. For every switch, we know a set of bulbs such that its state is flipped (on to off, off to on) when the switch is clicked. All bulbs are off, and then we click each switch with p-bility 50%. Find EV of the cube of the number of bulbs that are on.
Sum-length Given a sequence of length N (N ≤ 105), find the sum over sum·len3 over all intervals. Print the answer modulo 109 + 7.
There are a few possible solutions.Small power of subtree You're given a tree of size N (N ≤ 105) and an integer k (k ≤ 10). Find the sum of sizek over all "subtrees", i.e. connected subgraphs. Print the answer modulo 109 + 7.
DoubleLive (Topcoder SRM 727) Your army consists of B + H soldiers: B bears and H humans (B, H ≤ 2000). A bear has two hit points, a human has one hit point.
The enemy archer has T arrows (T ≤ 2·B + H). Every next arrow will hit a random alive soldier in your army, taking one hit point. When someone has zero hit points, he dies.
The strength of your army is defined as bears·humans·all, e.g. 3·7·10 = 210 for an army of 3 bears and 7 humans. It doesn't matter if some bears have only one hit point.
Find the EV of the strength of your army after the enemy archer uses all his arrows.
See my Youtube channel (link) for more videos on algos and CP, and my Facebook page https://fb.com/errichto for some shorter posts, news, problems.
Another problem on the ordered pairs technique : Chef cuts tree
How I wish this blog had been posted one day earlier! Yesterday there was a problem in the ICPC Xuzhou Regional that requires one to count the sum of cubes over the number of different subsequences in an array with size at most 200. We tried to use dynamic programming maintaining powers but failed, however by the ordered pairs(triples here) this problem can be solved quite easily. Yesterday was the first time in my life that I encountered the technique, and today the second time...
;_;
If I send you a blog one day earlier next time, is that considered cheating? :O
I guess not :D
I guess not :D
Could you please explain how you used this method to solve this question?
The exact problem is here. You can first try to solve it on your own using the ordered pairs technique. There's also $$$T\leq 20$$$ test cases for this specific problem, so one is required to solve the problem in $$$O(n^3)$$$ time.
To count the sum of cubes of the number of occurrences over all subsequences, one may count the number of triplets of occurrences of the same subsequence. One may attack this problem by doing some dynamic programmings, e.g., $$$dp[i][j][k][a]$$$ as the number of triplets of occurrences, such that the first is before $$$i$$$, the second before $$$j$$$, the third before $$$k$$$ and the common ending is $$$a$$$. This, however, runs in $$$O(n^4)$$$, which is still not affordable for this problem. To reduce the complexity, one may try to optimize out a dimension in dynamic programming. Consider extending the subsequence occurrences one by one; one may set up some auxiliary arrays, e.g., $$$f[i][j][k]$$$ meaning the first one has already extended, and the second and the third not yet. By using prefix sum, these arrays can be computed in cubic time.
Can you provide links to the problems in the blog?
It would be very helpful if someone can provide a list of OJ problems(as much as possible) on EV and contribution technique.
In last problem will DP[bears][humans] work if we include the number of hit arrows in state domain i.e. DP[i][b][h] = probability that after hitting 'i' arrows 'b' bears are dead and 'h' humans are dead then now we can know the number of wounded bears = i-h-2b. Then we can do transition to either attack human, fully fit bear or an injured bear, though complexity will be n*cubic. Is this correct? Edit : You talked about it later in the stream. Sorry.
Find EV of the square of the number of winning tickets? What does this particular thing, denotes as in general??, any one??
In problem 5: The approach where we have $$$n^6$$$ solution and then we optimize it, can someone elaborate on the details of it ? I tried using stars and bars as described in the video but I couldn't get it.
The video provides a formula
which is not enough because it doesn't consider putting dots at position i. If we put at least one dot at $i$, it's then allowed to leave the left and/or right part empty.
Here's a fix. Iterate over $$$L, M, R$$$ — the number of dots on left, middle, right. We need $$$L + M > 0$$$ and $$$M + R > 0$$$ and $$$L + M + R = 5$$$. Increase the answer by $$$\binom{i-1+(L-1)}{L} \cdot \binom{n-i+(R-1)}{R}$$$. This formula doesn't use $$$M$$$ because the number of ways to put $$$M$$$ dots at position $$$i$$$ is just $$$1^M$$$.
I won't be surprised if this can be simplified or just approached differently.
please correct me if I'm wrong, I don't think that will work (I tried it with code first to make sure) link
If we consider a simple case with $$$n = 20$$$ and $$$i = 10$$$ the sequence of indices $$$(1, 2, 3, 4, 15)$$$ should be counted $$$3!$$$ times (all different permutations of the 3 middle elements), whereas the formula you provided will count it only once since it deals with indistinguishable objects so $$$(1, 2, 3, 4, 15)$$$ is the same as $$$(1, 2, 4, 3, 15)$$$
Oh, you are right. The fix is ugly. We need to separately count cases with 1/2/3 different middle elements — and multiply those counts by 1/3/6, respectively. I'm not sure if this can be done nicely without a lot of for-loops like the number of elements on the left, the number of distinct elements on the left and so on.
For problem 4. Bulbs
Can't we simply calculate the probabilty for every bulb to be turned on at the end and then calculate the triples? And also, isn't the probability for every bulb simply 0, when there is no switch that turns it on, and 50% when there is at least one?
Hi there! Maybe it is a late reply, but I disagree. Indeed, the probability of each single bulb is 0 when there are no switches for it and 50% otherwise. However, when we need to calculate the probability for each triple of bulbs to be all turned on at the end is not, it is not just the multiplication of their three independent probabilities because the three events we are considering are not independent. Imagine having two bulbs and one switch that turns both bulbs on, then the probability of having both of the two bulbs turned on at the end is 50% (not 50% * 50% = 25%) because one switch can turn them both on (i.e. the two events are not independent), and the same goes for the triples.
thanks, i also thought same as Sedmoklasnikut, but your reply gave me insight.
i don't understand how E(x^2) = E(#pairs) i get that count(pairs) = x^2. but that's it. I watched that part 3-4 times. can someone please explain me or link me to a resource?
I did not understand problem 6 -> Small powers of subtree. We made a dp[v][i]-> number of ways to choose an ordered sequence of length i from this subtree. But while doing transition dp[u][i]+=dp[v][i];dp[u][i+1]+=dp[v][i]*some constant.......dp[u][k]+=dp[v][i]*some constant. I did not understand the transitions as the length of sequence i made from some nodes of subtree of v might not include the node v itself and hence directly including node u into the sequence made from subtree of v might not necessarily make a connected subgraph So are we defining our dp[u][i] like ->number of ways to choose an ordered sequence of length i from this subtree while one of the points being node u ?? please clarify.