These are the notes for Competitive Programming episode 86. Sometimes your idea is right but a few times too slow, and there is no better algorithm in sight. A bitset keeps a long row of true/false values packed into 64-bit machine words, so one AND, OR or shift changes 64 values in one instruction. The idea stays the same; the work is divided by 64. Two Trucks (subset sum) goes from a bool-array DP that takes seconds to the one-liner can |= can << x that finishes in a fraction of a second. Friend Triangles goes from a triple loop that takes seconds to (adj[i] & adj[j]).count(), well under a second. Both are stress-tested against brute force. 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. Where a program is slow, the notes say "seconds" rather than a number: the exact time depends on the machine, but the gap (seconds against a fraction of a second) is always there.
The real-life hook
A hall has 64 lights, each with its own switch. To turn them all on you walk to every switch: 64 moves. That is a bool array: one value per step. Now wire all 64 lights to one master lever: one move, 64 lights. A CPU works on 64-bit words in exactly this way: one AND, one OR, one shift, and 64 bits change at once. A bitset is a long row of such levers: an operation on n bits takes about n / 64 steps.
The second picture is a teacher with an answer-key stencil. Checking an answer sheet answer by answer is slow. A punched stencil laid over the sheet shows every match at once (that is AND), and counting the marks showing through the holes is count().
A CPU word holds 64 bits
- A
bool(orchar) array spends a whole byte on each true/false value, and a loop over it touches the values one at a time. - A 64-bit integer (
unsigned long long) holds 64 true/false values, one per bit. The CPU can AND, OR, XOR or shift all 64 in one instruction, and count the bits that are on with onepopcountinstruction. std::bitset<N>is an array of ⌈N / 64⌉ such words with the operators already written for you. Every whole-bitset operation is a loop over words, not over bits: about N / 64 steps.- That is why bitset solutions are written as O(n³ / 64) or O(n · S / w), where w = 64 is the word size. Big-O ignores constant factors, but in a contest a factor of 64 is the difference between Time Limit Exceeded and Accepted.
bitset basics
| Operation | Meaning | Cost |
|---|---|---|
bitset<N> b; |
N bits, all 0; N must be a compile-time constant | |
bitset<8> b("00101101"); |
from a string, written from bit 7 down to bit 0 | |
b[i], b[i] = 1, b.test(i), b.set(i), b.reset(i), b.flip(i) |
read / change one bit | O(1) |
a & b, a | b, a ^ b, ~a |
AND, OR, XOR, NOT of whole bitsets | O(N / 64) |
a << k, a >> k |
every bit moves k places up / down; bits pushed past the end are lost | O(N / 64) |
a.count() |
how many bits are on | O(N / 64) |
a.any(), a.none(), a.all() |
is any / no / every bit on? | O(N / 64) |
a.reset(), a.set() |
all bits 0 / all bits 1 | O(N / 64) |
a._Find_first(), a._Find_next(i) |
first on bit, next on bit after i (g++ only) | O(N / 64) |
cout << a |
prints bit N−1 first, bit 0 last | O(N) |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
bitset<8> a("00101101"); // written from bit 7 down to bit 0
bitset<8> b("00001111");
cout << "a = " << a << "\n";
cout << "a & b = " << (a & b) << "\n"; // AND: on in both
cout << "a | b = " << (a | b) << "\n"; // OR: on in either
cout << "a << 2 = " << (a << 2) << "\n"; // every bit moves 2 places up
cout << "bits on in a: " << a.count() << "\n";
cout << "bit 3 of a: " << a[3] << "\n";
}
Output:
a = 00101101
a & b = 00001101
a | b = 00101111
a << 2 = 10110100
bits on in a: 4
bit 3 of a: 1
a & b keeps the bits on in both (00001101), a | b the bits on in either (00101111). Shifting left by 2 moves every bit two places up: 00101101 becomes 10110100, and the two top bits fall off the end. Four bits are on in a, and bit 3 (counting from the right, starting at 0) is 1.
Problem B1 · Two Trucks
Written for this course.
A warehouse has n ≤ 3000 boxes; box i weighs w[i] kg, 1 ≤ w[i] ≤ 1000. Every box goes on truck 1 or truck 2. Print the smallest possible difference between the two loads.
Input: n, then n weights. Output: one integer.
| Input | Output | Why |
|---|---|---|
5 / 3 1 4 2 2 |
0 |
{3, 2, 1} and {4, 2}: 6 vs 6 |
1 / 7 |
7 |
one box: 7 vs 0 |
2 / 1000 1 |
999 |
1000 vs 1 is the best split |
Key observation: if truck 1 carries s kg, truck 2 carries S − s, where S is the total, and the difference is |S − 2s|. So we only need to know which loads s are possible at all: that is subset sum. Then we try every possible s.
Brute force: every split
Each box goes on truck 1 or not: 2^n splits. For n = 3000 that is hopeless, but for n ≤ 12 it is a perfect referee for stress tests (see the stress test below).
Subset sum with a bool array (correct, too slow)
can[s] is true if some boxes weigh exactly s; can[0] is true (an empty truck). For a box of weight x, every load s that was possible before becomes possible plus x: can[s] |= can[s − x]. We go downwards (s from S to x) so that this box is not added twice in the same round.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> w(n);
for (int& x : w) cin >> x;
int S = accumulate(w.begin(), w.end(), 0);
vector<char> can(S + 1, 0); // can[s]: some boxes weigh exactly s
can[0] = 1;
for (int x : w)
for (int s = S; s >= x; s--) // one box, used once
if (can[s - x]) can[s] = 1;
int best = INT_MAX;
for (int s = 0; s <= S; s++)
if (can[s]) best = min(best, abs(S - 2 * s)); // truck 1 gets s, truck 2 gets S - s
cout << best << "\n";
}
| Input | Output |
|---|---|
5 / 3 1 4 2 2 |
0 |
1 / 7 |
7 |
The largest test, 3000 random boxes made inside the program:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 gen(86);
int n = 3000; // the largest test
vector<int> w(n);
for (int& x : w) x = gen() % 1000 + 1;
int S = accumulate(w.begin(), w.end(), 0);
vector<char> can(S + 1, 0); // can[s]: some boxes weigh exactly s
can[0] = 1;
for (int x : w)
for (int s = S; s >= x; s--) // one box, used once
if (can[s - x]) can[s] = 1;
int best = INT_MAX;
for (int s = 0; s <= S; s++)
if (can[s]) best = min(best, abs(S - 2 * s)); // truck 1 gets s, truck 2 gets S - s
cout << best << "\n";
}
Output:
1
The answer is 1 (the total is odd), but the run took seconds: over a 2-second limit, Time Limit Exceeded. The work is n · S ≈ 3000 · 1.5 · 10^6 ≈ 4.5 · 10^9 steps.
The bitset version: can |= can << x
Look at the possible loads as a row of bits. With boxes of 1 and 4 kg, loads 0, 1, 4 and 5 are possible. Now a box of 3 kg: every possible load, plus 3. That is not a loop at all: it is the whole row shifted left by 3. The new possible loads are the old ones or the shifted ones:
| load s | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| can (before) | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| can << 3 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| can | (can << 3) | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
So the whole inner loop becomes can |= can << x, done 64 loads at a time. Why no "downwards" care is needed: can << x is computed from the old can before the OR, so each box is used at most once automatically.
The size of a bitset must be known when the program compiles, so we size it for the largest possible total, 3000 · 1000:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> w(n);
for (int& x : w) cin >> x;
const int MAXS = 3000 * 1000; // the largest possible total
bitset<MAXS + 1> can; // bit s on: total s is possible
can[0] = 1;
for (int x : w) can |= can << x; // every old total, plus x
int S = accumulate(w.begin(), w.end(), 0);
int best = INT_MAX;
for (int s = 0; s <= S; s++)
if (can[s]) best = min(best, abs(S - 2 * s)); // truck 1 gets s, truck 2 gets S - s
cout << best << "\n";
}
| Input | Output |
|---|---|
5 / 3 1 4 2 2 |
0 |
2 / 1000 1 |
999 |
The same largest test:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 gen(86);
int n = 3000; // the largest test
vector<int> w(n);
for (int& x : w) x = gen() % 1000 + 1;
const int MAXS = 3000 * 1000; // the largest possible total
bitset<MAXS + 1> can; // bit s on: total s is possible
can[0] = 1;
for (int x : w) can |= can << x; // every old total, plus x
int S = accumulate(w.begin(), w.end(), 0);
int best = INT_MAX;
for (int s = 0; s <= S; s++)
if (can[s]) best = min(best, abs(S - 2 * s)); // truck 1 gets s, truck 2 gets S - s
cout << best << "\n";
}
Output:
1
The same answer, in a fraction of a second. Same idea, same boxes, 64 loads per step.
Stress test against all 2^n splits
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int brute(vector<int>& w) { // try all 2^n splits
int n = w.size(), S = accumulate(w.begin(), w.end(), 0), best = INT_MAX;
for (int m = 0; m < (1 << n); m++) {
int s = 0;
for (int i = 0; i < n; i++) if (m >> i & 1) s += w[i];
best = min(best, abs(S - 2 * s));
}
return best;
}
int fast(vector<int>& w) {
bitset<20001> can;
can[0] = 1;
for (int x : w) can |= can << x;
int S = accumulate(w.begin(), w.end(), 0), best = INT_MAX;
for (int s = 0; s <= S; s++) if (can[s]) best = min(best, abs(S - 2 * s));
return best;
}
int main() {
mt19937 gen(86);
for (int it = 1; it <= 1000; it++) {
int n = gen() % 12 + 1;
vector<int> w(n);
for (int& x : w) x = gen() % 1000 + 1;
if (brute(w) != fast(w)) { cout << "differs on test " << it; return 0; }
}
cout << "all 1000 tests agree";
}
Output:
all 1000 tests agree
The constant-size trap
Why not size the bitset from the input?
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
bitset<n> seen; // size from the input?
cout << seen.size() << "\n";
}
Compiler output (real):
main.cpp: In function 'int main()':
main.cpp:8:13: error: the value of 'n' is not usable in a constant expression
8 | bitset<n> seen; // size from the input?
| ^
main.cpp:6:9: note: 'int n' is not const
6 | int n;
| ^
main.cpp:8:13: note: in template argument for type 'long unsigned int'
8 | bitset<n> seen; // size from the input?
| ^
main.cpp:9:18: error: request for member 'size' in 'seen', which is of non-class type 'int'
The size of a bitset is part of its type (a template argument), so it is fixed when the program compiles. Use the largest size the constraints allow (const int MAXS = 3000 * 1000;), or the doubling trick from the Mini project.
The opposite mistake compiles fine and is worse: a bitset too small for the totals. Shifting left drops the high bits, and those loads silently disappear:
#include <bits/stdc++.h>
using namespace std;
int main() {
bitset<8> can; // too small: totals up to 9 are possible
can[0] = 1;
for (int x : {5, 4}) can |= can << x;
cout << can << " (total 9 is " << (can.count() == 4 ? "kept" : "lost") << ")\n";
bitset<10> ok;
ok[0] = 1;
for (int x : {5, 4}) ok |= ok << x;
cout << ok << "\n";
}
Output:
00110001 (total 9 is lost)
1000110001
With boxes 5 and 4 the possible totals are 0, 4, 5, 9. In bitset<8> bit 9 does not exist, so total 9 vanished; bitset<10> keeps it.
Problem B2 · Friend Triangles
Written for this course.
A social network has n ≤ 3000 users. Row i is a string of n characters: g[i][j] == '1' if users i and j are friends (the matrix is symmetric, the diagonal is 0). Count the friend triangles: triples i < j < k who are all friends with each other.
5
01110
10110
11011
11100
00100
Users 0, 1, 2, 3 are all friends with each other, which gives the triangles {0,1,2}, {0,1,3}, {0,2,3}, {1,2,3}: the answer is 4. User 4 has only one friend (user 2), so is in no triangle.
The triple loop (correct, too slow)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> g(n); // g[i][j] == '1': i and j are friends
for (auto& row : g) cin >> row;
ll triangles = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (g[i][j] == '1')
for (int k = j + 1; k < n; k++) // a third friend of both?
if (g[i][k] == '1' && g[j][k] == '1') triangles++;
cout << triangles << "\n";
}
Output on the sample: 4.
The largest test, 3000 users, each pair friends with probability one half:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 gen(86);
int n = 3000; // the largest test
vector<string> g(n, string(n, '0'));
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (gen() % 2) g[i][j] = g[j][i] = '1'; // each pair: friends half the time
ll triangles = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (g[i][j] == '1')
for (int k = j + 1; k < n; k++) // a third friend of both?
if (g[i][k] == '1' && g[j][k] == '1') triangles++;
cout << triangles << "\n";
}
Output:
563063866
Correct, but it took seconds: Time Limit Exceeded. About n³ / 6 = 4.5 · 10^9 checks.
Key observation: count common friends
For a pair of friends i and j, every third member of a triangle is a friend of both: a common friend. As bitsets, the common friends of i and j are adj[i] & adj[j] (the stencil), and their number is .count(). Summing over every pair of friends counts each triangle once from each of its 3 edges, so we divide by 3.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> g(n); // g[i][j] == '1': i and j are friends
for (auto& row : g) cin >> row;
vector<bitset<3000>> adj(n); // row i: the friends of i, as bits
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (g[i][j] == '1') adj[i][j] = 1;
ll triangles = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (adj[i][j])
triangles += (adj[i] & adj[j]).count(); // common friends
cout << triangles / 3 << "\n"; // each triangle has 3 edges
}
| Input | Output |
|---|---|
| the 5-user sample | 4 |
1 / 0 (one user, no friends) |
0 |
The largest test:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 gen(86);
int n = 3000; // the largest test
vector<string> g(n, string(n, '0'));
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (gen() % 2) g[i][j] = g[j][i] = '1'; // each pair: friends half the time
vector<bitset<3000>> adj(n); // row i: the friends of i, as bits
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (g[i][j] == '1') adj[i][j] = 1;
ll triangles = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (adj[i][j])
triangles += (adj[i] & adj[j]).count(); // common friends
cout << triangles / 3 << "\n"; // each triangle has 3 edges
}
Output:
563063866
The same 563063866 triangles the triple loop found, well under a second.
Stress test against the triple loop
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
mt19937 gen(86);
for (int it = 1; it <= 500; it++) {
int n = gen() % 9 + 1;
vector<bitset<3000>> adj(n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (gen() % 2) adj[i][j] = adj[j][i] = 1;
ll slow = 0, fast = 0;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) for (int k = j + 1; k < n; k++)
slow += adj[i][j] && adj[i][k] && adj[j][k];
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++)
if (adj[i][j]) fast += (adj[i] & adj[j]).count();
if (slow != fast / 3) { cout << "differs on test " << it; return 0; }
}
cout << "all 500 tests agree";
}
Output:
all 500 tests agree
Complexity vs the constraints
n = 3000, limit 2 s. A machine does very roughly 10^8 to 10^9 simple steps a second.
| Method | Work | Verdict |
|---|---|---|
| Trucks: all 2^n splits | 2^3000 | referee only (n ≤ 12) |
| Trucks: bool array | n · S ≈ 4.5 · 10^9 | Time Limit Exceeded (seconds) |
Trucks: bitset can |= can << x |
n · MAXS / 64 ≈ 3000 · 3·10^6 / 64 ≈ 1.4 · 10^8 word steps | Accepted (a fraction of a second) |
| Triangles: triple loop | n³ / 6 ≈ 4.5 · 10^9 | Time Limit Exceeded (seconds) |
| Triangles: AND + count | (n² / 2 pairs) · (n / 64 words) ≈ 2 · 10^8 word steps | Accepted (well under a second) |
Memory: bitset<3000001> is 3000001 / 8 ≈ 375 KB; vector<bitset<3000>>(3000) is 3000 · 3000 / 8 ≈ 1.1 MB. A bitset row of n bits costs n / 8 bytes, 8 times less than a char array.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
bitset<n> b; with n from input |
error: the value of 'n' is not usable in a constant expression |
the size is part of the type | bitset<MAXN> for the largest n, or the doubling template |
| bitset too small for the totals | 00110001 (total 9 is lost) |
<< drops bits past the end |
size for the largest possible total |
vector<bool> for speed |
error: no match for 'operator<<' (operand types are 'std::vector<bool>' and 'int') |
packed bits, but no shift / AND / count on whole rows | std::bitset |
1 << i with i ≥ 31 |
1 << 40 printed 0 here, 1LL << 40 printed 1099511627776 |
1 is an int: undefined behaviour |
1LL << i, or a bitset |
forgetting / 3 in triangles |
3 times the answer | each triangle is seen from its 3 edges | divide by 3 |
| a huge bitset as a local array of many rows | crash (stack overflow) | locals live on a small stack | vector<bitset<N>> or a global |
count() inside the innermost loop over k |
no speed-up | you went back to one bit per step | AND whole rows, count once |
Mini project: a bitset whose size is chosen at run time
The size of a bitset must be a constant, but you can still pick it from the input: write the solution as a template on the size, and if the input needs more bits, call the same function with twice the size. The compiler builds one copy for each size from 64 up to the maximum you allow, and the input picks one at run time. Small inputs then use a small, fast bitset.
#include <bits/stdc++.h>
using namespace std;
// A bitset whose size is picked at run time: try LEN, and if the input needs more, call the
// same function with 2 * LEN. The compiler builds a copy for each size up to MAXLEN.
const int MAXLEN = 1 << 23; // 8388608 bits = 1 MB
template <int LEN>
int min_split(const vector<int>& w, int S) {
if (LEN <= S) { // too small for this input: double it
if constexpr (LEN * 2 <= MAXLEN) return min_split<LEN * 2>(w, S);
else return -1; // larger than we allowed
}
bitset<LEN> can;
can[0] = 1;
for (int x : w) can |= can << x;
int best = INT_MAX;
for (int s = 0; s <= S; s++) if (can[s]) best = min(best, abs(S - 2 * s));
cerr << "used bitset<" << LEN << ">\n";
return best;
}
int main() {
int n;
cin >> n;
vector<int> w(n);
for (int& x : w) cin >> x;
int S = accumulate(w.begin(), w.end(), 0);
cout << min_split<64>(w, S) << "\n";
}
Output (the line used bitset<...> goes to stderr):
$ printf "5\n3 1 4 2 2\n" | ./mini
used bitset<64>
0
$ printf "3\n100000 99999 2\n" | ./mini
used bitset<262144>
1
The first test has total 12, so bitset<64> is enough. The second has total 200001, so the size doubled up to 262144. Extend it: make the template take a lambda, so the same doubling works for any bitset solution.
Practice
These are the homework problems from the episode. All outputs are real.
1. Each box at most twice. Boxes of weights w[i] (n ≤ 3000, w ≤ 1000); each box may be used 0, 1 or 2 times. Can you make a total of exactly K kg?
Solution
"At most twice" is the same as having two copies of each box, each used at most once. So shift twice per box. The bitset must hold 2 · 3000 · 1000 bits; it is static so that its 750 KB do not sit on the stack. The stress test tries all 3^n choices.
#include <bits/stdc++.h>
using namespace std;
const int MAXK = 2 * 3000 * 1000; // every box twice, 3000 boxes of 1000 kg
bool fast(vector<int>& w, int K) {
static bitset<MAXK + 1> can;
can.reset();
can[0] = 1;
for (int x : w) {
can |= can << x; // first copy of the box
can |= can << x; // second copy
}
return K <= MAXK && can[K];
}
bool brute(vector<int>& w, int K, int i = 0, int s = 0) { // 0, 1 or 2 copies of each box
if (i == (int)w.size()) return s == K;
for (int c = 0; c <= 2; c++) if (brute(w, K, i + 1, s + c * w[i])) return true;
return false;
}
int main() {
vector<int> w = {3, 5};
for (int K : {6, 7, 11, 16, 17}) cout << K << ": " << (fast(w, K) ? "YES" : "NO") << "\n";
mt19937 gen(86);
for (int it = 1; it <= 300; it++) {
int n = gen() % 7 + 1;
vector<int> v(n);
for (int& x : v) x = gen() % 20 + 1;
int K = gen() % 120;
if (fast(v, K) != brute(v, K)) { cout << "differs on test " << it << "\n"; return 0; }
}
cout << "all 300 tests agree\n";
}
Output:
6: YES
7: NO
11: YES
16: YES
17: NO
all 300 tests agree
With boxes 3 and 5: 6 = 3 + 3, 11 = 3 + 3 + 5, 16 = 3 + 3 + 5 + 5; 7 and 17 cannot be made. Work: 2 · n · MAXK / 64 word steps.
2. Reachability counts. A directed graph with no cycles (a DAG), n ≤ 5 · 10^4 nodes. For each node, how many nodes can it reach (itself included)?
Solution
In reverse topological order (children before parents), reach[v] = {v} OR reach of every child. Summing sets with a hash set would double-count nodes reachable along two paths; a bitset OR does not. One bitset<n> per node would need n² / 8 bytes = 312 MB for n = 5 · 10^4, so we handle the targets in blocks of B = 4096: for targets lo .. lo + B − 1 we only keep B bits per node (n · B / 8 ≈ 25 MB), run the DP, add the counts, and move to the next block. Total work: (n / B) blocks · (n + m) · (B / 64) word operations = (n + m) · n / 64.
#include <bits/stdc++.h>
using namespace std;
// reach[v] = how many nodes v can reach (itself included) in a DAG, n up to 5*10^4.
// One bitset<n> per node would need n*n/8 bytes = 312 MB, so we do the targets in blocks of B.
const int B = 4096;
vector<int> count_reach(int n, vector<vector<int>>& out) {
vector<int> indeg(n, 0), order;
for (int v = 0; v < n; v++) for (int u : out[v]) indeg[u]++;
for (int v = 0; v < n; v++) if (!indeg[v]) order.push_back(v);
for (int i = 0; i < (int)order.size(); i++)
for (int u : out[order[i]]) if (--indeg[u] == 0) order.push_back(u);
vector<int> ans(n, 0);
vector<bitset<B>> r(n);
for (int lo = 0; lo < n; lo += B) { // targets lo .. lo + B - 1
for (int k = n - 1; k >= 0; k--) { // reverse topological order: children first
int v = order[k];
r[v].reset();
if (v >= lo && v < lo + B) r[v][v - lo] = 1;
for (int u : out[v]) r[v] |= r[u];
}
for (int v = 0; v < n; v++) ans[v] += r[v].count();
}
return ans;
}
int main() {
int n = 5; // 0 -> 1 -> 2, 0 -> 3, 3 -> 2, 4 alone
vector<vector<int>> out = {{1, 3}, {2}, {}, {2}, {}};
for (int x : count_reach(n, out)) cout << x << " ";
cout << "\n";
mt19937 gen(86);
for (int it = 1; it <= 100; it++) {
int m = gen() % 40 + 1;
vector<vector<int>> g(m);
for (int e = 0; e < 3 * m; e++) { int a = gen() % m, b = gen() % m; if (a < b) g[a].push_back(b); }
vector<int> fast = count_reach(m, g);
for (int s = 0; s < m; s++) { // BFS from every node
vector<char> seen(m, 0); queue<int> q; q.push(s); seen[s] = 1; int c = 0;
while (!q.empty()) { int x = q.front(); q.pop(); c++; for (int y : g[x]) if (!seen[y]) { seen[y] = 1; q.push(y); } }
if (c != fast[s]) { cout << "differs on test " << it << "\n"; return 0; }
}
}
cout << "all 100 tests agree\n";
}
Output:
4 2 1 2 1
all 100 tests agree
Node 0 reaches 0, 1, 2, 3; node 1 reaches 1, 2; node 2 only itself; node 3 reaches 3, 2; node 4 only itself. The stress test compares with a BFS from every node.
3. Strings that differ in one place. n binary strings of length L (n ≤ 3000, L ≤ 2000). Count the pairs that differ in exactly one position.
Solution
Two strings differ exactly where their XOR has a 1. So count pairs with (s[i] ^ s[j]).count() == 1: O(n² · L / 64).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int L = 2000; // longest string
int main() {
int n, len;
cin >> n >> len;
vector<bitset<L>> s(n);
for (int i = 0; i < n; i++) {
string t;
cin >> t;
for (int j = 0; j < len; j++) if (t[j] == '1') s[i][j] = 1;
}
ll pairs = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if ((s[i] ^ s[j]).count() == 1) pairs++; // differ in exactly one place
cout << pairs << "\n";
}
Input and output:
4 3
101
100
001
111
3
101 differs from 100, 001 and 111 in one place each; the other pairs differ in two places.
4. Bitset LCS. The longest common subsequence of two strings of length up to 5 · 10^4 (lowercase letters).
Solution
The normal LCS DP is O(|a| · |b|) = 2.5 · 10^9. In each DP row the values grow by 0 or 1 from one column to the next, so a row can be stored as bits (bit i on where the row grows). A known bit-parallel update turns one whole row into the next with word operations: X = M[c] | S, Y = (S << 1) | 1, S = X & ~(X − Y), where M[c] marks the positions of character c in a, and the subtraction is a big-number subtraction across words (with borrows, which std::bitset cannot do, so we use our own unsigned long long words). The LCS is the number of bits on in S. Work: O(|a| · |b| / 64).
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
// Bit-parallel LCS: one row of the DP is kept as bits, and a whole row is updated with
// a few word operations, including one big subtraction with borrows.
int lcs_bits(const string& a, const string& b) {
int n = a.size(), W = (n + 63) / 64;
vector<vector<ull>> match(26, vector<ull>(W, 0)); // match[c]: positions of c in a
for (int i = 0; i < n; i++) match[a[i] - 'a'][i / 64] |= 1ULL << (i % 64);
vector<ull> S(W, 0), X(W), Y(W);
for (char ch : b) {
const vector<ull>& M = match[ch - 'a'];
ull carry = 1; // Y = (S << 1) | 1
for (int k = 0; k < W; k++) { Y[k] = (S[k] << 1) | carry; carry = S[k] >> 63; X[k] = M[k] | S[k]; }
ull borrow = 0; // S = X & ~(X - Y)
for (int k = 0; k < W; k++) {
ull d = X[k] - Y[k] - borrow;
borrow = (X[k] < Y[k]) || (X[k] - Y[k] < borrow);
S[k] = X[k] & ~d;
}
}
int res = 0;
for (int k = 0; k < W; k++) res += __builtin_popcountll(S[k]);
return res;
}
int lcs_dp(const string& a, const string& b) {
vector<vector<int>> d(a.size() + 1, vector<int>(b.size() + 1, 0));
for (size_t i = 1; i <= a.size(); i++)
for (size_t j = 1; j <= b.size(); j++)
d[i][j] = a[i - 1] == b[j - 1] ? d[i - 1][j - 1] + 1 : max(d[i - 1][j], d[i][j - 1]);
return d[a.size()][b.size()];
}
int main() {
cout << lcs_bits("chaitime", "cuttingchai") << " " << lcs_dp("chaitime", "cuttingchai") << "\n";
mt19937 gen(86);
for (int it = 1; it <= 500; it++) {
string a(gen() % 150 + 1, 'a'), b(gen() % 150 + 1, 'a');
for (char& c : a) c = 'a' + gen() % 3;
for (char& c : b) c = 'a' + gen() % 3;
if (lcs_bits(a, b) != lcs_dp(a, b)) { cout << "differs on test " << it << "\n"; return 0; }
}
cout << "all 500 tests agree\n";
}
Output:
4 4
all 500 tests agree
"chaitime" and "cuttingchai" share "chai" (length 4), and the bit version agrees with the O(n·m) DP on 500 random tests.
Quick quiz
bitset<8> a("01011010"), b("00111100");
cout << (a & b).count() << " " << (a ^ b).count();
A) 2 4 · B) 2 6 · C) 4 4 · D) 3 5
Answer
A. a & b = 00011000 has 2 bits on; a ^ b = 01100110 has 4 bits on.
Interview questions
- What is a bitset and why is it fast? A fixed-size array of bits packed into 64-bit words; whole-bitset AND, OR, XOR, shifts and count work a word at a time, so they cost about N / 64 steps instead of N.
- What does O(n³ / 64) mean if Big-O ignores constants? Strictly it is still O(n³); writing / 64 (or / w) records the word-level speed-up, which is what decides a contest verdict.
- How does
can |= can << xsolve subset sum? Bit s ofcansays whether total s is possible; shifting by x adds the new box to every old total at once, and OR keeps the old totals. The shift reads the old row, so each box is used once. - How do you count triangles with bitsets? For each edge (i, j), the third vertices are the common neighbours
adj[i] & adj[j]; add their count, then divide the total by 3. - Why can't you write
bitset<n>with n from input? The size is a template argument, part of the type, so it must be a compile-time constant. Use the maximum size, a template that doubles the size, or a dynamic bit array (boost::dynamic_bitset, or your ownvector<unsigned long long>). vector<bool>vsbitset? Both pack bits;vector<bool>can change size but has no whole-row operators (<<,&,count), so it gives no 64× speed-up.- When does a bitset NOT help? When the work is not a whole-row operation (random single-bit reads in a loop), or when the rows don't fit in memory (n² / 8 bytes for an n × n matrix).
- What is popcount? The number of 1 bits in a word; a single CPU instruction (
__builtin_popcountll), whichbitset::count()uses word by word.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Bit | One binary digit: 0 or 1 | bit 3 of 00101101 is 1 |
| Word | The block of bits the CPU works on at once: 64 bits | unsigned long long |
| Word-level parallelism | Doing 64 bit operations with one word instruction | AND of two words |
std::bitset<N> |
A fixed-size row of N bits with whole-row operators | bitset<3000> adj[i] |
| Compile-time constant | A value known when the program is compiled | const int MAXS = 3000 * 1000; |
| Template argument | A value or type given in < > that becomes part of the type |
the N in bitset<N> |
AND (&) |
Bit on where both are on | 00101101 & 00001111 = 00001101 |
OR (|) |
Bit on where either is on | 00101101 | 00001111 = 00101111 |
XOR (^) |
Bit on where they differ | a ^ b |
Shift (<<, >>) |
Move every bit k places; bits past the end are lost | 00101101 << 2 = 10110100 |
count() |
How many bits are on | a.count() == 4 |
| Popcount | The CPU instruction that counts the 1 bits of a word | __builtin_popcountll |
| Subset sum | Which totals can be made from a set of numbers, each used once | possible truck loads |
| Dynamic programming (DP) | Building answers from answers to smaller cases | can[s] |
| Adjacency matrix | An n × n table: entry (i, j) is 1 if i and j are joined | the friend rows g[i] |
| Triangle | Three vertices all joined to each other | {0, 1, 2} |
| Common friend (common neighbour) | A vertex joined to both i and j | adj[i] & adj[j] |
| DAG | A directed graph with no cycles | homework 2 |
| Topological order | An order of a DAG's nodes where every edge goes forward | children after parents |
| LCS | Longest common subsequence of two strings | "chai" |
| Brute force / referee | A slow, surely correct solution used to check a fast one | all 2^n splits |
| Stress test | Many random small tests comparing fast and brute | all 1000 tests agree |
| Time Limit Exceeded (TLE) | The program ran longer than the limit | the bool-array DP |
vector<bool> |
A packed, resizable bit vector without whole-row operators | not a bitset |
| Undefined behaviour | Code whose result C++ does not define | 1 << 40 with an int |
Summary
- A CPU word holds 64 bits; a
bitsetdoes AND, OR, XOR, shifts andcount()a word at a time: about N / 64 steps. - Subset sum (Two Trucks):
can |= can << xreplaces the inner loop; n · S / 64 instead of n · S. - Triangles (Friend Triangles): sum
(adj[i] & adj[j]).count()over edges, divide by 3; n³ / 128 word steps instead of n³ / 6 checks. - The size is a compile-time constant: size it for the worst case (or double it with a template), and never too small, because
<<silently drops bits. - Same idea, about 64 times faster; always stress test against the brute force.
Solutions in C++, Java and Python
Problem B1 · Two Trucks
C++ (the accepted solution from the video)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> w(n);
for (int& x : w) cin >> x;
const int MAXS = 3000 * 1000; // the largest possible total
bitset<MAXS + 1> can; // bit s on: total s is possible
can[0] = 1;
for (int x : w) can |= can << x; // every old total, plus x
int S = accumulate(w.begin(), w.end(), 0);
int best = INT_MAX;
for (int s = 0; s <= S; s++)
if (can[s]) best = min(best, abs(S - 2 * s)); // truck 1 gets s, truck 2 gets S - s
cout << best << "\n";
}
Java (a long[] of words; the shift by x = 64·ws + bs is done word by word from the top, so the old words are read before they are changed)
import java.util.*;
import java.io.*;
public class Main { // Two Trucks with a long[] bitset
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken(); int n = (int) in.nval;
int[] w = new int[n]; int S = 0;
for (int i = 0; i < n; i++) { in.nextToken(); w[i] = (int) in.nval; S += w[i]; }
int words = (S >> 6) + 1;
long[] can = new long[words];
can[0] = 1L; // total 0 is possible
for (int x : w) { // can |= can << x, word by word, from the top
int ws = x >> 6, bs = x & 63;
for (int i = words - 1; i >= ws; i--) {
long v = can[i - ws] << bs;
if (bs != 0 && i - ws - 1 >= 0) v |= can[i - ws - 1] >>> (64 - bs);
can[i] |= v;
}
}
int best = Integer.MAX_VALUE;
for (int s = 0; s <= S; s++)
if ((can[s >> 6] >>> (s & 63) & 1L) != 0) best = Math.min(best, Math.abs(S - 2 * s));
System.out.println(best);
}
}
Python (a Python int is an arbitrary-size bitset: can |= can << x)
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); w = list(map(int, data[1:1 + n]))
S = sum(w)
can = 1 # a Python int used as a bitset: bit s on = total s possible
for x in w:
can |= can << x # every old total, plus x
best = min(abs(S - 2 * s) for s in range(S + 1) if can >> s & 1)
print(best)
main()
All three on the samples (real runs):
| Input | C++ | Java | Python |
|---|---|---|---|
5 / 3 1 4 2 2 |
0 |
0 |
0 |
1 / 7 |
7 |
7 |
7 |
2 / 1000 1 |
999 |
999 |
999 |
Problem B2 · Friend Triangles
C++ (the accepted solution from the video)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> g(n); // g[i][j] == '1': i and j are friends
for (auto& row : g) cin >> row;
vector<bitset<3000>> adj(n); // row i: the friends of i, as bits
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (g[i][j] == '1') adj[i][j] = 1;
ll triangles = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (adj[i][j])
triangles += (adj[i] & adj[j]).count(); // common friends
cout << triangles / 3 << "\n"; // each triangle has 3 edges
}
Java (each row is a long[]; Long.bitCount is popcount)
import java.util.*;
import java.io.*;
public class Main { // Friend Triangles with long[] rows
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
int words = (n + 63) >> 6;
long[][] adj = new long[n][words]; // row i: the friends of i, as bits
for (int i = 0; i < n; i++) {
String row = br.readLine().trim();
for (int j = 0; j < n; j++)
if (row.charAt(j) == '1') adj[i][j >> 6] |= 1L << (j & 63);
}
long triangles = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if ((adj[i][j >> 6] >>> (j & 63) & 1L) != 0)
for (int k = 0; k < words; k++) // common friends, 64 at a time
triangles += Long.bitCount(adj[i][k] & adj[j][k]);
System.out.println(triangles / 3); // each triangle has 3 edges
}
}
Python (each row is an int; int.bit_count() is popcount, Python 3.10+)
import sys
def main():
data = sys.stdin.read().split()
n = int(data[0]); rows = data[1:1 + n]
adj = [int(r[::-1], 2) for r in rows] # bit j of adj[i] = rows[i][j]
triangles = 0
for i in range(n):
for j in range(i + 1, n):
if adj[i] >> j & 1:
triangles += (adj[i] & adj[j]).bit_count() # common friends
print(triangles // 3)
main()
All three on the samples (real runs):
| Input | C++ | Java | Python |
|---|---|---|---|
| the 5-user sample | 4 |
4 |
4 |
1 / 0 |
0 |
0 |
0 |
Python big-int operations are also word-level inside, so these are far faster than pure Python loops over bits; for the largest tests in a real contest, C++ is still the safe choice.