CDX1604 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Puneet Gupta
Editorialist: Puneet Gupta

DIFFICULTY:

EASY

PREREQUISITES:

GREEDY, IMPLEMENTATION, SORTING

PROBLEM:

Given a sequence of integers A1, A2,  ..., AN, count the minimum number of moves needed to build a permutation, provided in one move, you are allowed to decrease or increase any number by one

EXPLANATION:

The solution of the problem is rather simple. Sort all integers a and then make integer 1 from a[1], integer 2 from a[2] and so on.
So, integer a[i] adds to the answer the value |a[i] - i|. The answer should be count in 64-bit type. You can simply guess why such solution is correct.

AUTHOR’S SOLUTION:

Author’s solution can be found here.

//