The problem is classic, given 6 people, either there is a group of 3 who know each other, or there is a group of 3 who do not know each other, assuming the known relationship is bidirectional.
Proof from West's Graph Theory book.
Use pigeon-hole principle, among 6 nodes, in G and ~G, at least one of them have deg 3, because deg_G(v) + deg_~G(v) = 5. Let's say it is G, and node v has deg >= 3. Now we consider 3 neighbors of v, none of them have an edge between them, otherwise we have a triangle. It follows that the three neighbors form a triple with no edges.
Thursday, February 4, 2016
Tuesday, February 2, 2016
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.
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
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.
Subscribe to:
Posts (Atom)
