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 (~10\,000~ or ~100\,000~) 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 ~100~ times came up with correct answers ~9~ times out of ~10~.

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 BOGOs). 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.