Editorial for UTS Open '18 P4 - Ianine's Lil Lab


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: PlasmaVortex

Subtask 1:

Each coupon has a pair (K, M), the number of keyboard and monitors that it can buy. (0, 0) coupons cannot buy anything, and can be ignored. (1, 0) and (2, 0) coupons should always be used to buy keyboards, while (0, 1) and (0, 2) should be used for monitors. When deciding how to spend the (1, 1) coupons, first count how many keyboards and monitors you will get from the (2, 0) and (0, 2) coupons, then use any (1, 1) coupons for the item that you have less of.

Time Complexity: \mathcal{O}(N)

Subtask 2:

There are 2 ways to spend each coupon, which makes 2^N ways in total. Loop through all 2^N possibilities and choose the best option.

Time Complexity: \mathcal{O}(N\cdot 2^N)

Subtask 3:

First, group the coupons by value. For each group, sort them in order of decreasing K_i (which is also increasing M_i, since they have the same value). Then, the coupons at the front will have the highest K_i, while the ones at the back have the highest M_i. Suppose you use 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 i for keyboards (for some 0\le i \le G_V, where G_V is the size of the group of coupons with value V), and the last G_V-i coupons on monitors.

Using a precalculated prefix sum array, we can loop through to find the best choice of i in \mathcal{O}(G_V) time. Do this for each group, and choose the group with the best final result.

Time Complexity: \mathcal{O}(N\log N)


Comments

There are no comments at the moment.