3

Sums and Expected Value — part 2

 2 years ago
source link: http://codeforces.com/blog/entry/62792
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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.com/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:

b2163fd41e3af3bc57a856e36eeda0e191cf76c8.pngdbc7ece5c2e9b7e7f80f013428a2ed764478ae36.png

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:

E(X + Y) = E(X) + E(Y)

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

  1. 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.

  2. 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.

  3. Cube of wins Same but find EV of the 3-rd or 4-th power.

  4. 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.

  5. 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.

  6. 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.

  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.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK