PROBLEM LINK:
Author: Sergey Kulik
Tester: Misha Chorniy
Editorialist: Pawel Kacprzak
DIFFICULTY:
EASY
PREREQUISITES:
Dynamic programming, bits
PROBLEM:
There are N meals to buy numbered from 1 to N. The i-th meal can be bought separately for price C_i. Meals can also be bought in sets. There are M sets and each set consists of some meals. The prices of the i-th set is P_i. The goal is to buy all N meals for the lowest possible price. In one test file there are multiple test cases to handle.
QUICK EXPLANATION:
The main idea is to use dynamic programming and bitmasks to compute dp[mask] as the smallest possible cost of buying elements set in the mask.
EXPLANATION:
In subtasks 1 and 2 methods based on computing the exactly value of dp_1 defined in the explanation for subtask 3 below might be used. In particular let dp[mask] be the lowest price to buy meals in mask. Then one possible idea for lower constrains is to iterate for all possible masks and for each single one, iterate over all possible seats of meals and try to lower the cost of meals covered by the current mask and the set of meals by combining their costs.
Subtask 3
First of all, notice that buying all meals is always possible, because they all can be bought separately. However, the price can be reduced by buying the meals in sets.
Let dp_1[mask_1] be the smallest price for buying meals in mask_1 using a single purchase - so using either a single purchase of a separated meal or a single purchase of a set of meals
Let dp_2[mask_2] be the smallest price for buying meals in mask_2 using any purchases.
Clearly, dp_2[mask_2] for mask_2 containing N ones is the final answer.
At the beginning, we can set values of dp_1 and dp_2 to some extremely large values in order to simplify the implementation.
The first step towards the solution is to compute dp_1 values for all possible 2^N masks. Later we are going to use these values to compute values in dp_2.
Let mask_{separete, i} be the mask corresponding the meal i. Moreover, let mask_{set, i} be the mask corresponding to the i-th set of meals. Initially, we set:
dp_1[mask_{separete,i}] = C_i for all i = 1, 2, \ldots, N.
Then, we set:
dp_1[mask_{set, i}] = \min(dp_1[mask_{set, i}], P_i) for i = 1, 2, \ldots, M.
Since buying a set of B meals might be the cheapest way to buy a set of A meals for A < B, then we are going to try to lower these costs as follows:
for (int mask = (1 << n) - 1; mask >= 0; —mask) {
for (int j = 0; j < n; ++j) {
if (mask & (1 << j)) {
dp_1[mask ^ (1 << j)] = min(dp_1[mask ^ (1 << j)], dp_1[mask]);
}
}
}
The thing to notice there is that we iterate from the masks containing the most meals to the masks containing less meals in order to try to reduce their prices. Notice that \texttt{mask ^ (1 << j)} is the mask with the j-th bit set to 0.
After than, we are ready to compute the values of dp_2. The idea is very simple, for a given mask we are going to iterate over all submasks of mask and ty to add a single meal to them to expand it to mask:
dp_2[0] = 0;
for (int mask = 0; mask < 1 << n; ++mask) {
int submask = (mask - 1) & mask;
while (submask > 0) {
dp_2[mask] = min(dp_2[mask], dp_2[submask] + dp_1[mask ^ submask])
submask = (submask - 1) & mask;
}
}
The above method has time complexity O(2^N \cdot N + 3^N), where the first part is the complexity of calculating dp_1 values and the second part is the complexity of calculating dp_2 values. While the complexity of the first part is quite obvious, the complexity of the second part needs an explanation. For each mask, we iterate over all its submasks. We know that there are \binom{N}{k} masks with k ones and each such mask has 2^{N-k} submasks. Thus the number of iterations during computation of dp_2 can be measure as \sum\limits_{k=0}^N \binom{N}{k} \cdot 2^{N-k} = 3^N.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
