Bit-Masking + DP
This is the 2nd part of my 2-part Bit-Masking Series. In this article I’ll be sharing how bit-masking can be used along with Dynamic Programming to optimize many problems.
By going through two problems I’ll try to share how bit-magic can be used over wide range of problems.
Pre-requsites :
· Should have a thorough knowledge about bits and how bit-magic works.
· Good command over recursion.
Feel free to go through my first article (bit.ly/Aman_Bitmask1) is you want to brush up Bit-mask concepts.
Onto the article!!
Dynamic Programming is a technique which reduces the complexity of a program by removing the computation time of over-lapping sub problems. It basically memorizes every state it underwent and try to compute further results using that.
No, it’s not like reinforcement learning in ML :)
Let’s start off with well known problem, Traveling Salesman Problem.
Q. You have n nodes and each node is connected to some other nodes. Traveler wants to visit all the nodes such that the distance he covers is minimum. Find the distance which traveler has to cover.
Sol :
This problem can be simply boiled down to the fact that we need to find the minimum weight Hamiltonian cycle in the given graph.
Naïve approach to the problem could be to compute all possible permutations of the nodes using depth-first-search and compute distances among them. Clearly it’s time complexity will be no less than O((n-1)!).
So how can we optimize this ?
I’ll be using a similar approach that I used in my previous article to compute different combinations.
Let’s suppose we have 4 nodes : A,B,C,D
Since every node has to be visited at least once, therefore for simplicity let’s take A as our source node and then traverse all other node.
Unlike graphs, we don’t require Boolean array to store which nodes we’ve visited so far. Bit-magic will automatically do this for us :)
For the current example since we have 4 nodes, so our mask at any point of time will be of the form MMMM, where each ‘M’ can either be 0 or 1 depending upon if the node has already been visited or not. Mask = 0000 means none of the node has been visited till now and mask = 1111 means that we have visited all the nodes.
Things that we should note over here is mask = 1111 also forms the base case for out recursion problem.
In the base case we’ve to return the cost to go back to the source node from the node that we visits last.
From the above discussion it should be clear that [mask][position] forms the unique DP state for the given problem.
Mask denotes the set of nodes that we have visited so far, and position tells the current node we are standing on.
Note : While approaching any problem using DP, first try to think what could be the possible unique state.
Since mask can take only 2^n unique values and total nodes = n, and we’ll make use of memoization too, so time complexity of this solutions reduces to O((2^n)*n).
Let’s go through the implementation part to get better grip over it.
Hope this would have helped to understand the concept of how bit-masking can reduce the complexity drastically.
Let’s discuss one more problem to get more insights.
Q. Given a number n permute this number n (permute all digits in number n) . Permuted numbers should have same number of digits in them. Given a number m(1<=m<=100), find the number of permutations divisible by m.
Sol :
While approaching this problem we need to realize two facts, first the number can have repeated digits (like 331) and secondly number should not have any leading zeros in it (since it is mentioned that number should have exactly same number of digits).
So taking [ pos ][ mask ] can turn out to be wrong over here. Reason simply being it will consider both 3’s as different ( in case of 331) and our ans will be more than actual ans because it will count the same number twice.
So here, we need to additionally store modulo also. If we have repeated digits, then we’ll only to taking those which comes first. If number is 52442. And mask is [10000] then we can jump to a mask [11000] or [10100]. We cannot jump onto [10010] or [10001].
pos basicaly tells the position at which new digit is inserted, and mask also store the number of digits which is equal to the number of set bits. So, we need not take pos into account as we did in above problem.
So our final solutions looks something like this:
For any position we need to consider all possible values that can come and take their first occurrence only. Also if our number has not been started yet, then we cannot consider 0 over there.
In every iteration we’ll be forming a smaller number and when all the bits of mask gets set, then number gets completed. This forms our base case and here when all the bits are set, we need to check if mod that we’ve been computing is zero or not. If mod comes out to be 0, then actually our permuted number is divisible by M, otherwise not.
Note : We just need to count the number of permutations, not print them all.
Let’s walk through the code to make it clearer.
Hope by going through these problems, by now you must have developed a basic understanding of useful Bit-Magic can be proved both in terms of implementation and optimization.
Below are some links to practice questions related to similar concept:
https://codeforces.com/problemset/problem/1169/E
https://www.codechef.com/JAN15/problems/SEALCM
Link to my previous article :
https://medium.com/analytics-vidhya/bits-bitmasking-62277789f6f5
Happy Coding : )
