Editorial for IOI '16 P1 - Detecting Molecules


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.

Subtask 1 is a special case. Iterate all possible k \le n, and try to take exactly k molecules.

Subtask 2 is a special case. Iterate all possible k_1, k_2 : k_1+k_2 \le n, try to take exactly k_1 molecules of minimal weight and exactly k_2 molecules of maximal weight.

Subtasks 3 and 4 may be solved using dynamic programming. The task is a classic knapsack problem. Use \mathcal O(nu) of time, and \mathcal O(u) of space.

You may optimize the dynamic programming, use bitset and you'll pass Subtask 5.

We suggested, a contestant who solves Subtasks 5 and 6 will invent a greedy approach. If you implement greedy in \mathcal O(n^2), you'll pass only Subtask 5. Good time to pass Subtask 6 is \mathcal O(n \log n).

There are 3 correct greedy solutions. All of them start with sorting the array of weights in nondecreasing order.

Greedy 1. Let fix k, number of molecules to take. We can choose set of size k with sum in [l \dots r] iff minSum[k] \le u and maxSum[k] \le l. Where minSum[] is partial minimums on prefixes and maxSum[] is partial maximums on suffixes. Both of them may be precalculated in \mathcal O(n).

Proof. Let's take minimal possible k molecules, its summary weight does not exceed l. Let's change the set smoothly from "k minimal molecules" to "k maximal molecules". One step: drop any one molecule, and take any other. Each step changes the sum by at most u-l. The last value of the sum is at least l. So one of the intermediate steps gives l \le sum \le u. ■

Greedy 2. There exists an answer which forms a segment. Use two pointers to find it in \mathcal O(n).

Proof. Let's fix k – number of molecules in the answer. The smallest k molecules form the leftmost segment, and the biggest k form the rightmost segment. Let's change the set smoothly from "the leftmost segment" to "the rightmost segment". One step: drop the leftmost molecule, and add a new one at the right. ■

Greedy 3. There exists an answer which forms a union of prefix and suffix. Use two pointers to find it in \mathcal O(n).

Proof. Let's fix k – number of molecules in the answer. The smallest k molecules form prefix, the biggest k form suffix. Let's change the set smoothly from "prefix" to "suffix". One step: make prefix shorter by one, make suffix longer by k. ■


Comments

There are no comments at the moment.