DS & Algo Problems — Bitmasking and DP

In this post we are going to look at one of the ‘simplest’ Dynamic Programming variation — Bitmasking. When I say ‘simplest’ I mean that ‘Bitmasking + DP’ problems are easy to identify and also most bit-masking problems have a more or less similar approach.

Some of the common traits of Bitmasking problems are:

1. Path finding problems — Enumerate all possible paths or paths based on certain conditions.
2. For a given input array A, depending in which order we go through the elements of the array A our objective function will change.
3. They require exponential runtime.
4. For folks into competitive programming will understand that problems with constraint on N (≤ 20) (i.e. size of array) hints towards bitmasking + DP.

I will not go into the details of bit-manipulation (which will be a topic of discussion later). For understanding bit-manipulation operations, I would refer to this stackoverflow forum.

https://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit

We will look at 5 problems to understand why these needs Bitmasking + DP approach to solve.

Problem 1

There is a new food delivery startup in town. For simplicity, assume that there are N delivery executives and N orders. Also we have estimated how much it would cost the startup if delivery executive ‘i’ delivers the order ‘j’. This considers all factors such as distance, traffic, customer priority, food value etc.

Given a NxN cost matrix, we need to assign each order to an executive in such a way that the total cost to the startup is minimum.

Note that each order is to be allotted to a single executive, and each executive will be allotted only one order.

The brute force approach can be solved using recursion:

The run-time complexity is O(N!) (1st person there are N choices, for each choice the 1st person makes, 2nd person can make N-1 choices and so on).

We can do better than this by realising that when we have assigned tasks to the first i persons, the cost of assignment of the remaining tasks to the remaining persons is independent of the task assignments made to the first ‘i’ persons. Thus we can cache the results.

We can use a bit-vector of size N, to hold the assigned tasks. Then we can use a cache. For e.g. if N=5, then assigned = [1,0,1,1,0], implies that tasks 0, 2 and 3 has been assigned to the first 3 persons.

The modified code is as follows:

The run-time of the above code is O(N*2^N).

Overall space complexity is O(N*2^N), due to the in-memory ‘cache’ variable. Each key is of length N and there are 2^N possible keys.

We can avoid the bit vector by using bit-operations. Since the binary representation of the bit vector denotes a decimal integer, we can alternatively use an integer for ‘assigned’ variable. Setting and un-setting of bits of the integer can be done using bit-wise operators.

For e.g. if N=5, then assigned = 13, implies that tasks 0, 2 and 3 has been assigned because the binary representation for integer 13 is ‘01101’.

Note that we have reversed the order of bits in this notation because it is easier to work with bit manipulation starting from the right end. Thus 0-th bit is set implies that the last bit is set and so on.

