Facebook Hacker Cup Round 2

Problem B: Carnival Coins.

Problem: You play a game with N coins. Each round you can use some number of coins and flip all of them. If the number of heads is at least K, then you win a point. You keep playing until all N coins are used. Calculate the expected number of points, assuming you play optimally. Flipping a single coin turns head with probability P.

Constraints: N <= 3000, K <= N, 0 <= P <= 1

First, we can calculate the probability prob[n][k], getting exactly k head when flipping n coins. Then it is easy to get cum[n] which is the probability to get at least K heads with n coins.

prob[n][k] = P * prob[n-1][k-1] + (1-P) * prob[n-1][k]
and prob[0][0] = 1.0

cum[n] = prob[n][K] + prob[n][K+1] + ... + prob[n][K]

Next, we need to compute dp[n], which is the expected number of points with n coins, if play optimally.
dp[n] could be cum[n] if we flip all n coins at once. Or we could split n coins into two subsets, one with j coins and the other with n-j coins, for j = 1 to n-1. Then dp[n] is the max among cum[n], dp[1] + dp[n-1], ..., dp[n-1] + dp[1]

Implementation is straightforward.

During contest, I missed both observation. Was calculating prob[n][k] using binomial coefficients and N=3000 is simply too big for double. Didn't see the recurrence. Also not seeing the simple dp to split coins into two subproblems.

===========================================
Problem  C : Snakes and Ladders

This problem looks intimidating, as N is 200000, so we need a O(nlogn) solution. What I have observed during contest:
1. It might help to find ladders with same height and no higher ladders in between. This is because for such ladders, any pair can hang a snake.
2. To compute the sum (X_j - Xi)^2, we can actually compute this sum in linear time.

Looking at the sum again, it is actually simple.
sum_(1<=i= sum_(1<=i= (n-1) * sum_(1<=i<=n) X_i^2 - second

while second = (sum_(1<=i<=n) X_i)^2 - sum_(1<=i<=n) X_i^2

To partition snakes into adjacent sets, we process each ladder in order of their x-value, and maintain a stack of previous heights in decreasing order. For each ladder, it kills all previous smaller heights, and append the current height to end of stack.