Maximize Diversity of an Array
All submissions for this problem are available.You are given an array $A$. The diversity of the array $A$ is defined as number of pairs $i, j, i < j $ such that $A_i \neq A_j$. You want to maximize the diversity of the array. For that, you are allowed to make at most $K$ operations on it, in any of which, you can select a particular element and change its value to any integer in the range 1 to $10^9$, both inclusive. Find out the maximum diversity of the array that you can obtain. ###Input: - First line will contain $T$, number of testcases. Then the testcases follow. - The first line of each testcase contains two integers $N, K$. where $N$ denotes the length of array $A$. - The next line of each testcase contains $N$ space separated integers, the i-th of which denotes $A_i$. ###Output: For each testcase, output in a single line, the answer corresponding to the testcase, which should be an integer denoting the maximum possible diversity. ###Constraints - $1 \leq T \leq 20$ - $0 \leq K \leq 10^9$ - $2 \leq N \leq 10^5$ - $1 \leq A_i \leq 10^9$ ###Sample Input: 3 3 10 1 2 3 4 2 1 1 2 2 6 2 2 3 3 2 4 4 ###Sample Output: 3 6 14
|Time Limit:||2 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.