These are the notes for Competitive Programming episode 36, part five of the dynamic programming section. Kiran, a delivery rider, starts at the shop, must visit every house exactly once and ride back. An original problem, Delivery Loop, asks for the shortest round trip. Riding to the nearest house prints 40 instead of 32; trying all (n − 1)! orders is right but gets TLE at 14 places. The future only needs which houses are done (a set) and where Kiran is now, not the order of the past. A set of up to 17 places fits in the bits of one int, a bitmask, so the state is dp[mask][last], and each ride adds one bit. O(2^n · n²) ≈ 3.8 · 10^7 for n = 17, which is exactly why n was so small. 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
Kiran leaves the shop with a bag of parcels, drops one at every house on his list, and comes back for the next batch. Petrol costs money, so the order matters. This is the classic travelling salesman problem (TSP): no fast algorithm is known for large n, but for n ≤ about 20 bitmask DP solves it exactly.
Problem M · Delivery Loop
(Written for this course, in the style of an AtCoder Beginner Contest problem.)
There are n places; place 0 is the shop. d[i][j] is the distance from place i to place j. Start at the shop, visit every place exactly once, and return to the shop. Print the shortest total distance.
- Input: n (1 ≤ n ≤ 17), then the n × n table d (0 ≤ d[i][j] ≤ 10^6, d[i][i] = 0).
- Output: the shortest round trip.
Sample 1:
4
0 6 5 16
6 0 9 10
5 9 0 11
16 10 11 0
Output: 32 (shop → 1 → 3 → 2 → shop: 6 + 10 + 11 + 5). Sample 2: 1 / 0 → 0 (only the shop).
A tiny n is a hint. n ≤ 20 usually means 2^n is affordable.
Attempt 1: ride to the nearest house (wrong)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<vector<ll>> d(n, vector<ll>(n));
for (auto &row : d) for (ll &x : row) cin >> x;
vector<bool> done(n, false);
done[0] = true;
int at = 0;
ll total = 0;
for (int step = 1; step < n; step++) {
int nxt = -1; // nearest house not done
for (int j = 0; j < n; j++)
if (!done[j] && (nxt == -1 || d[at][j] < d[at][nxt])) nxt = j;
total += d[at][nxt];
done[nxt] = true;
at = nxt;
}
total += d[at][0]; // back to the shop
cout << total << "\n";
return 0;
}
Sample 1 prints 40 (expected 32): shop → 2 (5) → 1 (9) → 3 (10) → shop (16). The nearest-first choices leave Kiran at house 3, and the ride home is the longest road of all.
Attempt 2: every order (Time Limit Exceeded)
next_permutation (episode 13) steps through every ordering of houses 1 … n − 1:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<vector<ll>> d(n, vector<ll>(n));
for (auto &row : d) for (ll &x : row) cin >> x;
vector<int> order;
for (int i = 1; i < n; i++) order.push_back(i);
ll best = LLONG_MAX;
do { // every order of the houses
ll len = 0;
int at = 0;
for (int h : order) { len += d[at][h]; at = h; }
best = min(best, len + d[at][0]);
} while (next_permutation(order.begin(), order.end()));
cout << best << "\n";
return 0;
}
Sample 1: 32, correct. With 14 places it prints Time Limit Exceeded: 13! ≈ 6.2 · 10^9 orders. At n = 17 it would be 16! ≈ 2 · 10^13.
The key question: what does the future need to know?
Two rides, shop → 1 → 3 → 4 and shop → 3 → 1 → 4, have visited the same houses and both stand at house 4. From here they have exactly the same choices. So the future only needs the set of visited places and the current place.
A set in one integer: bitmasks
Give place j the bit 2^j (1 << j). A set is the sum of its places' bits:
| place | shop (0) | 1 | 2 | 3 |
|---|---|---|---|---|
| bit value | 1 | 2 | 4 | 8 |
| visited? | ✓ | ✓ | ✓ |
The set {0, 1, 3} is 1 + 2 + 8 = 11 (binary 1011). The basic operations (episode 17):
| Operation | Code |
|---|---|
| is j in the set? | mask & (1 << j) (non-zero means yes) |
| add j | mask | (1 << j) |
| remove j | mask & ~(1 << j) |
| all n places | (1 << n) - 1 |
| size of the set | __builtin_popcount(mask) |
Because a set is a number, it can be an array index: dp[mask][last] is an ordinary 2D table with 2^n rows.
The bitmask DP
- State: dp[mask][last] = the shortest ride that starts at the shop, has visited exactly the places in mask, and now stands at last.
- Transition: for every j not in mask: dp[mask | (1 << j)][j] = min(…, dp[mask][last] + d[last][j]).
- Base: dp[1][0] = 0 (only the shop visited, standing at the shop). Everything else starts at +∞.
- Order: mask increasing. Adding a bit always makes the number bigger, so every state is final before it is used.
- Answer: min over last of dp[full][last] + d[last][0] (ride home).
States: 2^n · n ≈ 2.2 · 10^6 for n = 17; each tries n moves: O(2^n · n²) ≈ 3.8 · 10^7.
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 n;
cin >> n;
vector<vector<ll>> d(n, vector<ll>(n));
for (auto &row : d) for (ll &x : row) cin >> x;
const ll INF = LLONG_MAX / 4;
// dp[mask][last] = shortest ride from the shop that has visited exactly
// the places in mask, and is now standing at last
vector<vector<ll>> dp(1 << n, vector<ll>(n, INF));
dp[1][0] = 0; // only the shop, standing at the shop
for (int mask = 1; mask < (1 << n); mask++)
for (int last = 0; last < n; last++) {
if (dp[mask][last] == INF) continue;
for (int j = 0; j < n; j++)
if (!(mask & (1 << j))) // j not visited yet
dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][last] + d[last][j]);
}
ll best = INF;
int full = (1 << n) - 1;
for (int last = 0; last < n; last++)
best = min(best, dp[full][last] + d[last][0]); // ride home
cout << best << "\n";
return 0;
}
| Input | Output |
|---|---|
| sample 1 | 32 |
1 / 0 (only the shop) |
0 |
| the 14-place test that timed out | 99 (instant) |
The worst case, built inside main (n = 17):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 17; // worst case, built here
vector<vector<ll>> d(n, vector<ll>(n, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j) d[i][j] = (i * j * 7 + i + j) % 100 * 10000 + 1;
const ll INF = LLONG_MAX / 4;
// dp[mask][last] = shortest ride from the shop that has visited exactly
// the places in mask, and is now standing at last
vector<vector<ll>> dp(1 << n, vector<ll>(n, INF));
dp[1][0] = 0; // only the shop, standing at the shop
for (int mask = 1; mask < (1 << n); mask++)
for (int last = 0; last < n; last++) {
if (dp[mask][last] == INF) continue;
for (int j = 0; j < n; j++)
if (!(mask & (1 << j))) // j not visited yet
dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][last] + d[last][j]);
}
ll best = INF;
int full = (1 << n) - 1;
for (int last = 0; last < n; last++)
best = min(best, dp[full][last] + d[last][0]); // ride home
cout << best << "\n";
return 0;
}
Output: 1810017, well within the time limit. Memory: 2^17 × 17 long longs ≈ 18 MB.
A stress test
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(vector<vector<ll>>& d) {
int n = d.size();
vector<int> o;
for (int i = 1; i < n; i++) o.push_back(i);
ll best = LLONG_MAX;
do {
ll len = 0;
int at = 0;
for (int h : o) { len += d[at][h]; at = h; }
best = min(best, len + d[at][0]);
} while (next_permutation(o.begin(), o.end()));
return best;
}
ll fast(vector<vector<ll>>& d) {
int n = d.size();
const ll INF = LLONG_MAX / 4;
vector<vector<ll>> dp(1 << n, vector<ll>(n, INF));
dp[1][0] = 0;
for (int m = 1; m < (1 << n); m++)
for (int l = 0; l < n; l++) if (dp[m][l] < INF)
for (int j = 0; j < n; j++) if (!(m >> j & 1))
dp[m | 1 << j][j] = min(dp[m | 1 << j][j], dp[m][l] + d[l][j]);
ll best = INF;
for (int l = 0; l < n; l++) best = min(best, dp[(1 << n) - 1][l] + d[l][0]);
return best;
}
int main() {
mt19937 rng(36);
for (int t = 1; t <= 1000; t++) {
int n = rng() % 7 + 1;
vector<vector<ll>> d(n, vector<ll>(n, 0));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j) d[i][j] = rng() % 50 + 1;
if (brute(d) != fast(d)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 1000 tests passed";
}
Output: all 1000 tests passed.
One more bitmask DP: who gets which area?
The shop has n riders and n delivery areas; sending rider i to area j costs cost[i][j]. Every rider gets exactly one area; find the cheapest total. Trying every assignment is n! again. Hand out areas to riders in order (rider 0, then rider 1, …): the set of taken areas then tells you which rider is next, __builtin_popcount(mask). So the state is just dp[mask], and the next rider takes any free area j. O(2^n · n).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<vector<ll>> cost(n, vector<ll>(n));
for (auto &row : cost) for (ll &x : row) cin >> x;
// dp[mask] = cheapest way to give the jobs in mask
// to the first popcount(mask) riders
vector<ll> dp(1 << n, LLONG_MAX / 4);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int i = __builtin_popcount(mask); // the next rider
if (i == n) continue;
for (int j = 0; j < n; j++)
if (!(mask & (1 << j)))
dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[i][j]);
}
cout << dp[(1 << n) - 1] << "\n";
return 0;
}
Input 3 / 9 2 7 / 6 4 3 / 5 8 1 → 9 (rider 0 → area 1 for 2, rider 1 → area 0 for 6, rider 2 → area 2 for 1).
Complexity vs the constraints
| Approach | Time | Verdict |
|---|---|---|
| every order | O((n − 1)! · n) ≈ 3.6 · 10^14 at n = 17 | TLE at n = 14 |
| nearest house first | O(n²) | wrong (40 vs 32) |
| dp[mask][last] | O(2^n · n²) ≈ 3.8 · 10^7 | accepted |
Rule of thumb: 2^n · n² is fine up to n ≈ 20 (4 · 10^8 is already tight); 2^n · n alone up to about 23; beyond that, look for another idea.
Common mistakes (and the real outputs)
Bug 1: operator precedence in a bit test
#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<vector<ll>> d(n, vector<ll>(n));
for (auto &row : d) for (ll &x : row) cin >> x;
const ll INF = LLONG_MAX / 4;
// dp[mask][last] = shortest ride from the shop that has visited exactly
// the places in mask, and is now standing at last
vector<vector<ll>> dp(1 << n, vector<ll>(n, INF));
dp[1][0] = 0; // only the shop, standing at the shop
for (int mask = 1; mask < (1 << n); mask++)
for (int last = 0; last < n; last++) {
if (dp[mask][last] == INF) continue;
for (int j = 0; j < n; j++)
if (mask & 1 << j == 0) // j not visited yet?
dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][last] + d[last][j]);
}
ll best = INF;
int full = (1 << n) - 1;
for (int last = 0; last < n; last++)
best = min(best, dp[full][last] + d[last][0]); // ride home
cout << best << "\n";
return 0;
}
On sample 1 it prints 2305843009213693951, which is the INF value (LLONG_MAX / 4). In C++, == binds tighter than &, and << tighter than both, so mask & 1 << j == 0 means mask & ((1 << j) == 0), which is mask & 0: always false. No move is ever made. With -Wall, g++ warns: suggest parentheses around comparison in operand of '&'. Always write !(mask & (1 << j)) or (mask >> j & 1) == 0.
Bug 2: the wrong base case
#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<vector<ll>> d(n, vector<ll>(n));
for (auto &row : d) for (ll &x : row) cin >> x;
const ll INF = LLONG_MAX / 4;
// dp[mask][last] = shortest ride from the shop that has visited exactly
// the places in mask, and is now standing at last
vector<vector<ll>> dp(1 << n, vector<ll>(n, INF));
for (int i = 0; i < n; i++) dp[1 << i][i] = 0; // start anywhere?
for (int mask = 1; mask < (1 << n); mask++)
for (int last = 0; last < n; last++) {
if (dp[mask][last] == INF) continue;
for (int j = 0; j < n; j++)
if (!(mask & (1 << j))) // j not visited yet
dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][last] + d[last][j]);
}
ll best = INF;
int full = (1 << n) - 1;
for (int last = 0; last < n; last++)
best = min(best, dp[full][last] + d[last][0]); // ride home
cout << best << "\n";
return 0;
}
On sample 1 it prints 24 (expected 32). Starting from every place allows the ride house 3 → 1 → 2 → shop (10 + 9 + 5): a one-way trip that never rides the 16 km road out of the shop. The base case decides where the ride starts: dp[1][0] = 0 only.
Summary table
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| ride to the nearest house | 40 instead of 32 |
the ride home can be long | DP over sets |
if (mask & 1 << j == 0) |
2305843009213693951 |
== binds tighter than & |
!(mask & (1 << j)) |
dp[1 << i][i] = 0 for all i |
24 instead of 32 |
not a loop from the shop | dp[1][0] = 0 only |
dp[1 << n][n] with n = 25 |
800 million cells: MLE | 2^n grows fast | check n ≤ ~20 first |
1 << n for n ≥ 31 |
undefined / negative | int has 31 value bits |
1LL << n |
Mini project
Build a "route planner": read the distance table, run the bitmask DP and also store parent[mask][last] (the previous place). Walk back from the best final place to print the full route (shop → … → shop) and its length. Then add the option "Kiran need not return", which only changes the answer line. Compare with the nearest-house route on random inputs and print how often greedy is optimal.
Practice
-
Kiran need not return to the shop.
Answer
Same DP; the answer is min over last of dp[full][last] (no ride home). Sample 1: <b>24</b> (shop → 2 → 1 → 3: 5 + 9 + 10). -
Count the valid assignments: rider i accepts only some areas (ok[i][j] = 1). How many ways can every rider get a different accepted area (mod 10^9 + 7)?
Answer
The same dp[mask] with + instead of min: ways[0] = 1, ways[mask | 1<<j] += ways[mask] when ok[popcount(mask)][j]. If every rider accepts every area, the answer is n!: <b>6</b> for n = 3. -
Print the delivery order for sample 1.
Answer
Store the parent of each state and walk back from the best final state: <b>shop → 1 → 3 → 2 → shop</b> (6 + 10 + 11 + 5 = 32). The reversed loop shop → 2 → 3 → 1 → shop is equally short. -
Count Hamiltonian paths from the shop that visit every place (mod 10^9 + 7), given which roads exist.
Answer
Replace min by +: cnt[1][0] = 1, cnt[mask | 1<<j][j] += cnt[mask][last] for each road last → j. With all roads present and n = 4: <b>6</b> = 3! orders.
Quick quiz
mask = 13, bit j = place j. Which places are visited?
A) 0, 1, 2 · B) 0, 2, 3 · C) 1, 2, 3 · D) 0, 1, 3
Answer
B. 13 = 8 + 4 + 1 = binary 1101: bits 0, 2 and 3.
Interview questions
- When do you think of bitmask DP? When the state must remember a subset of a small set (n ≤ about 20) and the order inside the subset doesn't matter.
- What is the complexity of TSP by bitmask DP (Held–Karp)? O(2^n · n²) time, O(2^n · n) memory.
- Why is increasing mask order valid? Transitions only add bits, and adding a bit makes the number larger, so all predecessors of a mask are smaller.
- How do you iterate over all subsets of a mask?
for (int s = mask; s > 0; s = (s - 1) & mask): 3^n in total over all masks (episode 39, SOS DP, goes further). - What are the precedence traps with bits?
==and!=bind tighter than&,^,|;+binds tighter than<<. Bracket every bit expression. - Why does greedy fail for TSP? A locally short ride can force a long ride later, especially the ride home.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Bitmask | An integer whose bits encode a subset | 11 = {0, 1, 3} |
| Bitmask DP | DP whose state contains a subset as a bitmask | dp[mask][last] |
| Travelling salesman problem (TSP) | Shortest tour visiting every place once | Delivery Loop |
| Hamiltonian path / cycle | A path / cycle visiting every vertex exactly once | shop → 1 → 3 → 2 → shop |
| Held–Karp algorithm | The O(2^n · n²) bitmask DP for TSP | this episode |
1 << j |
The number with only bit j set | 1 << 3 = 8 |
mask | (1 << j) |
Add j to the set | 11 |
mask & (1 << j) |
Test whether j is in the set | 11 & 4 = 0 |
| Operator precedence | Which operator binds first | == before & |
| INF sentinel | A huge value meaning "unreachable" | LLONG_MAX / 4 |
| Greedy | Take the locally best choice | nearest house first |
| Stress test | Fast vs brute force on random small tests | all 1000 tests passed |
Summary
- Nearest house first fails (
40vs32); every order TLEs at n = 14. - The future needs which places are done + where you are: dp[mask][last].
- A set is stored in the bits of one int: add with
mask | (1 << j), test withmask & (1 << j). - Base dp[1][0] = 0, order: mask increasing, answer: min dp[full][last] + d[last][0]. O(2^n · n²), so n ≤ ~20.
- Real bugs:
mask & 1 << j == 0(prints INF), starting everywhere (24vs32).
Solutions in C++, Java and Python
Problem M · Delivery Loop
C++
#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<vector<ll>> d(n, vector<ll>(n));
for (auto &row : d) for (ll &x : row) cin >> x;
const ll INF = LLONG_MAX / 4;
// dp[mask][last] = shortest ride from the shop that has visited exactly
// the places in mask, and is now standing at last
vector<vector<ll>> dp(1 << n, vector<ll>(n, INF));
dp[1][0] = 0; // only the shop, standing at the shop
for (int mask = 1; mask < (1 << n); mask++)
for (int last = 0; last < n; last++) {
if (dp[mask][last] == INF) continue;
for (int j = 0; j < n; j++)
if (!(mask & (1 << j))) // j not visited yet
dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][last] + d[last][j]);
}
ll best = INF;
int full = (1 << n) - 1;
for (int last = 0; last < n; last++)
best = min(best, dp[full][last] + d[last][0]); // ride home
cout << best << "\n";
return 0;
}
Java
import java.util.*;
import java.io.*;
public class Main {
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;
long[][] d = new long[n][n];
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { in.nextToken(); d[i][j] = (long) in.nval; }
final long INF = Long.MAX_VALUE / 4;
long[][] dp = new long[1 << n][n];
for (long[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0; // only the shop, at the shop
for (int mask = 1; mask < (1 << n); mask++)
for (int last = 0; last < n; last++) {
if (dp[mask][last] == INF) continue;
for (int j = 0; j < n; j++)
if ((mask & (1 << j)) == 0) {
int nm = mask | (1 << j);
dp[nm][j] = Math.min(dp[nm][j], dp[mask][last] + d[last][j]);
}
}
long best = INF;
for (int last = 0; last < n; last++) best = Math.min(best, dp[(1 << n) - 1][last] + d[last][0]);
System.out.println(best);
}
}
Python (fine for the samples; 3.8 · 10^7 steps at n = 17 is too slow in pure Python)
import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
d = [list(map(int, data[1 + i * n: 1 + (i + 1) * n])) for i in range(n)]
INF = float("inf")
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # only the shop, at the shop
for mask in range(1, 1 << n):
row = dp[mask]
for last in range(n):
cur = row[last]
if cur == INF:
continue
for j in range(n):
if not mask & (1 << j): # j not visited yet
nm = mask | (1 << j)
if cur + d[last][j] < dp[nm][j]:
dp[nm][j] = cur + d[last][j]
full = (1 << n) - 1
print(min(dp[full][last] + d[last][0] for last in range(n)))
main()
Next episode: DP 6: digit DP (counting numbers up to 10^18, digit by digit).