SyntaxPilot
Courses/Competitive Programming/Lesson 39

Competitive Programming · Lesson 39 of 90 · 10 min

DP 8: SOS DP (sum over subsets)

queued

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

  1. Start: F[s] = number of items with exactly set s.
  2. Outer loop: bit b = 0 … m − 1.
  3. Inner loop: every mask with bit b on: F[mask] += F[mask ^ (1 << b)].
  4. Query: the answer for c is F[c], O(1).
  5. 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

  1. 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).

  2. 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)]).

  3. 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].

  4. 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

  1. What does SOS DP compute? For every mask, the sum of f over all its submasks (or, flipped, supersets) in O(m · 2^m).
  2. 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.
  3. 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.
  4. How do you invert SOS? The same loops with subtraction (Möbius transform).
  5. Where does SOS appear? Counting pairs with AND = 0, OR-convolutions, "how many items are compatible with this set" queries.
  6. What is the memory for m = 20? 2^20 values: 4 MB as int, 8 MB as long 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).