PROBLEM LINK:
Contest link: ICLFIN04
Author
Jaiwant Rawat
Tester
Editorialist
Jaiwant Rawat
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
LIS (Longest Increasing Subsequence)
PROBLEM:
PK is stuck on earth. In order to return to his planet he has to solve a problem by selecting N numbers from a set of T numbers and arrange them in a special pattern.
The pattern is such that the N numbers selected are in order i.e. they must be one of the subsequence of the given numbers. Also the N numbers selected should be in increasing order.
To make the situation a bit tougher for him the “BABA” gives PK q also.
If q is 0 then the N numbers should be the largest subsequence among all such possible subsequences. ( Definition of largest subsequence given in note).
If q is 1 then the N numbers should be the smallest subsequence among all such possible subsequences.
If q is greater than 1, first find N numbers which forms the largest subsequence and then find the N numbers which forms the smallest subsequence.
If he is not able to find subsequence of length ‘N’ then he has to do the above process for subsequence whose length is maximum.
PK could not solve the problem so he comes to you to help him solve the problem.
EXPLANATION:
There are just two steps in this problem.
Step1:-
- Finding the Lis to see if such a subsequence exist for a length L else find the answer corresponding to the subsequence of maximum length .
Also store at each position i the maximum subsequence length till that point .
Step2:-
- Now use the information stored in the array created in step1 to find the desired answer.