PROBLEM LINK:
Author: Roman Furko
Tester: Istvan Nagy
Editorialist: Xellos
DIFFICULTY:
MEDIUM
PREREQUISITES:
Dynamic programming, bitmasking, greedy algorithms.
PROBLEM:
There are N items and M discounts - subsets of the items. Each item has a price. You may choose any number of disjoint discounts and pay for all items except the cheapest item in each discount. You may also permute the prices in any way. Find the minimum price to pay.
QUICK EXPLANATION:
Solve the subproblem where you know the chosen discounts. Sort the discounts and prices, use a subset DP to compute the answer.
EXPLANATION:
Note: in this problem, subsets S \subset \lbrace0,1,..,N-1\rbrace should be represented by bitmasks. The intersection of two such subsets s_1 and s_2 can be found easily as s_1\&s_2 (bitwise and), their union as s_1|s_2 (bitwise or); if they’re disjoint, their union is simply s_1+s_2. Those operations work in O(1).
Small bounds mean exponential solutions (or old Topcoder). That means we probably want some subset DP that maximises our savings (the answer is just the sum of all prices minus the amount we saved using discounts), but that’s complicated by the fact that we can permute price tags. How should we assign them?
We have a subproblem to solve here: if we knew which discounts will be used, what’s the optimal assignment of price tags?
Let’s sort those tags first in an array \texttt{tags}[] - their starting order doesn’t matter, anyway. If the smallest discount offer is for at least d_1 items, then the largest d_1-1 prices must be paid. The d_1-th largest price can be discounted (i.e. not paid - literally “not counted” / “uncounted” towards the final price), but only if we pack the largest d_1 into that smallest discount offer. Similarly, if the second smallest discount offer is d_2, then the d_1+d_2-th largest price is the next one which can be discounted, and so on. This greedy assignment is really optimal, since for each k, the k-th largest discounted price is the maximum possible, so their sum - our savings - is the maximum possible.
That means we need to sort the discounts by their size - the number of items in them. We’ll process them in the order from smallest to largest and do a DP on an array \texttt{maxdisc}[s] - the maximum amount we can save if the union of discounts used so far is a subset s. When processing a discount that can be applied on a subset s_d, then we can ignore it (which doesn’t change \texttt{maxdisc}[]) or use it. We can use it if the subset s of items used in discounts so far was disjoint with s_d, which gives \texttt{maxdisc}[s+s_d]=\texttt{maxdisc}[s]+\texttt{tags}[|s+s_d|] (the array \texttt{tags}[] is sorted in non-increasing order here). Overall, we get
for s\&s_d=0.
The straightforward way to update \texttt{maxdisc}[], which involves trying all s and checking if they’re disjoint, won’t work here, since that takes at least O(M2^N)=O(4^N) time. For each discount, we need to efficiently enumerate all subsets s disjoint with it and only update \texttt{maxdisc}[s+s_d] for them; that will work fast enough, since the number of subsets s disjoint with some s_d is 2^{N-|s_d|} and the number of subsets s_d of size |s_d|=k is N\choose k, so are at most \sum_{k=0}^N {N\choose k} 2^{N-k}=(2+1)^N=3^N (we un-expanded the sum using the binomial theorem) subsets s disjoint to all possible distinct s_d. And if we have several identical discount offers, we can ignore all except one of them without affecting the answer.
As it works in reality, we don’t actually need to buy everything in discounts only (which may be impossible, anyway), any items can still be bought normally. Therefore, the maximum savings at the end are given as the maximum \texttt{maxdisc}[s] over all subsets s bought in discounts only; as mentioned already, to get the answer, we should subtract the savings from the sum of all prices.
Generate subsets s disjoint to s_d is actually quite simple - just find the items that aren’t in s_d, keep a list of subsets s generated so far and process those items one by one; for each item, take the subsets generated so far and generate two copies for each - with and without that item. Each subset is only generated once, so K subsets can be generated in time O(N+K).
We’ve got all that’s necessary now. If we precompute the sizes of all subsets in O(N 2^N), then the number of operations in the DP is O(3^N); even listing all disjoint pairs of subsets takes just O(3^N) as well, so the total time complexity is O(3^N); since we only need to remember them at each step, the memory spent is O(2^N).
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.
)