DP Optimization Quiz: Prefix Sums, Deque and Bitmask DP Test
A timed practice test on DP optimisations in C++: prefix-sum transitions, the monotonic deque, bitmask DP and its limits, and a travelling-salesman program.
- Course: Competitive Programming study plan
- Module: DP optimisations
- Kind: Checkpoint — cleared at 70%
- Reading time: 60 min
- Runtime: Clang 18 · C++20
Checkpoint — DP optimisations is the checkpoint that closes the DP optimisations module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
A timed checkpoint on the module: prefix sums over the previous row, the monotonic deque for a window maximum, the cost arithmetic that says when an optimisation is needed, and DP over subsets.
How it works. Sixty minutes from the moment you start the timer: ten questions and one program. 70% on the questions and the program accepted clears the module.
Before you start, make sure you can answer these from memory:
- The prefix-sum form of
dp[i−1][k−c] + … + dp[i−1][k], and why the difference needs+ MOD. - Which deque entries are popped from the back, and why that is safe.
- How many states and transitions the TSP bitmask DP has at n = 12, and at what n it stops fitting.
- How to test and set bit j of a mask.
The program is the shortest round trip through up to 12 cities.
Common questions
How does the bitmask DP for the travelling salesman problem work?
Let dp[mask][v] be the cheapest path that starts at city 0, visits exactly the cities in mask and ends at v. Start from dp[1][0] = 0; from each state, move to any city u outside mask. The answer is the minimum of dp[full][v] + d[v][0]. It costs O(2^n · n²) time and O(2^n · n) memory.
Why are masks processed in increasing numeric order?
Every transition adds a bit, so the new mask is numerically larger than the old one. Looping masks from 0 upwards therefore finishes every state before any state that extends it is read — the same reason a 1-D DP loops i upwards.
Exercise
Shortest round trip
There are n cities and d[i][j], the cost of travelling from city i to city j (not necessarily equal to d[j][i]). Starting at city 0, visit every city exactly once and return to city 0. Print the smallest total cost (0 when n = 1).
Use bitmask DP: dp[mask][v] = cheapest path from 0 that has visited exactly mask and ends at v.
Constraints: 1 ≤ n ≤ 12, 0 ≤ d[i][j] ≤ 1000, d[i][i] = 0. Input: n, then n rows of n integers. Output: the cost.
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0prints 80 — 0 → 1 → 3 → 2 → 0.
In this module: DP optimisations
← DP optimisations — prefix sums, a monotonic deque and bitmasks · KMP, the Z-function and rolling hashes →