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:

- 4,3,5,6,7,1,2 and
- 1,2,3,50,6,4,7

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:

- MAX(LCIS_length(seq1 less it's first element, seq2 less it's first element, first element of seq1)+1,

LCIS_length(seq1 less it's first element, seq2, prev_elem),

LCIS_length(seq1, seq2 less it's first element, prev_elem)).

If the first elements of seq1 and seq2 are the same AND the first element of seq1 is > prev_elem. - MAX(LCIS_length(seq1 less it's first element, seq2, prev_elem),

LCIS_length(seq1, seq2 less it's first element, prev_elem)).

If the first elements of seq1 and seq2 are different.

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.

4 | 3 | 5 | 6 | 7 | 1 | 2 | |

1 | |||||||

2 | |||||||

3 | |||||||

50 | |||||||

6 | |||||||

4 | |||||||

7 |

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).

4 | 3 | 5 | 6 | 7 | 1 | 2 | |

1 | |||||||

2 | |||||||

3 | |||||||

50 | |||||||

6 | |||||||

4 | |||||||

7 |

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.

4 | 3 | 5 | 6 | 7 | 1 | 2 | |

1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

2 | |||||||

3 | |||||||

50 | |||||||

6 | |||||||

4 | |||||||

7 |

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].

4 | 3 | 5 | 6 | 7 | 1 | 2 | |

1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

2 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |

3 | |||||||

50 | |||||||

6 | |||||||

4 | |||||||

7 |

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

4 | 3 | 5 | 6 | 7 | 1 | 2 | |

1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

2 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |

3 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

50 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

6 | 0 | 0 | 0 | 2 | 0 | 0 | 0 |

4 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

7 | 0 | 0 | 0 | 0 | 3 | 0 | 0 |

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.

4 | 3 | 5 | 6 | 7 | 1 | 2 | |

1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

2 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |

3 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

50 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

6 | 0 | 0 | 0 | 2 | 0 | 0 | 0 |

4 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

7 | 0 | 0 | 0 | 0 | 3 | 0 | 0 |

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

4 | 3 | 5 | 6 | 7 | 1 | 2 | |

1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

2 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |

3 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

50 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

6 | 0 | 0 | 0 | 2 | 0 | 0 | 0 |

4 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

7 | 0 | 0 | 0 | 0 | 3 | 0 | 0 |

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^{4}). 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^{3}) 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^{2}).

Re-constructing the LCIS can be trivially accomplished in time O(n) if we use extra space to the order of O(n^{2}) 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

- Here’s why there was a delay in updating the March contests’ ratings
- SnackDown 2017 is here and this time it is truly Open!
- A Star Studded Rating System
- New Goodies, New Categories & New Prizes Every Contest
- CodeChef’s 8, mate!

- About (12)
- ACM ICPC (20)
- Announcement (284)
- Campus Chapters (7)
- College Contests (9)
- Contests (264)
- Events (50)
- FAQ (1)
- Features (49)
- Interviews (18)
- Languages (1)
- Meetup (4)
- Open Source (1)
- Practice Problems (8)
- Prizes (20)
- Problems (6)
- ProblemSetting (1)
- Programmer of the Month (34)
- Schools (9)
- Tech Talks (23)
- Tutorials (25)
- Uncategorized (1)
- Volunteers (2)
- Winners (119)

- abhinav vinci on The new Karma system
- Ashu on A Star Studded Rating System
- Hemant Mangla on New Goodies, New Categories & New Prizes Every Contest
- Protap Ghose on New Goodies, New Categories & New Prizes Every Contest
- Shivam Fialok on New Goodies, New Categories & New Prizes Every Contest

- March 2017
- February 2017
- January 2017
- December 2016
- November 2016
- October 2016
- September 2016
- August 2016
- July 2016
- June 2016
- May 2016
- April 2016
- March 2016
- February 2016
- January 2016
- December 2015
- November 2015
- October 2015
- September 2015
- August 2015
- July 2015
- June 2015
- May 2015
- April 2015
- March 2015
- February 2015
- January 2015
- December 2014
- November 2014
- September 2014
- August 2014
- July 2014
- June 2014
- May 2014
- April 2014
- March 2014
- January 2014
- December 2013
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013
- May 2013
- April 2013
- March 2013
- February 2013
- January 2013
- December 2012
- October 2012
- September 2012
- August 2012
- July 2012
- June 2012
- May 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- August 2011
- July 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009

© 2009, Directi Group. All Rights Reserved.