SEQLCS - Editorial

PROBLEM LINK:

Practice
Contest

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.

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

7 Likes

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 element x of array B, we can find new value of L efficiently.

Now, by using only prev L, can we find new value of L only using that. Think about it, It is not possible. We need to somehow maintain LCS[\text{all prefixes of }A][\text{constructed part of } B] up to now. Now if we directly use the lcs array as one of the state parameters of dp, then this parameter can have total n^n values as it’s each element can be from 1 to n. This is too much for us to afford. We need to somehow optimize this. But, if we think slightly more, we can store the LCS array smartly by using the following idea. Let us say that we know LCS[1..i]**, then LCS[1,i+1] can be either same as LCS[1..i]** or can be 1 more than LCS[1..i]**. So, we will just store the positions where LCS value gets incremented by 1. This can be stored using a bitmask. So, now our dp state will be dp[i][mask][lcs]. Transitions are not that hard to find.

2 Likes

4th para in explanation.
We define LCSdp(i,j) as the LCS of a1,a2,…,ai and b1,b2,…,aj.
It should be bj instead of aj, I believe.
Same typo in 5th para also.

What is newMask[i][j] in setter’s code?

Cant Understand can someone help.

Editorial is tough can someone explain in simple manner

I am struggling with understanding the solution for the past few hours. I find the editorial to be confusingly written and I really can’t wrap my head around it…

Could somebody try and explain it somehow more… concisely?
I understand how to use DP to obtain LCS of two sequences and how bitmask works.

In fourth last paragraph
“Here comes the interesting property that in this array two consecutive elements can differ by at most 1”.
Can anyone explain why consecutive elements will differ by at most 1?

In my understanding, it is because when you look at LCSdp(x+1,q) and LCSdp(x,q), then as you add at most 1 element, the LCS length changes at most by one.

1 Like