You need to buy n units, one unit at each of n consecutive moments. At each moment a market price appears, drawn independently and uniformly at random from the interval [a, b] (a continuous distribution). After seeing it you must buy the unit right then, in one of two ways:
- pay the market price you just saw, or
- call your broker, who always charges the fixed price
p. You may call the broker at mostktimes in total.
You know n, a, b, k and p in advance and play optimally to minimise what you pay. Write
def optimal_execution_cost(n: int, a: int, b: int, k: int, p: int) -> float
returning the expected total amount paid for all n units under the optimal policy. Answers within 1e-6 relative error are accepted.
Example: n = 1, a = 0, b = 10, k = 1, p = 4. Use the broker whenever the price is above 4. Expected cost: 0.4 * 2 + 0.6 * 4 = 3.2.
Constraints: 1 <= n <= 600, 0 <= k <= 10**3 (k may exceed n), 0 <= a <= b <= 10**4, 0 <= p <= 10**4. Trying both choices recursively without memoisation is exponential; aim for O(n * min(n, k)).
Hint: Seeing price x, compare paying x now plus the cost of the rest with calls kept, against paying p plus the cost of the rest with one call fewer. The better choice switches at a threshold on x, so the expected cost of one step is an expectation of min(X, t) for some t.
Hint: Work out E[min(X, t)] for X ~ Uniform(a, b) carefully, including when t falls outside [a, b] and when a == b.
Show hint
Describe the situation before each purchase by two numbers: how many units are still to buy and how many broker calls are left. With no calls left you always pay the market, u * (a + b) / 2 for u units.