All submissions for this problem are available.
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.
A and B are two sequences of numbers( having same length let say X ) then A > B
if there exist a i ( 1 <= i <= X ) such that Ai > Bi and for all j < i ( Ai = Bi ).
- The first line of the input contains T the next T line contains the T[i]th number. The last line contains N and Q.
- Print the subsequence.
for q > 1 first print the largest and then print the smallest in next line.
- 1 ≤ T ≤ 10000
- 1 < N < T
- -300 ≤ T[i] ≤ 300
Input: 3 1 2 3 2 2 Output: 2 3 1 2
Example case 1.
since 2 3 is greater than 1 2
and q = 2
|Tags||dynamic-programming, f2012086, icl2015, medium-hard|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.