Chef and Minimum Colouring

All submissions for this problem are available.
### Read problem statements in [Mandarin Chinese](http://www.codechef.com/download/translated/NOV19/mandarin/CAMC.pdf) and [Vietnamese](http://www.codechef.com/download/translated/NOV19/vietnamese/CAMC.pdf) as well. Chef placed $N$ boxes (numbered $1$ through $N$) in a straight line. For each valid $i$, the $i$th box contains $A_i$ balls. Then, Chef painted the boxes using $M$ distinct colours in such a way that for each $M$ consecutive boxes, no two of these boxes have the same colour. Help Chef choose $M$ distinct boxes (not necessarily consecutive) such that no two of the chosen boxes have the same colour and the difference between the number of balls in a box that contains the maximum number of balls and a box that contains the minimum number of balls among the chosen boxes is the smallest possible. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $M$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$. ### Output For each test case, print a single line containing one integer ― the minimum possible difference between the maximum and minimum number of balls in the chosen boxes. ### Constraints  $1 \le T \le 5$  $2 \le M \le N \le 10^5$  $1 \le A_i \le 10^9$, for each valid $i$ ### Subtasks **Subtask #1 (30 points):** $N \le 10^3$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 1 4 2 10 20 15 28 ``` ### Example Output ``` 5 ``` ### Explanation **Example case 1:** Let's denote the colours by 'R' (red) and 'G' (green). There are two possible ways of painting the boxes: "RGRG" and "GRGR". There are four ways to choose two boxes (one red and one green box). The numbers of balls in them and the differences are:  $(10, 28)$ with difference $2810=18$  $(10, 20)$ with difference $2010=10$  $(15, 28)$ with difference $2815=13$  $(15, 20)$ with difference $2015=5$, which is the smallest possibleAuthor:  ojasbansal 
Editorial  https://discuss.codechef.com/problems/CAMC 
Tags  challenge, nov19, ojasbansal, sorting, twopointers, watcher 
Date Added:  9102019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions