You are not logged in. Please login at www.codechef.com to post your questions!

×

LAEDDIS - Editorial

PROBLEM LINK:

Practice Link
Contest Link

Author: Ankush Khanna

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic Programming, Binary Search, Longest Increasing Sub-Sequence

PROBLEM:

Given an array $A$ of size $N$ containing integers, find the longest increasing sub-sequence (LIS) of $A$.

QUICK EXPLANATION:

Key to AC: Use binary search based dynamic programming algorithm (Patience Sort based) to find LIS of an array.

EXPLANATION:

This is rather a very direct implementation problem. Though it involves Dynamic Programming, but this is readily available to be solved. It was just the language of the problem and problem statement framing that kept it somewhat hidden.

There are two versions of finding the size of LIS in a sequence. The first one is plain dynamic programming solution that works in $O(N^2)$ time with $O(N)$ auxiliary space. And the second one works in $O(N \log_2 N)$ time with $O(N)$ auxiliary space.

Sub-Task 1

Suppose $length[k]$ denotes the length of the LIS that ends at position $k$. $\therefore \space length[N - 1]$ (0-based indexing) will give us the length of the LIS in the given sequence.

for (int k = 0; k < N; k++) {
    length[k] = 1;
    for (int i = 0; i < k; i++) {
        if (A[i] < A[k]) {
            length[k] = max(length[k], length[i] + 1);
        }
    }
}

This C++ code runs in $O(N^2)$ time, which would suffice our constraints for sub-task 1, awarding us with 30 points. Just basic Dynamic Programming!

Sub-Task 2

For this sub-task, we must go below $O(N^2)$ time, and luckily we have binary search based dynamic programming algorithm for LIS which uses patience sort like structure (here) which works in $O(N \log_2 N)$ time due to binary search. Detailed explanation about LIS algorithms can be found in the links provided in this editorial.

COMPLEXITY:

$O(N \log_2 N)$ time and $O(N)$ auxiliary space.

SOLUTION:

Setter's Solution

Feel free to share your approach. If you have any queries, they are always welcome.

This question is marked "community wiki".

asked 06 Feb, 03:12

ankushkhanna's gravatar image

4★ankushkhanna
53
accept rate: 33%

edited 12 Feb, 19:59

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,678
×3,763
×2,169
×1,038
×790
×52
×14
×14

question asked: 06 Feb, 03:12

question was seen: 102 times

last updated: 12 Feb, 19:59