In the May Challenge we posed a question about computing the Longest Common Increasing Subsequence (LCIS) of 2 given sequences. What does LCIS mean? Given 2 sequences of integers, we need to find a longest sub-sequence which is common to both the sequences, and the numbers of such a sub-sequence are in strictly increasing order.

So for example, given the 2 sequences:

Possible common increasing sub-sequence of the 2 sequences above are:

(4), (3), (7), (6), (1), (2), (1,2), (3,6), (3,7), (6,7), (4,7) and (3,6,7).

The LCIS of the 2 sequences would be (3,6,7). It so happens that the 2 sequences above have a unique LCIS, though that may not always be the case.

Now, how do we go about computing the LCIS of 2 sequences in a reasonable amount of time? If we think a bit, we can come up with the recurrence:

LCIS_length(seq1, seq2, prev_elem) is equal to:

Now, if we implement it just the way it is, it is going to be quite expensive to compute the LCIS_length for any sequence having a length of more than say 20 elements. So, we want to use an approach which would work for larger input. On further thinking, we think that a faster(polynomial time) approach is possible.

Let’s lay out both the sequences along the first row and column of an nXm matrix, where n and m are the lengths of the 2 sequences given.

Let’s define each cell to hold the length of the LCIS ending at the row(or column) that that cell is defining. For example, cell [6,1] will hold the length of the LCIS that ends with the number 4. The cell [5,2] will not hold any meaningful value since there can be no sub-sequence that ends with both 6 and 3. Similarly, the cell [7,5] will hold the length of an LCIS that ends with the number 7.

What we will do is we run 2 for loops, one for the row and one for the column, and each time we find a match between an element in the top row and the left column(i.e. The input elements), we will try and find some sub-sequence computed till now that can be extended by the number that that cell represents.

It should be clear by now that the number that the cell [x,y] represents is the number in the first column in the row ‘x’ OR the number in the first row in column ‘y’ ONLY IF both these numbers are the same. For example, the cell [2,3] can NOT represent any number, whereas the cell [3,2] represents the number 3.

A sub-sequence that can be extended by a number in cell [x,y] will always lie in the matrix of which the cell [x-1,y-1] is the right-bottom most cell. Let is refer to such a matrix as the candidate matrix for cell [x,y]. For example, we have highlighted all the cells which can have potential candidate sub-sequences that can be extended by the cell [5,4](which represents the number 6).

Let’s start working out a solution row-by-row.

We need to remember that while processing the 1^st row, there is NO sub-sequence that can be extended by any sub-sequence that ends with a number in the first row! This would be the situation after we finished processing the first row.

When processing further rows, we check the candidate matrix of each cell being processed, and always extend the LCIS in the candidate matrix that ends with a number less than the representative number of the cell being processed.

When processing the 2^nd row, we notice that a sub-sequence ending at 2 can extend a subsequence ending at 1 because that sub-sequence is the LCIS that ends with a number less than 2 and lies in the candidate matrix for the cell [2,7].

Similarly, after processing all the rows, our matrix looks like this.

To find the LCIS, we search for the largest number in the matrix, and that gives you the length of the LCIS and also the number at which such an LCIS ends. To trace the LCIS, we need to find the largest number that lies in the candidate matrix of the cell to which this largest number belongs. In the figure below, the cell and candidate matrix have been highlighted in green and yellow colours respectively.

Tracing thus, we land up with 3 cells(marked in green).

The LCIS is just the numbers represented by the cells marked in green, when taken in increasing order of their value. i.e. (3,6,7).

The complexity of the approach presented above is O(n⁴). Can we bring it down?

If you notice, you will see that for each index representing numbers in the top most row, there is a unique integer associated with it. For example, indexes 1,2,3,4 are associated with numbers 4,3,5,6. There is always one integer associated with every such index. If we think a bit, it should be clear that whenever a CIS ends at some such index, and another longer CIS also ends at that index, then it is sufficient to just keep the larger of the 2. This is because the way in which we are processing the input(row-wise) allows us to track just the LCIS ending at any index.

If we adopt such an approach and use an auxiliary array to hold the LCIS ending at every such index, we land up with an O(n³) solution since we now need to scan just a single array for every element instead of an entire matrix.

However, if we think a little bit more, we can see that we don’t even need that scan, since we can always maintain(for every row scanned), a single variable holding the length of the LCIS that the number(N) in the first column of that row can extend. Whenever we encounter a cell which has the same representative number(N), we store a number one more than an LCIS that can be extended by this representative number of such a cell. This brings down the complexity further to O(n²).

Re-constructing the LCIS can be trivially accomplished in time O(n) if we use extra space to the order of O(n²) and this is left as an exercise for the reader.

Alphonso Mangoes,

Congratulations to everyone who participated in the May Challenge. This contest saw a lot of lead changes in the final two days with 5-6 people fighting for the top spot. When the dust settled we were left with the following winners:

1. Varun – D.J. Sanghvi (Mumbai)
2. Anshuman – IIIT Hyderabad
3. Ajay – IIIT Hyderabad

All solutions are now available (click on the contest problem -> all submissions -> view solution). You can try resubmitting solutions for problems in the practice arena. Test cases for May ’09 contest can be downloaded here.

A friendly reminder, this Friday we are starting our first ever CodeChef Gamer’s Challenge. Develop your own client-side browser game to win awesome prizes.

As always, if you have idea on how to make CodeChef better, please let us know.

Cheers,
The Chef