MEXARR - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: helloLad
Tester: wasd2401
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sorting

PROBLEM:

You have an array A. In one move, you can increase or decrease any of its elements by 1.
Find the minimum number of moves to reach an array whose mex is maximum possible.

EXPLANATION:

The maximum possible mex of an array A of length N is exactly N, attained exactly when A is [0, 1, 2, \ldots, N-1] (or some rearrangement of this).

So, we want to get A into this form; meaning we need to decide which of 0, 1, 2, \ldots, N-1 each A_i will end up at.
This can be done greedily!
That is, turn the smallest element of A into 0, the second-smallest into 1, the third-smallest into 2, …, the largest into N-1.

A simple way to implement this is to just sort A in ascending order first, so that A_i is the i-th smallest element.
Then, the required number of moves is just

\sum_{i=1}^N |A_i - (i-1)|
Proof of correctness

Let A_i denote the initial value at index i, and B_i denote the final value; so the total number of moves is the sum of |A_i - B_i| across all i.

If A_i \lt A_j and B_i \gt B_j, you can show (via some simple algebra) that swapping B_i and B_j never results in worse cost: sometimes it will remain the same, and sometimes it will decrease.
EIther way, this shows that there exists an optimal solution which has A_i\lt A_j \implies B_i \leq B_j, which is exactly what our greedy choice does!

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    print(sum(abs(a[i] - i) for i in range(n)))
2

include <bits/stdc++.h>
using namespace std;

int main() {
int t; cin>>t;
while(t–){
int n; cin>>n;
vector v(n, 0);
for(int i=0; i<n; i++){
cin>>v[i];
}
sort(v.begin(), v.end());
int ans =0;
for(int i=0; i<n; i++){
ans+=abs(v[i] - i);
}
cout<<ans<<endl;
}
}

Why am I getting a wrong answer in one of the unknown testcases for the above code?

1 Like
3

Use long long for ans