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 space-separated integers $N$ and $M$. - The second line contains $N$ space-separated 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 $28-10=18$ - $(10, 20)$ with difference $20-10=10$ - $(15, 28)$ with difference $28-15=13$ - $(15, 20)$ with difference $20-15=5$, which is the smallest possible
|Tags||challenge, nov19, ojasbansal, sorting, two-pointers, watcher|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.