PROBLEM LINK:
Author: Constantine Sokol
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang
DIFFICULTY:
Easy
PREREQUISITES:
Search
PROBLEM:
Given N objects and M weighted subsets of them, find a combination of subsets, such that all objects are covered at most once and the sum of the weights are maximized.
Some test cases are added in the practice room.
EXPLANATION:
Although N is large, M is quite small such that 2^M is tolerant. Therefore, we first need to construct the conflicts between different subsets. Two subsets are called conflict if and only if they shares a common object. To get this conflicts table, on each object, we can restore the IDs of subsets who contain the object. And then, mark they are conflicted with each other. This step takes O(N * M^2). Moreover, we can reduce the time complexity using the binary expression as following.
conflict[li] = 0;
[/li] For i = 1 to N do
int mask = 0;
For ID in IDs[i] do
mask |= 1 << ID;
end
For ID in IDs[i] do
conflict[ID] |= mask;
end
end
where, conflict[i] >> j & 1 stands for whether the i-th and j-th subsets are conflicted with each other. This code needs only O(NM) time.
And then, a simple DFS search can be applied to find the maximum weighted valid choice, like following:
int DFS(int i, int mask, int sum)
if (i == M) {
return sum;
}
int ret = DFS(i + 1, mask, sum); // don't select the i-th subset
if (mask >> i & 1) {
// conflicted, can't be chosen.
} else {
// try to select the i-th subset
ret = max( ret, DFS(i + 1, mask | conflict[i], sum + weight[i]);
}
return ret;
end
This procedure takes O(2^M) time. Therefore, the overall time complexity is O(NM+2^M).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
