Lucky Dip

Design a hardware module for the Lucky Dip redraw strategy.

You start with a bag containing n prizes with values v[0] through v[n - 1]. On each draw you may either keep the prize you got, or put it back and redraw uniformly from the same bag. You may redraw at most k times, and you always choose the action that maximizes the expected value.

Return the final expected value scaled by 1024.

Hardware I/O Encoding

• n is a scalar unsigned 4-bit integer
• k is a scalar unsigned 4-bit integer
• v is a one-dimensional stream of unsigned 9-bit integers
• the output is a scalar unsigned 32-bit integer equal to floor(expected_value * 1024)

Recurrence

Let e0 = floor(sum(v) * 1024 / n). For each redraw step,

• e(i + 1) = floor(sum(max(v[j] * 1024, e(i))) / n)

The answer is e(k).

Example

• input n = 5, k = 1, v = [10, 20, 30, 40, 50]
• initial expected value: floor(150 * 1024 / 5) = 30720
• next expected value: floor((30720 + 30720 + 30720 + 40960 + 51200) / 5) = 36864
• output: 36864

Source inspiration: Google Kick Start 2018 Round A - Problem B: Lucky Dip.