Description
Lucky Dip
Design a hardware module that optimizes bag selection strategy. Given N bags with value distributions, calculate the optimal expected value when you can inspect K bags and take the maximum, or take a guaranteed uniform random value from remaining bags.
Example: 5 bags with values [10,20,30,40,50]. With K=2 inspections, calculate optimal expected value strategy.
Source: Google Kickstart 2018 Round A - Problem B: Lucky Dip
Input
n
32-bit Unsigned IntegerNumber of bags.
k
32-bit Unsigned IntegerNumber of draws.
v
Stream of 32-bit Unsigned IntegerValues in each bag.
Output
64-bit Unsigned Integer
Expected value after k draws (scaled).