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.
Thanks very much for this explanation. I’m confused about one thing: you’re mentioning purchasing exactly x buckets, but can’t it sometimes be cheaper to purchase more than x buckets if there’s a particularly good deal with a very large number of buckets? Say you can purchase 2^{50} buckets for $ 1?
Initially you use N to mean the number of deals, but it seems like you are using N later to mean the among the deals, you are referring to the N^{th} deal.
If we take more than one deal \lfloor x/b_N \rfloor times, why wouldn’t that sometimes go over x? For example if the deals are $2 for 4 buckets, and $7 for 8 buckets, and then we have x=15 buckets, if we take the first deal 3 times and the second deal 1 time, that we would have 20 buckets. There must be some reason we wouldn’t to that, but I don’t follow it.
Would this be simpler if you just proved subtask 2?
For me the exercise for the reader is to understand the proof. I’m studying discrete mathematics through Coursera and AOPS but I’m not to the point where I can generate the proofs myself. By the way, I’m not a high school student, but I’m helping a high school relative who is really enthusiastic about USACO, so I explain the problems to her that she can’t get. I took some discrete math classes in college and did ok in competitive math in high school, so I have enough background to understand the proofs eventually.
