Last active
March 20, 2018 03:35
-
-
Save py-in-the-sky/ab54a2de17b2c5379f6fa1b6946a588d to your computer and use it in GitHub Desktop.
Solution to Google Code Jam Problem "Lucky Dip"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| Lucky Dip: https://codejam.withgoogle.com/codejam/contest/9234486/dashboard#s=p1 | |
| Concept Inventory: | |
| * Optimal Play: To play optimally, you choose to redip if your current | |
| dip's value is less than the expected value of redipping. Otherwise, | |
| you stick with your current draw. | |
| * Expected Value of a Dip: The expected value of a dip, given that the player | |
| plays optimally, depends on the probability of drawing a value that is less | |
| than the expected value of redipping. It is the sum of the following two | |
| computations: | |
| * The expected value of redipping times the probability of redipping being | |
| optimal (i.e., of drawing a value less than the expected value of redipping). | |
| I.e., if the expected value of redipping is E and there are L such values, | |
| then: E * L / N. | |
| * The probability of drawing a value greater than or equal to the expected | |
| value of redipping times the expected value of such a draw (i.e., the | |
| probability of redipping being suboptimal times the average of all the | |
| values that are greater than or equal to the expected value of redipping). | |
| I.e., if there are M such values and the sum of all such values is S, then: | |
| S/M * M/N = S/N. | |
| """ | |
| from bisect import bisect_left | |
| ### Iteration 3 ### | |
| def solve_even_faster(N, K, V): | |
| """ | |
| Runtime: O(N * logN + K); Extra Space: O(N) | |
| Note that for a given V, expectation_of_next_dip will never | |
| decrease as K increases. | |
| """ | |
| v = sorted(V) # O(N * logN) | |
| n = float(N) | |
| tail_sum = sum(v) # O(N) | |
| expectation_of_next_dip = tail_sum / n | |
| i = 0 | |
| for _ in xrange(K): # O(K) | |
| while v[i] < expectation_of_next_dip: | |
| # This loop is O(N) over the life of the algorithm. | |
| tail_sum -= v[i] | |
| i += 1 | |
| # x < expectation_of_next_dip for x in v[:i] | |
| # y >= expectation_of_next_dip for y in v[i:] | |
| expectation_of_next_dip = (expectation_of_next_dip * i / n + | |
| tail_sum / n) | |
| return expectation_of_next_dip | |
| ### Iteration 2 ### | |
| def solve_fast(N, K, V): | |
| "Runtime: O(logN * (N + K)); Extra Space: O(N)" | |
| v = sorted(V) # O(N * logN) | |
| n = float(N) | |
| v_tail_sums = tail_sums(v) # O(N) | |
| expectation_of_next_dip = v_tail_sums[0] / n | |
| for _ in xrange(K): # O(K * logN) | |
| # Partition values into those less than the expected value of | |
| # redipping and those greater than or equal to it. | |
| # The first i values are less than the expected value of | |
| # redipping; the last (N - i) values are greater than or | |
| # equal to it. | |
| i = bisect_left(v, expectation_of_next_dip) # O(logN) | |
| expectation_of_next_dip = (expectation_of_next_dip * i / n + | |
| v_tail_sums[i] / n) | |
| return expectation_of_next_dip | |
| def tail_sums(arry): | |
| "Runtime: O(N); Extra Space: O(N)" | |
| running_sum = 0 | |
| tail_sums_array = [0] * (len(arry) + 1) # O(N) | |
| for i in reversed(xrange(len(arry))): # O(N) | |
| running_sum += arry[i] | |
| tail_sums_array[i] = running_sum | |
| return tail_sums_array | |
| ### Iteration 1 ### | |
| def solve_slow(N, K, V): | |
| "Runtime: O(logN * K * N); Extra Space: O(N)" | |
| v = sorted(V) # O(N * logN) | |
| n = float(N) | |
| expectation_of_next_dip = sum(v) / n # O(N) | |
| for _ in xrange(K): # O(K * N * logN) | |
| # Partition values into those less than the expected value of | |
| # redipping and those greater than or equal to it. | |
| # The first i values are less than the expected value of | |
| # redipping; the last (N - i) values are greater than or | |
| # equal to it. | |
| i = bisect_left(v, expectation_of_next_dip) # O(logN) | |
| expectation_of_current_dip = expectation_of_next_dip * i / n | |
| for j in xrange(i, len(v)): # O(N) | |
| expectation_of_current_dip += v[j] / n | |
| expectation_of_next_dip = expectation_of_current_dip | |
| return expectation_of_next_dip | |
| def main(): | |
| T = int(raw_input()) | |
| for t in xrange(1, T+1): | |
| N, K = map(int, raw_input().split()) | |
| V = map(int, raw_input().split()) | |
| # print 'Case #{}: {}'.format(t, solve_slow(N, K, V)) | |
| # print 'Case #{}: {}'.format(t, solve_fast(N, K, V)) | |
| print 'Case #{}: {}'.format(t, solve_even_faster(N, K, V)) | |
| if __name__ == '__main__': | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment