Bitset Tricks—Contest Cheat Sheet

Quick Revisit

• USE WHEN: $O(n^2)$ TLE and problem involves boolean vectors, subset membership, or reachability
• KEY INSIGHT: std::bitset gives automatic /64 speedup on boolean operations
• INVARIANT: dp |= (dp << x) adds item $x$ to all reachable sums in $O(S/64)$
• CLASSIC BUG: bitset size must be a compile-time constant—use template or #define
• PREREQUISITE: Bitset Optimization for theory; this file is recipes only

Companion to Bitset Optimization—that file covers internals and theory; this one is copy-paste recipes.

CF Rating Range: 1700–2200

---

API Quick Reference

#include <bitset>
bitset<N> b;            // N must be compile-time constant
b.set(i);  b.reset(i);  b.flip(i);   // single-bit ops, O(1)
b[i]                    // access bit i (as reference)
b.count()               // popcount, O(N/64)
b.any() / b.none()      // O(N/64)
b <<= k; b >>= k;       // shift all bits, O(N/64)
b & c; b | c; b ^ c;    // bulk bitwise ops, O(N/64)
b._Find_first()          // first set bit (GCC only)
b._Find_next(i)          // next set bit after i (GCC only)

---

Trick 1—Subset Sum Existence

Spot it: "Is sum $T$ achievable?" with $S$ up to ~500k. Complexity: $O(n\cdot S/64)$ time, $O(S/64)$ space.

bitset<MAXS> dp;
dp[0] = 1;
for (int x : items)
    dp |= (dp << x);
// answer: dp[T]

$n=500,S=500\text{k}$: from $2.5\times {10}^8$ → $\sim 4\times {10}^6$.

---

Trick 2—Transitive Closure

Spot it: "Pairwise reachability" in dense digraph, $n\le 2000$–$5000$. Complexity: $O(n^3/64)$ time, $O(n^2/64)$ space.

bitset<MAXN> reach[MAXN];
// init: reach[u].set(v) for each edge u→v, reach[u].set(u)
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        if (reach[i][k])
            reach[i] |= reach[k];

$n=2000$: from $8\times {10}^9$ → $\sim 1.25\times {10}^8$.

---

Trick 3—Knapsack Reachability

Spot it: 0/1 knapsack asks only "which weights are achievable?" (no values), weight bound up to ~${10}^6$. Complexity: $O(n\cdot W/64)$ time. Loses per-state value tracking.

bitset<MAXW> dp;
dp[0] = 1;
for (auto& item : items)
    dp |= (dp << item.weight);
// dp[w] == 1 iff weight w is reachable

Same shift as Trick 1, framed as knapsack. Combine with a separate pass if you also need optimal values.

---

Trick 4—String Matching (Bitap / Shift-OR)

Spot it: Pattern matching with wildcards, Hamming distance ≤ $k$, or short patterns ($|P|\le$ a few thousand). Complexity: $O(|T|\cdot |P|/64)$ exact; $O(|T|\cdot k\cdot |P|/64)$ with $k$ errors.

// Exact matching (Bitap algorithm)
int m = pattern.size();
bitset<MAXM> mask[256];
for (int i = 0; i < m; i++) mask[(int)pattern[i]].set(i);

bitset<MAXM> state;
for (char c : text) {
    state <<= 1;
    state.set(0);
    state &= mask[(int)c];
    if (state[m - 1]) { /* match at current position */ }
}

For $k$-error matching, maintain $k+1$ state bitsets—one per error count.

---

Trick 5—Subset / Column DP Speedup

Spot it: Bitmask DP inner loop needs intersection, union, or popcount across items—batch it. Complexity: Inner loop drops from $O(n)$ to $O(n/64)$.

bitset<N> predicate;  // bit i set if item i satisfies condition
for (int mask = 0; mask < (1 << n); mask++) {
    bitset<N> sub(mask);
    int count = (sub & predicate).count();  // O(N/64)
}

Useful for column-based DP on groups of items when $n$ is moderate.

---

Speedup At-a-Glance

Pattern	Without	With bitset	×Speedup
Subset-sum feasibility	$O(nS)$	$O(nS/64)$	~50×
Transitive closure	$O(n^3)$	$O(n^3/64)$	~50×
Boolean matrix multiply	$O(n^3)$	$O(n^3/64)$	~50×
Gaussian elim over GF(2)	$O(n^{2}m)$	$O(n^{2}m/64)$	~50×
Popcount of $n$-bit set	$O(n)$	$O(n/64)$	~50×

---

When NOT to Use Bitset

• Sparse sets. If only $O(\sqrt{n})$ bits are set out of millions, std::set or unordered_set beats scanning the full bitset.
• Dynamic / runtime size needed. bitset<N> requires compile-time $N$. If $N$ varies, you need vector<uint64_t> with manual ops.
• Non-boolean state. Bitset encodes 0/1 only. If you need max-value, counts, or multi-bit state per cell, bitset cannot replace the DP array.

---

Gotchas (quick list)

• bitset<n> with variable n won't compile—plan for the max.
• Single-bit access is $O(1)$, same as plain array—/64 only helps bulk ops.
• b <<= k is $O(N/64)$, not $O(1)$.
• _Find_first / _Find_next are GCC-only extensions.
• Large bitsets ($>{10}^6$) may thrash cache, reducing real speedup.
• vector<bool> is packed but lacks bulk bitwise ops—don't confuse with bitset.
• Memory: bitset<500000> = 62.5 KB per instance.

---

Practice Problems

#	Problem	Diff	Trick
1	CF 1037E—Trips	1900	Reachability (#2)
2	CF 1060E—Sergey and Subway	2100	Pairwise distance
3	CF 1602E—Envy	2400	Subset-sum (#1)
4	AtCoder ABC 326 F	—	Knapsack (#3)
5	CSES—Reachability Queries	—	Transitive closure (#2)

---

Cross-References

• Bitset Optimization—full theory and memory layout
• Bit Manipulation—prerequisite operations
• DP—Knapsack
• DP—Bitmask