Editorial for UTS Open '18 P4 - Ianine's Lil Lab
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Each coupon has a pair , the number of keyboards and monitors that it can buy.
coupons cannot buy anything, and can be ignored.
and
coupons should always be used to buy keyboards, while
and
should be used for monitors. When deciding how to spend the
coupons, first count how many keyboards and monitors you will get from the
and
coupons, then use any
coupons for the item that you have less of.
Time Complexity:
Subtask 2
There are ways to spend each coupon, which makes
ways in total. Loop through all
possibilities and choose the best option.
Time Complexity:
Subtask 3
First, group the coupons by value. For each group, sort them in order of decreasing (which is also increasing
, since they have the same value). Then, the coupons at the front will have the highest
, while the ones at the back have the highest
. Suppose you used a coupon on monitors, and used another coupon after it for keyboards. If instead you used the first one for keyboards and the second for monitors, you would have gotten more monitors and keyboards. Therefore, you should never use a coupon for monitors when a coupon behind it is used for keyboards, because there will always be a better way to use the coupons. In other words, the optimal way to spend the coupons is to use the first
for keyboards (for some
, where
is the size of the group of coupons with value
), and the last
coupons on monitors.
Using a precalculated prefix sum array, we can loop through to find the best choice of in
time. Do this for each group, and choose the group with the best final result.
Time Complexity:
Comments