Errichto's blog

By Errichto, 3 years ago, In English

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 CESThttps://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:

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

The other important formula is E(X·Y) = E(XE(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(XE(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.

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

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Another problem on the ordered pairs technique : Chef cuts tree

»
3 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    ;_;

    If I send you a blog one day earlier next time, is that considered cheating? :O

»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide links to the problems in the blog?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be very helpful if someone can provide a list of OJ problems(as much as possible) on EV and contribution technique.

»
22 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Find EV of the square of the number of winning tickets? What does this particular thing, denotes as in general??, any one??