You’re given a sequence of NN distinct integers. You need to find a subsequence of length KK with the maximum possible median. Meet In The Median solution codechef
The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is selected. For example, if the sequence is [3,4,2,1,5][3,4,2,1,5], then the median is 33 since after sorting, it will look like [1,2,3,4,5][1,2,3,4,5] and 33 is the only middle element. The median of [4,2,1,5][4,2,1,5] is 22 since after sorting, the value 22 is the left of the two middle elements 22 and 44.
A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if the sequence is [2,1,4,5,7][2,1,4,5,7], then [1,5,7][1,5,7], [2,1,4][2,1,4],  are some valid subsequences but [4,1,2][4,1,2], [1,6,7][1,6,7] are not.
Input Format Meet In The Median solution codechef
- The first line will contain TT, the number of test cases. The description of test cases follow.
- The first line of each test case consists of two space-separated integers NN, the length of the sequence, and KK, the length of the subsequence to be found.
- The second line of each test case consists of NN distinct space-separated integers AiAi, the elements of the sequence.
- For each test case, output two lines.
- The first line should consist of the median of the subsequence with the maximum median.
- The second line should consist of KK space-separated integers, representing a subsequence with that median. If there are multiple such subsequences, print any.
Constraints Meet In The Median solution codechef
- Sum of NN over all test cases won’t exceed 5×1055×105
Sample Input 1
1 5 3 1 4 3 6 5
Sample Output 1
5 1 6 5