hardCodingConceptMidSenior
Assign n tasks to n workers at minimum cost, with n up to 20. Why a bitmask, and what does it cost?
Bitmask DP keeps the cheapest cost for every subset of workers already used. The number of set bits says which task comes next, so there are 2^n states with n moves each, O(2^n * n) time and 2^n memory. At n = 20 that is about a million states, where trying all 20! orders is hopeless.
4 min readUpdated 2026-10-10Target archetype: Big Tech
Answer
Short answer
Use bitmask DP over the set of workers already used. Let dp[mask] be the minimum cost of giving the first popcount(mask) tasks to exactly the workers in mask; the next task is fixed by the count, so each state tries at most n free workers. That is O(2^n · n) time and O(2^n) memory: roughly a million states and twenty million steps at n = 20.
Was this answer helpful?
Likely follow-ups
- There are 12 tasks and 20 workers. Which side does the mask go over, and what does that change in the cost?
- Return the actual assignment, not just the minimum cost. What extra memory do you need?
- A worker's cost for a task rises if a named rival worker is already busy. Does your recurrence survive?
- Write the top-down memoised version. How deep does the recursion go, and is that a risk?
Related questions
- Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra give the wrong answer?mediumAlso on dynamic-programming5 min
- Every number in the array appears three times except one. Find the single number in O(1) extra space, and make sure it works for negatives.mediumAlso on bit-manipulation5 min
- Edit distance where insert costs 1, delete costs 2 and replace costs 3. Define the DP state and the recurrence, and tell me what changes from the classic version.mediumAlso on dynamic-programming4 min
- Count the set bits in a 32-bit integer. Now tell me what your loop does when I hand it a negative number.mediumAlso on bit-manipulation4 min