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

×

M71LIS- Editorial

PROBLEM LINK :

Practice
Contest

Author: manjunath1996
Tester: nmalviya1929
Editorialist: manjunath1996

DIFFICULTY:

MEDIUM

PREREQUISITES:

DP,LIS

PROBLEM:

Given an array of N elements and Q queries.Each query consist of and index of array.You have to find length of Longest Increasing Subsequence consisting of element at that index.

EXPLANATION:

You have to find LIS consisting of element at given index.One brute force approach will be calculating LIS for each query as follows.
for all i from 0 to N-1
    LIS(i)=1;
    if(i > query_index)
        for all index from query_index to i-1 
            if( a(i)> a(j) )
               LIS(i)=max(LIS(i),LIS(j)+1);
    else
           for all index from 0 to i-1
            if( a(i)> a(j) )
                LIS(i)=max(LIS(i),LIS(j)+1);
The complexity of this code is O(Q*N^2) as each time LIS calculation takes O(N^2) time. It will give TLE given q=10^5 queries and 10^3 array length.

So,one observation we can make is, LIS(i) consist of length of LIS which contains element of that index i.So,We can find Longest Increasing subsequence from left as well as Longest Decreasing Subsequence from right. Now,at every index i,We have LIS(i) which is Longest Increasing Subsequence of subarray [0...i] which consist of element at index i. Also,We have LDS(i) which actually is LIS of subarray[i..n] which contains element at index i. So,To find LIS of whole array which consist of element at index i, we can easily answer it as LIS(i)+LDS(i)-1. The running time is O(N^2 + Q).It will easily pass in time limit.Also,there is better approach to find LIS in O(NlogN).So, we can also solve this problem in O(NlogN + Q).

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found Link

Tester's solution can be found Link

asked 26 Aug '17, 12:29

manjunath1996's gravatar image

4★manjunath1996
1287
accept rate: 8%

edited 26 Aug '17, 13:46

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:

×2,172
×52
×14

question asked: 26 Aug '17, 12:29

question was seen: 180 times

last updated: 26 Aug '17, 13:46