DP: Bitmask Dynamic Programming

Bitmask dynamic programming is a powerful technique for solving combinatorial optimization problems where you need to consider all subsets of a set. By representing subsets as integers, it transforms exponential state spaces into manageable DP tables, enabling efficient solutions to classic problems like the Traveling Salesman Problem. Mastering bitmask DP allows you to tackle NP-hard challenges in competitive programming and real-world scheduling when the number of elements is small.

Representing Subsets with Bitmasks

The foundation of bitmask DP lies in using bitmasks—n-bit integers—to represent subsets of n elements. Each bit in the integer corresponds to one element: a 1 means the element is included in the subset, and a 0 means it is excluded. For example, with n=4, the bitmask $1010_2$ (decimal 10) represents the subset containing the first and third elements (assuming zero-based indexing from the least significant bit). This compact representation allows you to iterate over all $2^n$ subsets using a simple loop from 0 to $2^n-1$.

Bitwise operations are key to manipulating these masks efficiently. The bitwise AND ($\&$) checks if an element is present, bitwise OR ($|$) adds an element, and bitwise XOR ($\wedge$) toggles membership. For instance, to check if the i-th element is in mask, you use if (mask & (1 << i)). To add it, mask | (1 << i). This integer-based approach is far faster than using boolean arrays or sets, making it ideal for DP states.

Consider a simple scenario: you have a set of tasks, and you need to track which ones are completed. Instead of a list, a single integer mask can encode the completion status, enabling quick transitions. This efficiency is why bitmask DP is a staple in algorithm design for subset-based problems.

Dynamic Programming over Subsets

With subset representation handled, dynamic programming over subsets involves defining a DP state that captures the optimal solution for a given mask. Typically, dp[mask] stores the minimum cost or maximum value for the subset represented by mask. The transitions build larger subsets from smaller ones by adding one element at a time, leveraging the optimal substructure property.

The DP process starts with a base case, often dp[0] = 0 for the empty subset. Then, for each mask from 1 to $2^n-1$, you iterate over possible last added elements to compute dp[mask]. For example, if dp[mask] represents the minimum cost to cover the subset mask, you might transition from dp[mask without element i] by adding the cost of including i. The recurrence looks like:

$$dp[mask]=\underset{i\in mask}{\min }\{dp[mask\setminus \{i\}]+cost[i]\}$$

Here, $mask\setminus \{i\}$ is implemented as mask ^ (1 << i) or mask & ~(1 << i). This bottom-up approach ensures that all subsets are processed in increasing order of size, often using iterative loops. The time complexity is $O(2^n\cdot n)$ for basic transitions, but it can vary based on problem specifics.

Implementing the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a classic application of bitmask DP. In TSP, you need to find the shortest possible route that visits each of n cities exactly once and returns to the start. With bitmask DP, you can solve it in $O(n^2\cdot 2^n)$ time, which is feasible for n up to around 20.

Define dp[mask][last] as the minimum cost to visit all cities in the subset mask, ending at city last. The base case: dp[1 << start][start] = 0 for starting at city 0 (or any designated start). Then, for each mask, you iterate over last cities and possible next cities not in mask. The recurrence is:

$$dp[mask|(1<<next)][next]=\min \{dp[mask][last]+dist[last][next]\}$$

After filling the DP table, the answer is the minimum over all last cities of dp[(1 << n) - 1][last] + dist[last][start] to complete the cycle. Here’s a step-by-step outline:

1. Initialize a 2D array dp with dimensions $2^n$ by n, filled with infinity.
2. Set dp[1 << start][start] = 0.
3. For mask from 0 to $2^n-1$:

• For each last city where dp[mask][last] is finite:
• For each next city not in mask:
• New mask = mask | (1 << next)
• Update dp[new mask][next] with min(dp[new mask][next], dp[mask][last] + dist[last][next]).

1. Compute the result by adding the return cost.

This approach efficiently explores all permutations without explicit enumeration, making TSP tractable for small n.

Solving Assignment Problems

Bitmask DP also excels at assignment problems, where you need to assign n tasks to n workers with varying costs, aiming to minimize total cost. Each worker handles exactly one task, and each task is done by one worker. This is known as the assignment problem, solvable with Hungarian algorithm, but bitmask DP offers a straightforward $O(n\cdot 2^n)$ solution for small n.

