Distinct Numbers Codechef Solution

Problem

Given an array $A$ consisting of $N$ distinct integers (1 \le A_i \le 2 \cdot N)(1≤Ai​≤2⋅N), we have to perform $K$ moves. We perform the following steps in one move:

• Select an integer $X$ such that $1\le X\le 2\cdot N$ and X \ne A_iX=Ai​ for all $i$ $(X$ is not equal to any element of the current array$)$.
• Append $X$ to $A$.
• The score of this move = (\max_{1 \le i \le |A|} A_i) – X=(max1≤i≤∣A∣​Ai​)−X.
  Note that the score is calculated after appending $X$. Thus, $X$ can be the maximum element of the array as well.

For e.g. if $A=[3,1,5]$ and we append $X=2$ to $A$, then, $A$ becomes $[3,1,5,2]$ and the score of this move is $\max ([3,1,5,2])-2=5-2=3$.

Find the maximum sum of scores we can achieve after performing exactly $K$ moves.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains three space-separated integers $N$ and $K$ — the size of the array $A$ and the number of moves respectively.
  • The second line of each test case contains $N$ space-separated integers A_1, A_2, \dots, A_NA1​,A2​,…,AN​ denoting the array $A$.

Output Format

For each test case, output the maximum sum of scores we can achieve after performing exactly $K$ moves.
It is guaranteed that it is always possible to perform $K$ moves under the given constraints.

Constraints

Sample 1:

3
3 1
1 3 6
2 2
1 2
3 2
1 2 5

4
1
3

Explanation:

Test Case 1: We can perform the following move:

• Append $X=2$. Score of this move $=\max ([1,3,6,2])-2=6-2=4$

Hence, the maximum total score is $4$.

Test Case 2: We can perform the following moves:

• Append $X=4$. Score of this move $=\max ([1,2,4])-4=4-4=0$
• Append $X=3$. Score of this move $=\max ([1,2,4,3])-3=4-3=1$

Hence, the maximum total score is $0+1=1$.

Test Case 3: We can perform the following moves:

• Append $X=4$. Score of this move $=\max ([1,2,5,4])-4=5-4=1$
• Append $X=3$. Score of this move $=\max ([1,2,5,4,3])-3=5-3=2$

Hence the maximum total score is $1+2=3$.