I’m a bit annoyed with the problem 3 official solution. It’s very brief and doesn’t elaborate the actual reasons or proofs for its claims. Looking at just subtask #2, there is a sentence that starts by giving the three possible number of purchases that we need to consider for each deal. It is followed by this sentence, "Once again, we don’t need to check for an intermediate number of deals because that will always be no better than taking it fewer or more times. "
I vaguely understand what the first half of the sentence is saying and I’m close to knowing enough to program it. But the proof of why this is true, the second half, is incomprehensible to me. Can someone explain it?
Oops, as someone who reviewed the analysis, I was mostly just checking for whether the claims looked correct as opposed to whether the claims were actually proved. But it’s a good exercise for the reader.
Suppose the i-th deal provides b_i buckets of milk where 1=b_1<b_2 < \dots < b_N and b_i|b_{i+1}. In this problem, b_i=2^{i-1}, but the same reasoning also works in the more general case.
Suppose we want to purchase exactly x buckets of milk. We’d like to show there’s an optimal solution for x that takes the N-th deal either 0 or q:=\lfloor x/b_N\rfloor times.
Let f(x) be the minimum cost to purchase exactly x buckets of milk. We claim that f(x)=q\cdot f(b_N)+f(x\% b_N). This would imply the conclusion since to purchase exactly b_N buckets of milk we’ll need to decide whether to take the N-th deal either zero times or one time, then we can repeat that decision q times.
It remains to show that for any way to purchase exactly x buckets, where x\ge b_N, there is always a subset of those deals that sums to exactly b_N buckets (implying f(x)=f(x-b_N)+f(b_N), and we can repeat this logic q times until x<b_N). Sort the chosen deals in decreasing order, and let p_i be the total number of buckets in the largest i deals. Then there exists some i such that p_{i-1}<b_N\le p_i. For such i we claim that b_N=p_i. This is true because \frac{p_{i-1}}{p_i-p_{i-1}}, \frac{b_N}{p_i-p_{i-1}}, \frac{p_i}{p_i-p_{i-1}} are all integers, and the first and last of these integers are exactly one apart.
