Non-Decreasing Subsequence of size K solution codechef

You are given a positive integer KK and an array AA consisting of NN non-negative integers. Find the lexicographically smallest sequence BB that satisfies the following conditions

  • We can obtain BB by rearranging the elements in AA.
  • The length of longest non-decreasing subsequence of BB is equal to KK.

If no such sequence exists, print 1−1.

Non-Decreasing Subsequence of size K solution codechef – Input Format

 

November Cook-Off 2021 Division 3 - CodeChef

  • First line of the input contains TT, the number of testcases. Then the testcases follow.
  • First line of each test case contains two space separated integers NN and KK.
  • Second line of each test case contains NN space separated integers describing the array AA.

Output Format

For each test case, output the array BB in a single line with a space between two consecutive elements. And output 1−1 if no such array BB exists.

Constraints

  • 1T2001≤T≤200
  • 1N2001≤N≤200
  • 1KN1≤K≤N
  • 1AiN1≤Ai≤N
  • Sum of NN over all test cases doesn’t exceed 200200.

Non-Decreasing Subsequence of size K solution codechef

4
3 1
2 1 3
3 2
2 1 3
3 3
2 1 3
3 1
2 2 3

Sample Output 1 

3 2 1
1 3 2
1 2 3
-1

Explanation

There are 66 arrays that are rearrangements of the array [2,1,3][2,1,3].

  • [1,2,3][1,2,3] with length of longest non-decreasing subsequence equal to 33.
  • [1,3,2][1,3,2] with length of longest non-decreasing subsequence equal to 22.
  • [2,1,3][2,1,3] with length of longest non-decreasing subsequence equal to 22.
  • [2,3,1][2,3,1] with length of longest non-decreasing subsequence equal to 22.
  • [3,1,2][3,1,2] with length of longest non-decreasing subsequence equal to 22.
  • [3,2,1][3,2,1] with length of longest non-decreasing subsequence equal to 11.

Test case 1: Non-Decreasing Subsequence of size K solution codechef

Observe from the list above that [3,2,1][3,2,1] is the only rearrangement of [2,1,3][2,1,3] with the length of the longest non-decreasing subsequence equal to 33. And hence [3,2,1][3,2,1] is the lexicographically smallest that satisfies the given conditions.

Test case 2: Non-Decreasing Subsequence of size K solution codechef

Observe from the above list the [1,3,2][1,3,2] is the lexicographically smallest among all those rearrangements with the length of the longest non-decreasing subsequence equal to 22. And hence [1,3,2][1,3,2] is the lexicographically smallest that satisfies the given conditions.

Test case 3:

Observe from the list above that [1,2,3][1,2,3] is the only rearrangement of [2,1,3][2,1,3] with the length of the longest non-decreasing subsequence equal to 11. And hence [1,2,3][1,2,3] is the lexicographically smallest that satisfies the given conditions.

Test case 4: Non-Decreasing Subsequence of size K solution codechef

There are only 33 possible ways to rearrange [2,2,3][2,2,3].

  • [2,2,3][2,2,3] with length of longest non-decreasing subsequence equal to 33.
  • [2,3,2][2,3,2] with length of longest non-decreasing subsequence equal to 22.
  • [3,2,2][3,2,2] with length of longest non-decreasing subsequence equal to 22.

So there does not exist any rearrangement of [2,2,3][2,2,3] with the length of the longest non-decreasing subsequence equal to 11.

Leave a Comment

Your email address will not be published. Required fields are marked *