FARAWAY - Editorial

PROBLEM LINK:

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

Author: Nishank Suresh
Testers: Utkarsh Gupta, Jatin Garg
Editorialist: Nishank Suresh

DIFFICULTY:

1056

PREREQUISITES:

None

PROBLEM:

Given an array A whose elements lie between 1 and M, define the distance of an array B (also with elements from 1 to M) to be \sum_{i=1}^N |A_i - B_i|. Compute the maximum possible distance of an array from A.

EXPLANATION:

It is of course optimal to choose either B_i = 1 or B_i = M for each index i.

Note that this choice can be made independently for every index, so the solution is to simply take the best option for each one.

That is, the answer is

\sum_{i=1}^N \max(|A_i - 1|, |A_i - M|)

Note that the answer might not fit inside a 32-bit integer, so make sure to use an appropriate data type.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (Python)
for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    print(sum([max(x-1, m-x) for x in a]))