EngineerPro - K01
DP & Bitmask
Trần Khánh Hiệp, 2023.
1
[EngineerPro] DP & Bitmask
1. Why using DP with Bitmask?
Contents 2. Examples
3. Homework
2
1. Why using DP with
Bitmask?
3
[EngineerPro] DP & Bitmask
- Recall: DP needs states
- Bitmasks can be used to represent subsets
- When a DP problem needs subsets as states, bitmasks come in handy
- Finding “best” subset
- TSP
- Finding “best” subsequence
4
2. Examples
5
[EngineerPro] DP & Bitmask
- Shortest Path Visiting All Nodes (TSP)
- Naive Solution: backtracking
- Observation 1: In the backtracking solution, we have to store all visited nodes. That can be represented as
a bitmask.
- Observation 2: In the backtracking solution, we always have to keep track of the last visited node to know
the distance to the next one. It’s similar here.
=> DP state: dp[visited][last]
- Observation 3: Given a state (visited, last), we can try every node to move next.
- new_visited = visited | (1 << next)
- cost(last, next) = ? => Floyd-Warshall algorithm
=> O(2^n * n^2) solution.
6
[EngineerPro] DP & Bitmask
- Smallest Sufficient Team (Set Cover Problem)
- Observation 1: This is an NP-hard problem. But set of skills is small.
=> Possible to iterate through all subsets of skills.
- Observation 2: Let dp[mask] be the min no. people to get skills mask, we can try to add more people to
improve the mask: new_mask = mask | people[i]. The result is f[(1 << len(skills)) - 1].
=> O(2^n * m) solution.
7
[EngineerPro] DP & Bitmask
- Maximize Score After N Operations
- Observation 1: We need to keep track of used numbers.
=> Use bitmask.
- Observation 2: From the bitmask, we know how many numbers are used, hence, how many operations
have been done: current turn = mask.bit_count() / 2 + 1
- Observation 3: Let dp[mask] be the max score after the set of numbers in mask is used.
After using two numbers nums[u] and nums[v], the new mask is:
mask2 = mask | (1 << u) | (1 << v)
=> dp[mask] = max(dp[mask2] + current_turn * gcd(nums[u], nums[v]))
8
[EngineerPro] DP & Bitmask
- Minimum Cost to Connect Two Groups of Points
- Observation 1: Using bitmasks to keep track of remaining numbers in both groups is expensive, but one
group is possible.
- Observation 2: We can match each number in the 1st group one by one, while using a bitmask to keep
track of the remaining numbers in group 2.
- Observation 3: Let dp[i][mask] be the min cost when all numbers from 0…i-1 in group 1 and all numbers in
mask from group 2 have been matched.
- We can match number i in group 1 with any number j in group 2 with cost[i][j] and the new mask
becomes mask | (1 << j).
- If we’re done matching for number i, the new state is: (i + 1, newmask).
- If we want to match number i to more numbers in group 2, the new state is: (i, newmask).
9
3. Homework
10
[EngineerPro] DP & Bitmask
- Number of Squareful Arrays
- Find the Shortest Superstring
- Parallel Courses II
- Maximum Students Taking Exam
11
