Dynamic Programming over Submasks (Submask DP) - Preparation to IOI Part 5
Dynamic Programming over Submasks (Submask DP)
Dynamic Programming over Submasks (Submask DP)
Introduction
Bitmask DP is dynamic programming over small sets. Instead of storing a whole list of chosen elements, we encode the set as one integer: each bit tells us whether one element belongs to the set.
This is useful when the number of elements is small, usually around 15 to 22, but the number of possible orders, groupings, or assignments is enormous. A mask gives us exactly 2n possible subsets, so we can often replace a factorial or much larger search with an exponential DP that is practical for small n.
Problem or motivation
There are n students and pairs of students who are in conflict. We must divide all students into the minimum possible number of teams. Inside one team, no conflicting pair is allowed.
m
We assume n≤16. Students are numbered from 1 to n in the input.
For example, suppose the conflict pairs are (1,2), (2,3), and (3,4). Two teams are enough: students 1 and 3 can form one team, while students 2 and 4 form the other.
Core concept
Representing a set with a mask
We use one bit for each student. In the implementation, student 1 corresponds to bit 0, student 2 to bit 1, and so on.
For n=4, the mask 11012 represents students 1, 3, and 4:
bit 0 is 1, so student 1 is present;
bit 1 is 0, so student 2 is absent;
bits 2 and 3 are 1, so students 3 and 4 are present.
The most common operations are:
test whether element v is present: (mask&(1≪v))=0;
add element v: mask∣(1≪v);
remove element v when it is known to be present: maskXOR(1≪v);
represent all elements: (1≪n)−1.
There are exactly 2n masks from 0 to 2n−1. The state mask=0 represents the empty set.
A mask is only a compact representation. The meaning of the DP state must still be stated precisely. Let dp[mask] be the minimum number of valid teams needed for exactly the students in mask.
The base case is dp[0]=0: no teams are needed for an empty set.
Enumerating every submask
The standard loop for all non-empty submasks of mask is:
It starts with the whole mask. After processing sub, the expression (sub−1)&mask produces the next smaller submask. Subtracting one moves to a smaller bit pattern, and the bitwise AND removes every bit that does not belong to mask.
These are exactly all non-empty submasks, each visited once. The empty submask is excluded by the condition sub>0. If a transition also needs the empty submask, it must be processed separately or the loop must use a careful break after processing zero.
Why the nested complexity is O(3n)
It is tempting to say that there are 2n masks and up to 2n submasks, giving O(4n). That bound is valid but not tight.
Across all pairs (mask,sub) where sub is contained in mask, every element has three possible roles:
it is outside mask;
it is inside mask but outside sub;
it is inside sub.
Therefore there are 3n such pairs in total. Enumerating every submask of every mask takes O(3n) time.
This distinction is important:
choosing one element in each transition usually gives O(n2n);
choosing an arbitrary submask usually gives O(3n).
Main algorithm
We need two pieces of information:
valid[mask] tells us whether all students in mask can be placed in one team;
dp[mask] stores the minimum number of valid teams covering exactly mask.
Precomputing valid teams
For each student v, store a bitmask conflict[v] containing everyone who conflicts with that student.
We could check every pair inside every mask, but validity can be computed more cleanly from a smaller mask. Take one bit firstBit from mask, let v be its student, and let rest be the mask after removing it. Then mask is valid exactly when rest is already valid and student v has no conflict with anyone in rest:
valid[mask]=valid[rest]∧((conflict[v]&rest)=0).
Thus every valid[mask] is computed in O(1) after valid[rest], for a total of O(2n).
DP transition
For a non-empty mask, choose one valid team contained in it. The remaining students are represented by maskXORteam, so the transition is
Every remaining mask is a proper submask of mask, so its numerical value is smaller. Therefore we can process masks in increasing order.
Anchoring one student
The same final partition can otherwise be generated in many different orders. For example, choosing team A and then team B describes the same partition as choosing B and then A.
To reduce this repetition, take the lowest set bit of mask and require the chosen team to contain that student. This does not remove any possible answer: in every partition, exactly one team contains the anchored student. We only need to decide which other students join that team.
Let firstBit be the bit of the anchored student and let other=maskXORfirstBit. We enumerate every submask extra of other, including the empty submask, and form team=extraORfirstBit.
Including extra=0 is essential because the anchored student may need to form a team alone.
Algorithm:
Implementation
Complexity
Valid-team precomputation:O(2n).
DP:O(3n); anchoring one student reduces repeated work but does not change the asymptotic bound.
Memory:O(2n+n).
1. Build the conflict mask of every student.
1.1. For every conflict pair (x, y), add y to conflict[x].
1.2. Add x to conflict[y].
2. Precompute which masks form valid teams.
2.1. Set valid[0] = true.
2.2. For every mask from 1 to (1 << n) - 1:
2.2.1. Let firstBit be the lowest set bit of mask.
2.2.2. Let v be the index of firstBit.
2.2.3. Set rest = mask XOR firstBit.
2.2.4. Set valid[mask] to true if valid[rest] is true and conflict[v] has no common bit with rest.
3. Initialize the DP.
3.1. Set every dp[mask] to infinity.
3.2. Set dp[0] = 0.
4. Compute all non-empty states in increasing order.
4.1. Let firstBit be the lowest set bit of mask.
4.2. Set other = mask XOR firstBit.
4.3. Enumerate every submask extra of other, including 0.
4.3.1. Set team = extra OR firstBit.
4.3.2. If valid[team] is true, minimize dp[mask] with dp[mask XOR team] + 1.
5. Output dp[(1 << n) - 1].
for(int sub = mask; sub > 0; sub =(sub - 1) & mask){ // use sub}
#include <bits/stdc++.h>using namespace std;const int N = 16;const int inf = 1e9;int conflict[N];bool valid[1<< N];int dp[1<< N];int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int x, y; cin >> x >> y; x--; y--; conflict[x] |= 1<< y; conflict[y] |= 1<< x;} int total = 1<< n; valid[0] = true; for(int mask = 1; mask < total; mask++){ int firstBit = mask & -mask; int v = __builtin_ctz(firstBit); int rest = mask ^ firstBit; valid[mask] = valid[rest] &&((conflict[v] & rest) == 0);} fill(dp, dp + total, inf); dp[0] = 0; for(int mask = 1; mask < total; mask++){ int firstBit = mask & -mask; int other = mask ^ firstBit; for(int extra = other; ; extra =(extra - 1) & other){ int team = extra | firstBit; if(valid[team]){ dp[mask] = min(dp[mask], dp[mask ^ team] + 1);} if(extra == 0){ break;}}} cout << dp[total - 1]<< endl; return 0;}