[Solution] Distinct Numbers CodeChef Solution

Problem

Given an array $A$ consisting of $N$ distinct integers $(1 \le A_i \le 2 \cdot 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_i$ 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$.
  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_N$ 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.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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$.