Let dp[mask] represent the minimum cost to assign tasks corresponding to the set mask to the first k workers, where k is the number of 1s in mask (i.e., workers 0 to k-1). The idea: for the k-th worker (where k = popcount(mask)), assign them an unassigned task i from mask. The recurrence is:

$$dp[mask]=\underset{i\in mask}{\min }\{dp[mask\setminus \{i\}]+cost[k][i]\}$$

Here, k is the index of the worker being assigned, derived from the count of bits in mask. Start with dp[0] = 0 for no tasks assigned. Iterate over all masks, and for each, determine k as the number of set bits, then try assigning each task i in mask to worker k. After processing, dp[(1 << n) - 1] gives the minimum total cost.

For example, with 3 workers and tasks, mask 101 (tasks 0 and 2) might be assigned to workers 0 and 1, and worker 2 would get the remaining task. This method generalizes to various matching scenarios, such as project allocations or team formations, where subset-based states are natural.

When to Use Bitmask DP

Understanding applicability is crucial for effectively deploying bitmask DP. It is best suited for optimization problems where the state involves selecting a subset from a small set of n elements, typically with n ≤ 20 due to the $2^n$ state space. Beyond 20, the exponential growth makes it impractical, so heuristic or approximate methods are needed.

Key indicators include problems where you need to consider all combinations, like covering sets, ordering with constraints, or partitioning. For instance, in graph problems involving Hamiltonian paths or vertex cover on small graphs, bitmask DP can be optimal. It’s also useful in scheduling where resources are limited and tasks have dependencies represented as subsets.

Contrast bitmask DP with other techniques: for larger n, use greedy algorithms or integer programming; for problems with linear structures, standard DP suffices. Always assess if the problem has the optimal substructure and overlapping subproperties essential for DP. If yes, and n is small, bitmask DP is a go-to tool for exact solutions.

Common Pitfalls

1. Off-by-one errors in bit indices: Beginners often confuse zero-based and one-based indexing when setting bits. For example, to represent the i-th element (starting from 0), use 1 << i, not 1 << (i-1). Always double-check your bit shifts against your element numbering to avoid missing or duplicating subsets.

Correction: Standardize on zero-based indexing. When reading problems, map elements to bits consistently. Use helper functions like (mask >> i) & 1 to check inclusion, and test with small n to verify.

1. Incorrect DP state transitions: Misunderstanding how to build larger masks from smaller ones can lead to incomplete or wrong solutions. For instance, in TSP, failing to ensure that the start city is included in the base case might skip valid tours.

Correction: Clearly define the DP state meaning. Sketch transition diagrams on paper. For TSP, ensure the start city is fixed in the mask initially, and transitions add unvisited cities. Validate with sample inputs.

1. Ignoring time and memory limits: With $2^n$ states, memory usage for dp arrays can be high. For n=20, $2^{20}\approx 1$ million states, which is manageable, but for n=25, it exceeds typical limits. Also, $O(2^n\cdot n)$ time might be too slow if not optimized.

Correction: Calculate space and time upfront. Use iterative DP and bitwise operations to keep constants low. For memory, consider using 1D arrays if possible, and avoid unnecessary dimensions.

1. Overlooking problem constraints: Applying bitmask DP to problems where n is too large or where subsets aren't the right state representation. For example, if the problem involves continuous parameters, bitmask DP isn't suitable.

Correction: Analyze the problem statement for subset-based decisions. If n is large (e.g., >25), look for alternative approaches like meet-in-the-middle or approximation algorithms.

Summary

• Bitmask DP uses n-bit integers to represent subsets, enabling efficient iteration over all $2^n$ subsets via bitwise operations.
• It allows dynamic programming over subsets with states like dp[mask], building solutions from smaller to larger masks.
• The Traveling Salesman Problem can be solved in $O(n^2\cdot 2^n)$ time by tracking visited cities and last city in the DP state.
• Assignment problems are tackled by assigning tasks to workers based on subset masks, with complexity $O(n\cdot 2^n)$.
• Use bitmask DP for problems with small n (typically ≤20) where the state involves subset selection, and ensure optimal substructure exists.
• Avoid common mistakes like indexing errors and inefficient transitions by testing with small cases and calculating resource usage.