Easy problems in the last two contests, but I didn’t solve them quickly because of formulas with expected values

839C: Journey

Idea 1

ans = sum of (Pr(leaf) * Depth(leaf)) . Pr(leaf) can be calculated in DP steps, while we can calucate Depth(leaf) in separate DFS, and when we reach the leaf

Idea 2

For each tree, ans(root) = sum of (ans(leave)/k) + 1. This formula works because all leaves increase depth by 1, therefore, we can abstract all 1s out

841C: Leha and function

Intuition is obvious, but how to prove it? I used experimentation to prove the greedy solution - a slow approach.

For any K-size subset in N, we can use a bijection to represent it as a list of deltas d(1), d(2), …..d(k), d(k+ 1), where d(1) = a(1), sum of all d(i) = N + 1, i.e., d(k+1) = N + 1 - a(K)

Since this applies to any K-size subset in N, we know Ex(d(1)) + Ex(d(2)) + … = N + 1, because of linearity of expected value

The hard part is to prove E(d(1)) = (N + 1) / (K+ 1)

Idea 1

Use hockey-stick identity!

sum of [r, n] choose(i , r) = choose(n+ 1, r+1)

Idea 2

Note that if we swap any d(i) and d(j), and keep others same, the corresponding a(i) is still valid, i.e., d(i) and d(j) follow the same distribution => Ex(d(i)) = Ex(d(j))