### 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 extrm{DP}(i, extrm{arr}) as number of ways to add i more integers to array B such that extrm{arr}* denotes LCS of i^{th} prefix of A with current elements in B).

extrm{DP}(i, extrm{arr}) = \sum_{j = 1}^{K} extrm{DP}(i - 1, extrm{next}( extrm{arr}, j)), where extrm{next}( extrm{arr}, j) returns the new updated extrm{arr} after adding value j at the end of array B.

We can represent this array extrm{arr} by a bitmask of N values, where i^{th} bit is set if arr_{i} > arr_{i-1}.

Function extrm{next(mask, i)} can be precalculated for each pair of extrm{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 extrm{LCS}(a, b) quickly? For this, we need to have a proper understanding of how LCS is calculated.

We define extrm{LCSdp}(i, j) as the LCS of a_1, a_2, ..., a_i and b_1, b_2, ..., a_j. Now,

extrm{if}(a_i == b_j)\hspace{1mm} extrm{then}\hspace{1mm} extrm{LCSdp}(i, j) = extrm{LCSdp}(i - 1, j - 1) + 1

extrm{else} \hspace{1mm} extrm{LCSdp}(i, j) = extrm{max}( extrm{LCSdp}(i, j - 1), extrm{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 extrm{LCSdp} matrix again. If we have with us

extrm{LCSdp}(1, q), extrm{LCSdp}(2, q), ..., extrm{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

extrm{LCSdp}(1, q+1), extrm{LCSdp}(2, q+1), ..., extrm{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 extrm{LCSdp}(j, q+1) = extrm{LCSdp}(j - 1, q) + 1

or else, extrm{LCSdp}(j, q+1) = extrm{max}( extrm{LCSdp}(j - 1, q + 1), extrm{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 extrm{LCSdp} array as one of the state parameters of DP.

So, states of our DP are extrm{number of elements to be added} and extrm{current LCSdp array}.

We define extrm{DP}(i, extrm{arr}) as number of ways to add i more integers where extrm{arr} contains the current extrm{LCSdp} array( extrm{LCSdp}* 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. extrm{DP}(i, extrm{arr}) = \sum_{j = 1}^{K} extrm{DP}(i - 1, extrm{next}( extrm{arr}, j)), where extrm{next}( extrm{arr}, j) returns the new updated extrm{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 extrm{arr} and return 1 if this LCS is equal to L.

If we implement this DP recursively, we also need to memoize these extrm{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 extrm{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 extrm{next}( extrm{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 extrm{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 extrm{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 extrm{LCSdp} array extrm{arr}, we can pre-calculate extrm{next}( extrm{arr}, i) \forall i \le K.

So, for all possible masks denoting extrm{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.