Can anyone explain how is![Sorting with stacks]] solvable with bitmask dp?
[1]: [1]: Programming tutorials, Coding problems, and Practice questions
The first step here is to understand what is going on in the problem. The problem says that we must push all N elements in the array A one by one to any of the K stacks. And then when that is done, we must pop the stacks in any order until all the elements that come out form a sorted array. There is an additional rule that a stack should never contain the same number twice. Without this rule with approach would be almost the same, so you can just keep it at the back of your mind. If you’re familiar with the algorithm for merging two sorted list into one sorted list, you’ll quickly realize that the only way we can pop the stacks to get a sorted array is if all the stacks are each individually sorted. So now you’ll be able to see that the problem wants you find the number of ways to split the array A into at most K strictly increasing subsequences. The problem URL is a bit of a giveaway though 
Now we can apply dynamic programming. The first thing to figure out now is the dp state. Let’s imagine we are at some index i. Now we must add A[i] to one of the K sequences. These K sequences contain all elements from A[0] to A[i-1] in some distribution. We can only add A[i] to a sequence S[j] if A[i] > S[j][last], where S[j][last] is the last element added to the sequence S[j]. This tells us that S[j][last] is the only element of S[j] that we need to be bothered with, so we can just represent each sequence by its last element. Let’s call S[j][last] as L[j]. When we find a suitable sequence to add A[i] to, we can add it to the sequence and hence we are effectively changing the last element of that sequence to A[i]. This will matter for the next state. The function below should make things clear.
function f(i, L):
if i==N return 1 // reached the end
result = 0
for j in range 0 to length of L - 1
if A[i] > L[j]:
new_L = copy of L
new_L[j] = A[i] // adding A[i] to jth sequence, thereby replacing L[j]
result = result + f(i+1, new_L)
if length of L < K // we have less than K sequences,
new_L = copy of L // so we can start a new one with A[i]
add A[i] to new_L
result = result + f(i+1, new_L)
return result
This is the basic idea we will improve on.
First improvement: Instead of passing a collection as L, we can instead use a bitmask that will represent L. This is possible because N is quite less. And of course if we use bitmasks, we cannot store the value of some A[i] itself in the mask, instead we must store the index i. So if A[i] is in L, in the mask the i^{th} bit will be set to 1. Doesn’t really change much, except now all operations on L are now bitwise operations.
Second improvement: The i parameter to the function is redundant and can be removed. That is because we reach index i only after going through all indices 0 to i-1. Although other elements may have been replaced as the last element of the sequence they were put into, since i-1 was the element last added to L, it is guaranteed to be found in L. So the current index i is just 1 plus the highest set bit in the bitmask L.
This is my code after making these improvements, but the time limit is strict so even this doesn’t clear all test cases.
Third improvement: Switch to iterative dp. Since each bit in the mask is getting replaced by some higher bit for the next call, for a bottom up solution we must loop from the highest mask possible to 0. And that’s it! Here is my solution that got AC.
I hope I was able to explain my approach well. This is not strictly the editorial’s approach though, so the usage of the mask, etc, may slightly differ. Overall complexity is \mathcal{O}(n \cdot 2^n). Feel free to ask if something is not clear 
2 Likes
Absolutely perfect!
Thanks a lot!
Sure, the problem was interesting 