AMR10G - Christmas Play

My kid's kindergarten class is putting up a Christmas play.  (I hope he gets the lead role.)  The kids are all excited, but the teacher has a lot of work.  She has to produce costumes for a scene with K soldiers.  She wants to buy all the costumes in the same size, allowing for some small amount of length alteration to be done by the kids' parents later.  So she has taken all the kids' height measurements.  Can you help her select K kids from her class of N to play the soldier role, such that the height difference between the tallest and shortest in the group is minimized, and alternations will be easiest?  Tell her what this minimum difference is.
The first line contains the number of test cases T. T test cases follow each containing 2 lines.
The first line of each test case contains 2 integers N and K.
The second line contains N integers denoting the height of the N kids.
Output T lines, each line containing the required answer for the corresponding test case.
T <= 30
1 <= K <= N <= 20000
1 <= height <= 1000000000

3 1
2 5 4
3 2
5 2 4
3 3
2 5 4
In the first test case, the teacher needs to only select 1 kid and hence she can choose any kid since the height difference is going to be 0.
In the second test case, the teacher can choose kids with height 4 and 5.
In the third test case, the teacher is forced to choose all 3 kids and hence the answer = 5-2 = 3

hide comments
abhishen99: 2020-05-29 15:36:06

AC in one go!!

manish_thakur: 2020-01-17 13:09:31


sanket17: 2019-07-11 06:16:44

Brute Force Wins

klmo: 2019-04-20 10:10:34

Be careful with Scanner in java

shadan_amir1: 2019-01-04 12:12:57

MergeSort+WindowSliding=MERRY Christmas!!

adipat: 2018-10-20 10:00:07

Easy problem. First sort in increasing order, then loop from i till i+k < n. Find the minimum of heights[i+k-1]-heights[i]. Basically we need to find the minimum difference between two end points such that there are k elements between them.

pigpork: 2018-06-13 14:07:50

printf ("Follow my Instagram!");

payal2621: 2018-02-07 17:20:32

guys search for window technique on geeks for geeks dont copy the code just understand the example
u will get the idea

sonuverma: 2017-11-11 08:57:05

use quickSort in C

madhur4127: 2017-10-20 18:37:20

Another brute force problem!

Added by:Varun Jalan
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ICPC Asia regionals, Amritapuri 2010