PROBLEM LINK:
Author: Tasnim Imran Sunny
Tester: Istvan Nagy
Editorialist: Lalit Kundu
DIFFICULTY:
Medium
PREREQUISITES:
dynamic programming, bitmasking
PROBLEM:
Given a sequence A of N integers where each integer lies between 1 and K and an integer L, count number of different sequences B of length N such that longest common subsequence(LCS) of A and B is L.
N, K, L \le 16.
QUICK EXPLANATION:
======================
We define \textrm{DP}(i, \textrm{arr}) as number of ways to add i more integers to array B such that \textrm{arr}[i] denotes LCS of i^{th} prefix of A with current elements in B).
\textrm{DP}(i, \textrm{arr}) = \sum_{j = 1}^{K} \textrm{DP}(i - 1, \textrm{next}(\textrm{arr}, j)), where \textrm{next}(\textrm{arr}, j) returns the new updated \textrm{arr} after adding value j at the end of array B.
We can represent this array \textrm{arr} by a bitmask of N values, where i^{th} bit is set if arr_{i} > arr_{i-1}.
Function \textrm{next(mask, i)} can be precalculated for each pair of \textrm{mask} and value i.
EXPLANATION:
================
While constructing a dynamic programming solution, it is always a good idea to iterate over something (usually the state of dp). Let us say that we are constructing array B from left to right, let us say that we know LCS of A and currently constructed part of B(let us denote it by l). So, now we need to ask ourself about what information we should maintain in the state so that when we put the next elementof array B as x , how can we find new value of l efficiently.
Now, by using only previous l, can we find new value of l? Think about it, it is not possible.
So, if we have two sequences a_1, a_2, ..., a_p and b_1, b_2, ..., b_q and we progressively keep adding values at the end of sequence b, how can we can re-calculate \textrm{LCS}(a, b) quickly? For this, we need to have a proper understanding of how LCS is calculated.
We define \textrm{LCSdp}(i, j) as the LCS of a_1, a_2, ..., a_i and b_1, b_2, ..., a_j. Now,
\textrm{if}(a_i == b_j)\hspace{1mm} \textrm{then}\hspace{1mm} \textrm{LCSdp}(i, j) = \textrm{LCSdp}(i - 1, j - 1) + 1
\textrm{else} \hspace{1mm} \textrm{LCSdp}(i, j) = \textrm{max}(\textrm{LCSdp}(i, j - 1), \textrm{LCSdp}(i - 1, j))
Now assume, we have sequences a_1, a_2, ..., a_p and b_1, b_2, ..., a_q. We add one more value a_{q+1}. How do we re-calculate LCS? We need to maintain some information with us, or else, we’ll have to calculate the whole \textrm{LCSdp} matrix again. If we have with us
\textrm{LCSdp}(1, q), \textrm{LCSdp}(2, q), ..., \textrm{LCSdp}(p, q)
which is nothing but an array of LCS of each prefix of a with whole array b, then we can easily find values
\textrm{LCSdp}(1, q+1), \textrm{LCSdp}(2, q+1), ..., \textrm{LCSdp}(p, q+1)
which denotes LCS of each prefix of a with updated b. How? Think before you read ahead.
If at any position j, a_j == b_{q+1}, then \textrm{LCSdp}(j, q+1) = \textrm{LCSdp}(j - 1, q) + 1
or else, \textrm{LCSdp}(j, q+1) = \textrm{max}(\textrm{LCSdp}(j - 1, q + 1), \textrm{LCSdp}(j, q)).
Note that if we calculate new array from left to right, we’ll have all values available on right hand side.
Now, how does all this help us? We are going to formalise our DP in a way such that at each step, we are going to progressively add more elements to array B. We can directly use the \textrm{LCSdp} array as one of the state parameters of DP.
So, states of our DP are \textrm{number of elements to be added} and \textrm{current LCSdp array}.
We define \textrm{DP}(i, \textrm{arr}) as number of ways to add i more integers where \textrm{arr} contains the current \textrm{LCSdp} array(\textrm{LCSdp}[i] denotes LCS of i^{th} prefix of A with current elements in B). So, how can we define the recurrence of our DP?
At each step, we assume that we add value j at the end of array B. So we traverse over j. \textrm{DP}(i, \textrm{arr}) = \sum_{j = 1}^{K} \textrm{DP}(i - 1, \textrm{next}(\textrm{arr}, j)), where \textrm{next}(\textrm{arr}, j) returns the new updated \textrm{LCSdp} array after adding value j at the end(we already have implemented this function). The base case of this recurrence is when 0 elements are required to be added. In this case, we find the current LCS from the array \textrm{arr} and return 1 if this LCS is equal to L.
If we implement this DP recursively, we also need to memoize these \textrm{LCSdp} arrays, for which we can use a map in C++. Let’s see what is the complexity right now? First, we need to know how many distinct \textrm{LCSdp} arrays can exist. Here comes the interesting property that in this array two consecutive elements can differ by at most 1. So, at each step, there could be a raise or not. So, we can say that 2^N is an upper bound on number of such distinct sequences.
Remember, complexity of a recursive memoized DP is product of different states with transition complexity. So our complexity is N*2^N(different states)*K*N*log_{2}{2^N}(transition). N*K factor in transition because we calculate \textrm{next}(\textrm{arr}, j) in O(N), by adding each of the K values. log_{2}{2^N} is the retrieving cost of a state’s value from the map. Total complexity right now is O(N^3 * K * 2^N), which is quite high, we need to improvise our solution.
How do we reduce the complexity? Let’s try to remove the use of map for memoization, if we remove map then complexity can be reduced by a factor of N. We need to have a compact representation of \textrm{LCSdp} array. Instead of storing whole array, for each of the N positions, we store whether there is an increment or not(remember the property?). So, now each \textrm{LCSdp} array can be represented as a bitmask less than 2^{16}. Hereby goes the factor due to memoization. Current complexity is O(N^2 * K * 2^N). Its still not enough!
One more observation, we can make is that for a certain \textrm{LCSdp} array \textrm{arr}, we can pre-calculate \textrm{next}(\textrm{arr}, i) \forall i \le K.
So, for all possible masks denoting \textrm{LCSdp} arrays, for all possible values from 1 to K, we pre-calculate the next mask. Doing this will take O(2^N*K*N) and complexity of DP will have one more factor of N removed. So overall complexity now will be O(N*K*2^N) which is good enough.
For implementation, see setter’s commented code.