SPOJ.com - Problem AMR10G

AMR10G - Christmas Play

#ad-hoc-1

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.

INPUT
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
Output T lines, each line containing the required answer for the corresponding test case.

CONSTRAINTS
T <= 30
1 <= K <= N <= 20000
1 <= height <= 1000000000

SAMPLE INPUT

SAMPLE OUTPUT

0
1
3

EXPLANATION
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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 Next >

	Sumit Paroothi: 2015-08-12 07:27:05 easy one!
	shreyas agrawal: 2015-08-05 17:17:55 my code is running on ideone and also all test cases are running but it is not get accepted on spoj Last edit: 2015-08-05 17:18:59
	Parth: 2015-06-16 20:48:26 O(nlogn+n) Time 0.08 sec ...easy...............:)
	SangKuan: 2015-05-19 08:33:03 same code,tle with common lisp,ac by c++...lol
	:.Mohib.:: 2015-05-18 17:37:44 Silly mistakes coast me 2 wa...:(.....O(nlogn+n)==> AC in 0.08
	deerishi: 2015-02-25 07:59:32 O(nlogn + n)! Doesn't really look like an ICPC problem.
	parit: 2015-02-21 22:12:52 Giving CE, but while running on ideone and on codeblock it is showing proper answer. need Help.
	kavin: 2015-01-31 12:49:22 test cases have extra white spaces in it. need to trim it before processing it. Last edit: 2015-01-31 12:50:16
	MKM: 2015-01-29 19:48:46 0.08 easy!
	Mitch Schwartz: 2015-01-07 22:48:33 @Anvesh Kumar Arrabochu: Possibility of judge error seems very small. You could look again at the submissions to see if they are really identical. (Or in general you could of course get different results for same code using some probabilistic methods, but that probably doesn't apply to your code for this problem.) Anubhav Mathur's reported compilation error issue doesn't carry much weight, since he didn't bother saying anything about the nature of the compilation errors. (The details of a compilation error are visible to the user who submitted that code.) If I recall correctly, his issue occurred at a time when everyone was getting compilation error or internal error because of a temporary site-wide issue that Anubhav may have somehow not noticed. If you double check your submissions and still suspect a judge error, you could email a bug report to admins if you want; see the "About SPOJ" page for that contact info. Last edit: 2015-01-07 23:07:10

Submit solution!

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