Meet In The Median solution codechef

For Solution

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], [5][5] 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.

Output Format

• 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

• 1≤T≤301≤T≤30
• 1≤K≤N≤2×1051≤K≤N≤2×105
• 1≤Ai≤1091≤Ai≤109
• 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``````