Editorial for TLE '16 Contest 4 P5 - Buying Gifts

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: d

For the 5% subtask, there is one gift type. Sort the shops according to their prices, and pick the $N$ ~N~ cheapest shops. The cost of one gift is the $N^{th}$ ~N^{th}~ shop's price.

Time complexity: $\mathcal{O}(S \log S)$ ~\mathcal{O}(S \log S)~ or $\mathcal{O}(S^2)$ ~\mathcal{O}(S^2)~

For the 15% subtask, there are exactly two gift prices. This was intended to be an easier version of the 60% subtask.

Time complexity: $\mathcal{O}(S^2)$ ~\mathcal{O}(S^2)~

For the 20% subtask, it is possible to choose $N$ ~N~ out of the $S$ ~S~ possible stores. For each combination, calculate the total price if these $N$ ~N~ stores were chosen. The answer is the minimum total price out of all the combinations.

Time complexity: $\mathcal{O}(2^S \cdot S \cdot T)$ ~\mathcal{O}(2^S \cdot S \cdot T)~

There are two different ways to approach the 60% subtask.

The first approach is to notice that there are at most $S^T$ ~S^T~ possible combinations of gift prices. For each possible list of prices, it is possible to count the number of stores that can be used. This simplifies to calculating a $T$ ~T~-dimensional prefix sum array, which takes $\mathcal{O}(2^T \cdot S^T)$ ~\mathcal{O}(2^T \cdot S^T)~ for the inclusion-exclusion approach, and $\mathcal{O}(T \cdot S^T)$ ~\mathcal{O}(T \cdot S^T)~ for the dimension-by-dimension approach. Out of all the combinations, the elements with a value greater/equal to $N$ ~N~ should be considered for the final answer, since these elements allow you to visit at least $N$ ~N~ shops.

Time complexity: $\mathcal{O}(T \cdot S^T)$ ~\mathcal{O}(T \cdot S^T)~

The second approach also uses the fact that there are at most $S^T$ ~S^T~ combinations of gift prices. The first gift's price is set to one of the $S$ ~S~ possible values. Then the second gift's price is set, and so on until a final list of prices is reached. This can be done recursively. However, this approach might be very slow, so bitmask can be used to decrease runtime. A shop's availability can be stored as a bit in memory, which allows for quick calculations and bit counting. Every time a price is set, some random shops become unavailable (due to the price being way too low for the shop). A recursive implementation can be made extremely fast by removing branches that cannot yield any solution / a better solution. One drawback is that the first two subtasks need to be coded separately.

Time complexity: $\mathcal{O}(S^T)$ ~\mathcal{O}(S^T)~

Comments

There are no comments at the moment.