Editorial for DMOPC '15 Contest 3 P5 - Total Annihilation
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Knowledge required: meet-in-the-middle
Anyone with knowledge of the subset sum problem probably recognized this problem immediately. For anyone who does not know, the subset sum problem is one of the most famous NP-complete problems, you can learn more about it here.
If we add all samples to one array, with the antimatter samples being negative, the problem is reduced to finding the number of subsets that sum to .
The naive
solution involves iterating over all possible subsets using bitmasks.
For full points, we use a technique called meet-in-the-middle. Similar to divide and conquer, we divide the array into
equally sized arrays.
In the first half, we use the same naive technique to find all subset sums and cache them.
For each subset sum
in the second half, we look for the number of occurrences of
in the cached results.
This can be done by using either binary search or a map.
Time Complexity:
Bonus: Can you solve this problem using meet-in-the-middle?
Comments