Editorial for ECOO '13 R1 P4 - Coupon Day
Submitting an official solution before solving the problem yourself is a bannable offence.
Recommended Approach
I think the best approach is to treat the BOGO
coupon separately from the other coupons. If there is no BOGO
, use a backtracking search, trying each coupon on each unused price. But if there is a BOGO
, first try the backtracking search without that coupon, then sort the prices in ascending order, apply the BOGO
to each adjacent pair of prices, then use the backtracker to fill in the rest. Keep track of the best score from all these searches and print it out. If done correctly, this approach is guaranteed to find the optimal solution. It is also possible to solve this a bit more quickly with a "best first" search, but this is more complicated and involves the use of a priority queue structure.
Random Approach
Because the problem size is so small, a random search works quite well too. In this approach, you simply randomly pair items to coupons and compute the resulting price. Do this a bunch of times ( or ) and you are almost guaranteed to come up with the correct answer, making this a great strategy for the purposes of this contest. When the random search was coded by one of the problem testers, even iterating times came up with correct answers times out of .
Greedy Approach
You can get a long way substituting a greedy algorithm for the backtracker in the recommended approach above. The greedy algorithm repeatedly looks for the best price-coupon pairing and applies it. If there is a tie among the flat coupons, it chooses the one that is least wasteful (e.g. if the best is $10 coupon applied to either $53 or $14, apply it to $14.) This works for about 90% of test cases, but there are still a few where it does not. For example, prices 88.17, 43.18, 67.14, 2.51 and coupons 20%, 20%, $50, $50. Greedy wants to apply the $50 coupons to the two highest prices, but the better solution is to apply it to the middle two and use a 20% coupon on the other two. It is also possible to do the greedy but mess up the BOGO
(e.g. include it in the regular greedy search instead of exhaustively trying all BOGO
s). This is a problem when there is a two-coupon combo that beats the BOGO
.
Pitfalls
There is a catch in the TAX
coupon. When you calculate the savings on the $5, $10, and $50 coupons, you must take the savings in HST into account as well. Otherwise there is a small range of dollar values where you will mistakenly think the TAX
coupon saves you more than the other one. For $5, the range is $39-$43. For $10, it's $77-$86. And for $50, it's $385 to $434. You also have to be very careful with rounding in this problem, and when reading the numbers from the file you should apply rounding to the numbers you get because of possible floating point precision errors.
Test Cases
The contest team coded 6 solvers. Greedy, Greedy with the BOGO
mistake above, Greedy with the TAX
mistake above, a backtracker, best first, and a random search. Each set of test cases has one case that works with all four approaches, and then at least two that fail on the Greedy version and then one that fails on the versions that have bad BOGO
and bad TAX
calculations. Backtrackers or random search algorithms with the TAX
mistake might also fail on some cases.
Comments