These are the notes for Competitive Programming episode 39, part eight of the dynamic programming section. Anjali's tiffin kitchen has m ≤ 20 ingredients; every dish uses a set of them and every customer can eat a set of them. An original problem, Tiffin Menu, asks, for every customer, how many dishes use only allowed ingredients: the dishes whose set is a subset of the customer's set. Checking every customer against every dish is O(n · q): TLE. Precomputing an answer for every one of the 2^m sets by listing submasks costs 3^m ≈ 3.5 · 10^9: still too slow. SOS DP treats each bit as a direction of a grid and runs prefix sums one bit at a time: O(m · 2^m) ≈ 2 · 10^7. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
Anjali numbers her ingredients 0 … 19 (rice = 0, dal = 1, paneer = 2, …). Dal rice uses {rice, dal}. A customer who can eat {rice, dal, paneer} can order dal rice, because every ingredient of the dish is allowed. She wants, for each customer, the number of dishes on the menu they can order.
Problem P · Tiffin Menu
(Written for this course, in the style of a Codeforces Div. 2 problem.)
Sets of ingredients are given as bitmasks: bit i of the number is 1 when ingredient i is in the set.
- Input:
m n q(1 ≤ m ≤ 20, 1 ≤ n, q ≤ 5 · 10^5), then n dish masks, then q customer masks (each 0 ≤ mask < 2^m). - Output: for every customer c, the number of dishes d with d ⊆ c.
Sample 1:
3 6 5
1 3 2 5 7 3
3 5 7 4 0
Output: 4 2 6 0 0. (Customer 3 = {rice, dal} can order dishes 1, 3, 2, 3; customer 7 can order all six.)
Subset test: d ⊆ c exactly when (d & c) == d: every bit of d is also a bit of c.
Attempt 1: every customer × every dish (Time Limit Exceeded)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, q;
cin >> m >> n >> q;
vector<int> dish(n), cust(q);
for (int &d : dish) cin >> d;
for (int &c : cust) cin >> c;
ll total = 0;
for (int i = 0; i < q; i++) { // every customer
int cnt = 0;
for (int d : dish) // every dish
if ((d & cust[i]) == d) cnt++; // dish is a subset of the customer
cout << cnt << " \n"[i == q - 1];
}
return 0;
}
Sample 1 prints 4 2 6 0 0. With 5 · 10^5 dishes and customers (built inside main) it gets Time Limit Exceeded: 2.5 · 10^11 checks.
Attempt 2: an answer per mask, by listing submasks
There are only 2^m ≈ 10^6 different sets, so precompute an answer for every set. Let f[s] = number of dishes with exactly set s, and
F[c] = Σ f[s] over all s ⊆ c (the sum over subsets of c)
A submask of c is a mask s with s ⊆ c. The classic loop lists all of them:
for (int s = c; ; s = (s - 1) & c) { // every submask of c, from c down to 0
F[c] += f[s];
if (s == 0) break;
}
Over all c this costs 3^m: each bit is either outside c, in c but not in s, or in both. 3^20 ≈ 3.5 · 10^9: about 3 seconds of CPU on the SyntaxPilot machine. Too slow, and m = 20 is the maximum.
The idea: prefix sums, one bit at a time
Recall 2D prefix sums (episode 8): sum along every row first, then along every column, instead of adding a whole rectangle for each cell. A mask with m bits is a point in an m-dimensional grid of side 2, and s ⊆ c means s ≤ c in every coordinate. So "sum over subsets" is an m-dimensional prefix sum. Do it one dimension (bit) at a time:
for (int b = 0; b < m; b++) // bit b = one direction
for (int mask = 0; mask < (1 << m); mask++)
if (mask & (1 << b))
F[mask] += F[mask ^ (1 << b)]; // the same mask without bit b
After the pass for bit b, F[mask] = sum of f[s] over the s that agree with mask on bits b + 1 … m − 1 and are ⊆ mask on bits 0 … b. After the last pass, F is the full sum over subsets. Each subset is reached in exactly one way (switch off its missing bits in increasing bit order), so nothing is counted twice.
Trace for sample 1 (m = 3, masks 0 … 7):
| mask | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| f (exact) | 0 | 1 | 1 | 2 | 0 | 1 | 0 | 1 |
| after bit 0 | 0 | 1 | 1 | 3 | 0 | 1 | 0 | 1 |
| after bit 1 | 0 | 1 | 1 | 4 | 0 | 1 | 0 | 2 |
| after bit 2 | 0 | 1 | 1 | 4 | 0 | 2 | 1 | 6 |
The SOS DP checklist
- Start: F[s] = number of items with exactly set s.
- Outer loop: bit b = 0 … m − 1.
- Inner loop: every mask with bit b on:
F[mask] += F[mask ^ (1 << b)]. - Query: the answer for c is F[c], O(1).
- The bit loop is outside.
The accepted solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, q;
cin >> m >> n >> q;
vector<int> dish(n), cust(q);
for (int &d : dish) cin >> d;
for (int &c : cust) cin >> c;
vector<int> F(1 << m, 0);
for (int d : dish) F[d]++; // dishes with exactly this set
for (int b = 0; b < m; b++) // one ingredient (bit) at a time
for (int mask = 0; mask < (1 << m); mask++)
if (mask & (1 << b))
F[mask] += F[mask ^ (1 << b)]; // the same set, without bit b
for (int i = 0; i < q; i++) cout << F[cust[i]] << " \n"[i == q - 1];
return 0;
}
| Input | Output |
|---|---|
| sample 1 | 4 2 6 0 0 |
1 1 2 / 0 / 0 1 (one empty dish) |
1 1 |
The 5 · 10^5 × 5 · 10^5 case that timed out:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m = 20, n = 500000, q = 500000; // worst case, built here
mt19937 rng(39);
vector<int> dish(n), cust(q);
for (int &d : dish) d = rng() % (1 << m);
for (int &c : cust) c = rng() % (1 << m);
vector<int> F(1 << m, 0);
for (int d : dish) F[d]++; // dishes with exactly this set
for (int b = 0; b < m; b++) // one ingredient (bit) at a time
for (int mask = 0; mask < (1 << m); mask++)
if (mask & (1 << b))
F[mask] += F[mask ^ (1 << b)]; // the same set, without bit b
ll total = 0;
for (int c : cust) total += F[c];
cout << "total " << total << "\n";
return 0;
}
Output: total 796257889, in a few hundredths of a second.
A stress test
1000 random menus (m ≤ 6, up to 30 dishes); for every mask the SOS value must equal a brute-force count:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 rng(39);
for (int t = 1; t <= 1000; t++) {
int m = rng() % 6 + 1, n = rng() % 30 + 1;
vector<int> dish(n);
for (int &d : dish) d = rng() % (1 << m);
vector<int> F(1 << m, 0);
for (int d : dish) F[d]++;
for (int b = 0; b < m; b++)
for (int mask = 0; mask < (1 << m); mask++)
if (mask & (1 << b)) F[mask] += F[mask ^ (1 << b)];
for (int c = 0; c < (1 << m); c++) { // brute: check every dish
int cnt = 0;
for (int d : dish) if ((d & c) == d) cnt++;
if (cnt != F[c]) { cout << "mismatch on test " << t; return 0; }
}
}
cout << "all 1000 tests passed";
}
Output: all 1000 tests passed.
Supersets too: must-have ingredients
If each customer names ingredients they must have, count the dishes d with c ⊆ d: a sum over supersets. Same loops, the other direction:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, q;
cin >> m >> n >> q;
vector<int> dish(n), cust(q);
for (int &d : dish) cin >> d;
for (int &c : cust) cin >> c;
// G[mask] = dishes that contain EVERY ingredient in mask
vector<int> G(1 << m, 0);
for (int d : dish) G[d]++;
for (int b = 0; b < m; b++)
for (int mask = 0; mask < (1 << m); mask++)
if (!(mask & (1 << b)))
G[mask] += G[mask | (1 << b)]; // the same set, plus bit b
for (int i = 0; i < q; i++) cout << G[cust[i]] << " \n"[i == q - 1];
return 0;
}
Sample 1 read as must-haves prints 3 2 1 2 6 (must have rice and dal: dishes 3, 7, 3; no demands: all six).
Complexity vs the constraints
| Approach | Time | Verdict |
|---|---|---|
| every customer × every dish | O(n · q) = 2.5 · 10^11 | TLE |
| every submask of every mask | O(3^m) ≈ 3.5 · 10^9 | ~3 s, too slow |
| SOS DP | O(m · 2^m + n + q) ≈ 2 · 10^7 | accepted |
Memory: one int array of 2^20 entries = 4 MB.
Common mistakes (and the real outputs)
Bug 1: loops swapped (mask outside, bit inside)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, q;
cin >> m >> n >> q;
vector<int> dish(n), cust(q);
for (int &d : dish) cin >> d;
for (int &c : cust) cin >> c;
vector<int> F(1 << m, 0);
for (int d : dish) F[d]++; // dishes with exactly this set
for (int mask = 0; mask < (1 << m); mask++)
for (int b = 0; b < m; b++) // bit inside?
if (mask & (1 << b))
F[mask] += F[mask ^ (1 << b)]; // the same set, without bit b
for (int i = 0; i < q; i++) cout << F[cust[i]] << " \n"[i == q - 1];
return 0;
}
Sample 1 prints 4 2 8 0 0: 8 dishes for customer 7, but the menu has only 6. With the bit loop inside, F[mask ^ bit] is already a complete sum when it is added, so a submask is reached along several paths and counted several times.
Bug 2: a huge array on the stack
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m = 20, n = 500000, q = 500000; // worst case, built here
mt19937 rng(39);
vector<int> dish(n), cust(q);
for (int &d : dish) d = rng() % (1 << m);
for (int &c : cust) c = rng() % (1 << m);
ll F[1 << 20] = {}; // 2^20 long longs = 8 MB, on the stack
for (int d : dish) F[d]++;
for (int b = 0; b < m; b++)
for (int mask = 0; mask < (1 << m); mask++)
if (mask & (1 << b)) F[mask] += F[mask ^ (1 << b)];
ll total = 0;
for (int c : cust) total += F[c];
cout << "total " << total << "\n";
return 0;
}
Runtime Error (SIGSEGV): 2^20 long longs are 8 MB, more than the usual 8 MB stack can hold together with everything else. Use a vector, or declare the array globally (static storage).
Summary table
| Mistake | What you see | Why | Fix |
|---|---|---|---|
for mask { for b { … } } |
4 2 8 0 0 (only 6 dishes) |
a submask is counted many times | for b { for mask { … } } |
ll F[1 << 20]; inside main |
Runtime Error (SIGSEGV) |
8 MB on the stack | vector or a global array |
| every submask of every mask | 3^20 ≈ 3.5 · 10^9 steps | too slow for m = 20 | SOS: O(m · 2^m) |
d & c == d |
wrong subset test | == binds tighter than & |
(d & c) == d |
F[mask] += F[mask ^ (1 << b)] without the bit check |
sums over unrelated masks | adds a superset | only when bit b is on |
Mini project
Write a small "bitmask toolkit" with four functions on a vector of size 2^m: subsetSum (SOS), subsetUndo (the inverse: subtract in the same loops), supersetSum and supersetUndo. Test that undo(sum(f)) = f on random arrays, and use them to count, for every mask c, the dishes whose set is exactly c after a menu change.
Practice
-
Count pairs i < j with a_i & a_j = 0 (a_i < 2^20).
Answer
a_j & a_i = 0 means a_j ⊆ complement(a_i). With F = SOS of the counts, total = Σ F[~a_i & (2^m − 1)], minus 1 for each a_i = 0 (pairing with itself), then divide by 2. For [1, 2, 3, 0]: <b>4</b> pairs (1&2, 0&1, 0&2, 0&3). -
For each a_i, the largest a_j that is a submask of a_i.
Answer
The same loops with max instead of +: start G[mask] = mask if it occurs in the array, else −1; G[mask] = max(G[mask], G[mask ^ (1 << b)]). -
Undo SOS: recover f from F.
Answer
Run the same loops with −= instead of += (inclusion–exclusion, the Möbius transform). From the trace: F = [0,1,1,4,0,2,1,6] gives back f = [0,1,1,2,0,1,0,1]. -
Count subsets of the array whose AND is 0 (mod 10^9 + 7).
Answer
Let G[mask] = number of elements that are supersets of mask (superset SOS). Subsets whose AND contains mask: 2^G[mask] − 1 (non-empty). Inclusion–exclusion over masks: answer = Σ (−1)^popcount(mask) · (2^G[mask] − 1), i.e. a superset "undo" evaluated at mask 0.
Quick quiz
How many submasks does the mask 1011 (binary) have?
A) 3 · B) 4 · C) 8 · D) 11
Answer
C. 1011 has three bits on; each is in or out of s: 2^3 = 8 submasks, including 0 and 1011 itself.
Interview questions
- What does SOS DP compute? For every mask, the sum of f over all its submasks (or, flipped, supersets) in O(m · 2^m).
- Why is the bit loop outside? It is an m-dimensional prefix sum done one dimension at a time; swapping the loops reuses already-complete sums and over-counts.
- How do you enumerate submasks of a mask, and what does it cost?
for (s = c; ; s = (s − 1) & c)until s = 0; over all masks 3^m. - How do you invert SOS? The same loops with subtraction (Möbius transform).
- Where does SOS appear? Counting pairs with AND = 0, OR-convolutions, "how many items are compatible with this set" queries.
- What is the memory for m = 20? 2^20 values: 4 MB as
int, 8 MB aslong long(keep it off the stack).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Bitmask | An integer whose bits encode a subset | 5 = 101 = {0, 2} |
| Subset / submask | s ⊆ c: every bit of s is in c | 001 ⊆ 011 |
| Superset | c ⊇ s: c contains every bit of s | 111 ⊇ 011 |
| Subset test | (d & c) == d |
(1 & 3) == 1 |
| Submask enumeration | s = (s − 1) & c lists all submasks of c |
3 → 3, 2, 1, 0 |
| Sum over subsets (SOS) | F[c] = Σ f[s] over s ⊆ c | F[011] = 4 |
| SOS DP | Prefix sums one bit at a time, O(m · 2^m) | this episode |
| Zeta / Möbius transform | Other names for the SOS sum and its inverse | undo with -= |
mask ^ (1 << b) |
Flip bit b (switch it off when it is on) | 011 ^ 010 = 001 |
| Stack overflow | A too-large local array or too-deep recursion | ll F[1 << 20] |
Summary
- Every pair is O(n · q); listing submasks of every mask is 3^m: both too slow for m = 20.
- Count items per exact mask, then, for each bit b, for each mask with bit b:
F[mask] += F[mask ^ (1 << b)]. - The bit loop is outside; supersets use
mask | (1 << b)when bit b is off. - O(m · 2^m): about 2 · 10^7 for m = 20. Keep the 2^m array off the stack.
- Real bugs: swapped loops (
4 2 8 0 0), an 8 MB local array (SIGSEGV).
Solutions in C++, Java and Python
Problem P · Tiffin Menu
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, q;
cin >> m >> n >> q;
vector<int> dish(n), cust(q);
for (int &d : dish) cin >> d;
for (int &c : cust) cin >> c;
vector<int> F(1 << m, 0);
for (int d : dish) F[d]++; // dishes with exactly this set
for (int b = 0; b < m; b++) // one ingredient (bit) at a time
for (int mask = 0; mask < (1 << m); mask++)
if (mask & (1 << b))
F[mask] += F[mask ^ (1 << b)]; // the same set, without bit b
for (int i = 0; i < q; i++) cout << F[cust[i]] << " \n"[i == q - 1];
return 0;
}
Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
int m = nextInt(in), n = nextInt(in), q = nextInt(in);
int[] F = new int[1 << m];
for (int i = 0; i < n; i++) F[nextInt(in)]++; // dishes with exactly this set
for (int b = 0; b < m; b++) // one bit at a time
for (int mask = 0; mask < (1 << m); mask++)
if ((mask & (1 << b)) != 0) F[mask] += F[mask ^ (1 << b)];
StringBuilder sb = new StringBuilder();
for (int i = 0; i < q; i++) sb.append(F[nextInt(in)]).append(i == q - 1 ? "\n" : " ");
System.out.print(sb);
}
static int nextInt(DataInputStream in) throws IOException {
int r = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { r = r * 10 + (b - '0'); b = in.read(); }
return r;
}
}
Python (correct, but m · 2^m = 2 · 10^7 Python steps take several seconds; use C++ for m = 20)
import sys
def main():
data = sys.stdin.buffer.read().split()
m, n, q = int(data[0]), int(data[1]), int(data[2])
F = [0] * (1 << m)
for x in data[3:3 + n]:
F[int(x)] += 1 # dishes with exactly this set
for b in range(m): # one bit at a time
bit = 1 << b
for mask in range(1 << m):
if mask & bit:
F[mask] += F[mask ^ bit]
print(" ".join(str(F[int(c)]) for c in data[3 + n:3 + n + q]))
main()
All three print 4 2 6 0 0 for sample 1.
Next episode: DP 9: probability and expected-value DP (expected dice rolls and the self-loop trap).