Include-exclude dynamic programming method
There are N soldiers (numbered from 1 to N). Each soldier has several skill subsets from M different skills (numbered 1 through M). A recruitment of an army is a collection of mercenary units of its constituent soldiers. How many different subsets of soldiers satisfy that have specific skill requirements Problem
In accordance with the task, the Explanations is reduced to finding the number of subsets of these numbers, the OR of which is exactly equal to the required value, for example, req
Let f (i) be the number of numbers j such that j OR i = i. Then the answer is Ξ£i (-1) ^ popcount (i xor req) (2 ^ f (i) - 1) for all i such that i OR req is req
How does this formula come from and how does popcount describe what it is added or subtracted.
source to share
Here's my example. The way to solve it: instead of thinking about groups that have a certain set of skills, let the mind be in groups of soldiers who do not have certain skills.
Since this second property spreads well from the group to all members.
Before we start, a little oversimplification:
Without loss of generality, we can filter out soldiers with at least one skill outside the required set. Since the skills of a subset must be exactly the skill set required, those smart soldiers who know too much will never be needed.
From this point on, we assume that the required skill set {1, ... , R}
and that the skills of the soldiers are in between 1
and R
.
We'll need this definition A_i
(where i
belongs {1,..,R}
):
A_i
: A set of groups of soldiers with skills i
in their group skill set .
In other words, a group of A_i
( inter
means intersection) is a group in which at least one soldier has a skill number i
.
Now if i<j
,
A_i inter A_j
= groups of soldiers with skills i
and j
in their group skill set .
In other words, a group from A_i inter A_j
is a group with at least one of the properties
- one soldier with both skills
i
andj
. - two soldiers, one with knowledge
i
, one with knowledgej
.
AND
A_1 inter A_2 ... inter A_R
is a set of groups of soldiers that have skills 1,.., R
in their group skill set.
The question that is asking the problem can be expressed with A_i
:
What's the size A_1 inter A_2 ... inter A_R
?
It is equal
2^2^R - size( comp(A_1) union comp(A_2) ... union comp(A_R) )
where comp(A)
is an additional set.
Now we can apply the principle of exclusion of inclusion.
There is one more trick to make it computable:
If i
s is a subset {1,..,R}
, then groups from
intersection(comp(A_j) for all j in I)
- groups of soldiers without skills (as a group) c i
. Note that a soldier in such a group is definitely a soldier who has no skills in i
. Define g(I)
as the number of soldiers who do not have the skill set i
. Moreover, we have
size( intersection(comp(A_j) for all j in I) ) = 2^g(I)
In the end, I have the result:
2^2^R - sum( (-1)^(size(I)+1) * 2^g(I) , for each I subset of {1,..,R} and I non-empty)
Hope this helps. Let me know if anything else is unclear.
source to share