ed1d1a8d's blog

USACO Cow Coupons
By ed1d1a8d, 10 years ago, In English

I'm having difficulty understanding the editorial for this problem: Cow Coupons. The editorial states that the algorithm is optimal because it chooses the minimum value for each cow added to the lineup. However, how do you know that we will never choose a cow with greater value, but that will contribute less to the "revoke" heap. I tried constructing a case as a counter-example, but obviously failed because the algorithm is correct. Additionally, I couldn't find a clear way to show why such a construction is impossible. My question is, why is the algorithm correct? I don't really get their explanation. Thanks.

  • Vote: I like it
  • +15
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Suppose we have k coupons to use.

Let the current set of cows you have selected thus far be S. Initially S is empty, and the greedy algorithm keeps on adding cows to S. We will prove that at each step, S is part of some optimal solution (i.e. there exists some optimal solution that contains S as a subset)

The base case is the empty set, which is trivially a part of any optimal solution.

For the inductive step, we assume that S is currently of some solution set. Now we want to add cow i. We want to show that S + i is also part of some optimal solution. There are two cases.

  1. |S| < k. Thus cow i is cow with lowest C_i. Let T be some optimal solution that contains S as subset. Choose any cow j in T\S that is bought with coupon. Such j must exist since |S| < k and it's always best to use all coupons. Then cost of T-j+i <= cost of T, so choosing cow i is optimal as well.

  2. |S| >= k. Thus, cow i is cow with min(P_i, C_i + (P_x — C_x)) for some x in S such that P_x — C_x is minimum. Again, consider some optimal solution T that contains S as subset.

Firstly, we look at the case where all cows in S hold on to their coupons (i.e. cows in S hold coupons according to current state of the greedy algorithm). This means no cow in T\S holds a coupon. Pick any cow j in T\S and swap that cow with cow i. Also, if P_i < C_i + (P_x — C_x), give the coupon of cow x to cow i. You can verify that this new arrangement has at least as low cost as T, thus selecting cow i is optimal.

Secondly, we look at the case where some cow y in S lost its coupon to some cow j in T\S. Swap cow i with cow j, and give the coupon of cow j to cow i. Again you can verify that this new arrangement is at least as good as T. Thus selecting cow i is optimal as well.

Thus we have completed proof of our inductive step.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For the case where some cow in y lost its coupon, what if C_i > C_j, wouldn't the new arrangement be worse?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You can assume that y == x, where cow x is cow in S with coupon that causes smallest increase in cost when coupon is revoked. (If cow x does not hold coupon in T, just set y := x. Otherwise, give the coupon of x to some cow z in S that got its coupon revoked in T). Then from the way you chose cow i , which is min(P_i, C_i + (P_x-C_x)), it is guaranteed that switching cow i in does not increase the cost.

      → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I used a different solution for this problem. I don't know exactly why it works either, but it does since it passed all the tests.

What I did is the following: Insert into an array all the costs for all the cows together, both costs with coupons and without coupons and sort them by non-decreasing cost. Then iterate on the array and buy the cows greedily: you don't buy a cow only if your remaining money is not enough, if you have already bought this cow before with a coupon or if you have have no coupons left and this cost requires one.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +5 Vote: I do not like it

    How does this work for the following test case:

    2 1 10

    5 1

    100 3

    Doesn't your solution use the coupon on cow 1, and get an answer of 1? The answer is 2: use the coupon on cow 2.

    Am I missing something?

    EDIT: Wait, maybe you mean you only use the coupon if the full price is not payable at that moment, and otherwise just wait and (possibly) pay the full price later. That would pass my test.

    EDIT 2: Yeah, that makes sense, and it doesn't seem like it would be too hard to prove its correctness by some contradictions about choosing other than your algorithm does.

    EDIT 3: My new idea doesn't work either oops...For example it fails if you have enough coupons for every cow.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're right. That test would break my solution. It seems like the test cases are really weak.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I just came up with a solution off the top of my head right now, but it seems too simple.

I keep a sorted list of both P and C. Then I take the first element of each list and compare them. If P is less, it gets removed from that list and bought. If C is less, I apply the coupon to the most expensive cow (I pop the end of P and the beginning of C) and buy the cow at price C. Repeat until the next cow to be bought is larger than remaining money.

Is this correct? If not, why?

→ Reply