Watch my lecture-stream tomorrow (Thursday) at 14:00 CEST —
https://www.youtube.com/watch?v=qdlPY37MBPo https://www.youtube.com/watch?v=U_h3IjreRek. I will go through theory and problems from this blog. The only prerequisite is knowing what is probability. The next (harder) part on Monday.
The video will be available later, with timestamps for each problem — so you don't have to watch everything.
Definition of EV
Let's say we bought a lottery ticket for 2$. We will win 10$ with probability 10%, and 20$ with p-bility 2%. On average, it gives us 0.1·10 + 0.02·20 = 1.4, so we are worse off after buying the ticket. The computed average is called the expected value.
The expected value (EV, expectation) is the average value of an event/experiment. For example, EV of the number of pips rolled on a 6-sided die is 3.5:
Linearity of EV (super important theorem):
Technique "Contribution to the sum"
If we want to find the sum over many ways/possibilities, we should consider every element (maybe a number, or a pair or an edge) and count how many times it will be added to the answer.
EV easy problems
Aces We choose 10 cards at random from a standard deck of 52 cards. Find EV of the number of aces.
Inflation The price of a tv is 1000$. Each of the next N days, the prices goes up by 5$ or 10$ (each with p-bility 50%). Find EV of the final price.
Bonus: What if it goes up by 1% or 2% each day?
Max of two You roll a 6-sided die twice. Find EV of the bigger of two scores.
Max of N You roll a 6-sided die N times. Find EV of the biggest score.
A few possible solutions.
Birthdays You teach informatics in a class with 20 students. When someone has a birthday, you must let the whole class to play games instead of learning algorithms and using Excel. Maybe some students have birthday on the same day, so there would be fewer than 20 wasted days during a year? Find EV of the number of days when at least one student has birthday.
Bonus/fact: Birthday paradox.
First heads Find EV of the number of coin tosses until you get heads.
How to check your answer with a program?
Two heads Find EV of the number of coin tosses until you get heads two times in total.
Two heads in a row Find EV of the number of coin tosses until you get heads two times in a row.
Volleyball 12 teams, including Poland, play in the volleyball tournament. Teams are divided into 4 groups, each with 3 teams. In each group, every team plays against every other team, and then two best teams advance to the elimination stage. In case of a perfect tie, two random teams advance. The elimination stage has quarterfinals, semifinals and the final match. In every match, a random of two teams wins (50% each).
Find p-bility that Poland will win the whole tournament. Find EV of the number of matches won by Poland. Find EV of the number of matches won by Poland, assuming that they won the whole tournament (in other words, find EV of the number of matches won by the winner of the whole tournament).
Problems for "contribution" technique
Hills Given a sequence of length N (N ≤ 105), count triples of indices i < j < k that ai < aj > ak.
Bonus: Count zig-zags of length 10, i.e. i1 < i2 < ... < i10 that a[i1] < a[i2] > a[i3] < a[i4] > ... < a[i10].
Paths in tree Given a tree of length N (N ≤ 105), find the sum of lengths of all paths. (Solve this without not-trivial dp or centroids.)
Bonus: Find the sum over squares of lengths of paths.
Sum over subsets There are N competitions, the i-th with prize ai. You're quite good and you will win each competition with p-bility 50%. Find EV of the total won prizes.
Equivalently: Find the sum over total prize over all 2N possibilities, and print answer modulo 109 + 7. (This answer divided by 2N gives the answer from the first version.).
Math encoder (Code Jam Kickstart 2017 round B) You are given a sequence of N numbers (N ≤ 2000 or N ≤ 105). We're to choose one of 2N - 1 non-empty subsets, uniformly at random. Find EV of the difference between the maximum and minimum element in the subset.
Equivalently: Find the sum over the difference over all subsets, and print the answer modulo 109 + 7.
Imbalanced array (CF Educational Round 23) Same as the previous problem, but choose a random of N·(N + 1) / 2 intervals.
Bonus: Do it in O(N) if the input contains a permutation of numbers 1 through N.
Randomizer (CF 313 D) You're given a convex polygon with N vertices (N ≤ 2000 or N ≤ 105). We choose a random subset of vertices, what gives us a new (small) convex polygon. Find EV of the perimeter of the new polygon.
Well, the CF problem was a bit harder, with computing area and using Pick's theorem.
Random CH You're given N points (N ≤ 200 or N ≤ 2000), no three are collinear. Each point disappears with p-bility 50%. Find EV of the size of the convex hull of remaining points.
(The size of CH is the number of its vertices.).
Eating ends You're given a sequence of length N (N ≤ 2000 or N ≤ 105). N - 1 times we will remove the first or the last element, each with p-bility 50%. Find EV of the last remaining number.
Well, the implementation is hard because of precision issues.
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, including one that we will discuss in the next part.