(https://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit)

The same code when written using bitwise operators:

The space complexity is now O(2^N).

‘(k & 1<<j)’ returns 0 if j-th bit is not set in integer k else non-zero. (j is 0-indexed)

To set the j-th bit of an integer k do ‘k |= (1 << j)’ and to unset do ‘k &= ~(1 << j)’

The properties of the problem, if we observe carefully, satisfy all the Bitmasking problem traits:

1. Depending in which order we assign the ‘orders’ to the executives, the overall cost will change.
2. Since we need to evaluate all possible ordering of ‘orders’, the total number of orderings is N!. Thus require exponential runtime.

We can also define a non-recursive solution as follows:

f[k] denotes the minimum cost of assigning a subset of M tasks (represented by the integer ‘k’) to the first n persons (where n = number of bits set in k).

For an 8x8 cost matrix, the average time taken by the 1st approach (non-cached) is 0.11 seconds whereas average time taken by the last approach is 0.00083 seconds.

Problem 2

You are given a list A of N integers. Here, N is an even number. These integers must be distributed into N/2 pairs and the power of each of the pairs is added.

The power of a pair P(i, j) consisting of the i-th and j-th number is defined as bitwise XOR of the two numbers A[i] and A[j], that is A[i] ^ A[j] where 1 < i < N, 1 < j < N and i != j.

Write a program to determine the minimum and the maximum possible sum of the N/2 pairs.

Again this problem has the following characteristics:

1. Assuming that the array A is the list of N integers, we need to assign each integer to only a single pair.
2. Depending in which order we assign the integers to the pairs, the total sum would change.
3. We need to evaluate all possible pairings. The number of possible pairings is N!/((N/2)!*2^(N/2)). Which is still exponential in N.

Brute force solution is to go through all possible assignment of integers to the pairs which can be easily accomplished using recursion. But will skip that as it is trivial.

Below is the Python solution with bitmasking and DP:

As before we let the assigned integers be represented using N bits. Thus the assigned integers can be represented using another integer between 0 and 2^N-1.

For e.g. if the array is [1,2,3,4,5,6], then the assignment ‘101011’=43 implies that the numbers at indices 0, 1, 3 and 5 has been assigned (indexing starts from end) and they are part of 2 groups:

The 2 groups can be (1,2)(4,6) or (1,4)(2,6) or (1,6)(2,4).

Each time pick 2 integers from the set bits, and using DP find the minimum of the remaining bits and add the XOR of the 2 integers. Note that we must only pick integers when the number of assigned bits is even.

Time complexity of the above approach is O(N²*2^N). Space complexity is O(2^N).

Problem 3

There are n people and 40 types of hats labeled from 1 to 40.

Given a list of list of integers hats, where hats[i] is a list of all hats preferred by the i-th person.

Return the number of ways that the n people wear different hats to each other.

This is similar to the order assignment problem, only difference is that the number of executives may not be equal to the number of orders (which is more realistic). Also the problem asks for number of ways of assignment instead of finding minimum cost.

The problem satisfies the following traits:

1. If we assume that the array A is the list of people then we must assign a single hat to each people depending on their preferences.
2. Depending on which hat is assigned to which people, we would have different number of ways of assigning hats.
3. Total number of assignments is exponential in N (number of people). Then the number of possibilities is approximately ‘M chooses N’ where M is the number of hats.
4. For a subset of K people, the number of ways of assigning hats numbered 1 to H can be found by assuming that the i-th person selects the H-th hat (if he has in its preference) and the remaining K-1 people selects from hats numbered 1 to H-1.

The problem can be solved using recursion. But that would be trivial.

Instead we show a python solution using bitmasking + DP approach:

f[k][h] — denotes the number of ways of assigning hats numbered 1 to h to the set of people represented by the integer ‘k’.

Thus if N=5, k=13 and h=8, then the binary representation for 13 = ‘01101’, denotes that hats 1 to 8 has been distributed to the 0-th, 3-rd and 4-th people.

f[k][h] can be computed by finding the people whose preferences has the h-th hat then using DP adding the number of ways f[k & ~(1<<i)][h-1] i.e. number of ways of assigning hats 1 to h-1 to all people except the i-th person.

Problem 4

Hamiltonian Path is a path in a directed or undirected graph that visits each vertex exactly once. Given an undirected graph, check whether it contains a Hamiltonian Path or not.

This looks like a simple case of depth first search. But with DFS we need to traverse all possible paths and then check if at-least one path has all the N vertices. Alternatively we can list all possible permutations of the vertices and check if there is any permutation where all adjacent vertices has an edge between them.

Complexity of above is O(N!) because we need to traverse all possible paths.

The problem has the following properties:

1. We need to visit all vertices exactly once.
2. Number of vertices covered depends on the order in which we visit them due to the adjacency matrix.
3. Total number possible paths is O(N!) which is exponential in N.
4. There exists a Hamiltonian path of K vertices if there is a vertex i such that if j is the end vertex of a Hamiltonian path of the remaining K-1 vertices (excluding i) then there is an edge between i and j.

Which makes bitmasking + DP as a potential approach for solving this problem.

The bitmasking + DP python solution is as follows:

Let f[k][i] = ‘True’ if there is a Hamiltonian path with the vertices represented by the bit vector ‘k’ ending with vertex i else ‘False’.

We encode the vertices using bits. Then for a set of assigned vertices, we select a vertex i and then for each end vertex j, f[k][i] is True only if f[k & ~(1 <<i)][j] (assigned vertices excluding i, ending with vertex j) is True and there is an edge between i and j.

Time complexity of the above is O(N²*2^N) and space complexity is O(N*2^N).

Problem 5

You are given a bunch of sticks. For each stick, its two ends are labelled with two numbers (1–6, possibly same).

You can connect two stick A and B, if and only if one of numbers of stick A is the same as one of the numbers of stick B. For example, a stick with [1,5] can be connected with a stick with [1,4] by connecting the two ends labelled as 1. In this case, these two sticks will become one with longer length, and its two ends now becomes [4,5]. Assume for each given stick, its length is 1.

Return the length of longest stick that can be formed using the given sticks.

The problem is similar to the Hamiltonian path problem seen above as in we need to do DFS to find the solution, only difference is that instead of finding a Hamiltonian path, we need to find the longest path.

This can be done in brute force way by recursion (DFS) but that would not be interesting enough !!! By now we must have got the clue how this problem can be solved using bitmasking and DP.

Below is the python code:

f[k][i][0] = max length stick formed with sticks represented by integer k ending with the i-th stick.

f[k][i][1] = number on the end-face of the final stick.

The recursive relation and the remaining code is quite self explanatory if you have followed the earlier problems carefully. As with the Hamiltonian path problem, time complexity is again O(N²*2^N).

This ends our discussion on Bitmasking + DP. This is one of the few common DP strategies asked quite frequently in online competitive programming and online programming assessments.