HIDIF - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sky_nik
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have an array A of length N.
At most one of its elements can be replaced with any integer between 1 and K.
Find the maximum possible value of

\sum_{i=1}^{N-1} |A_i - A_{i+1}|

EXPLANATION:

Suppose we choose to replace A_i.
Then, since our aim is to maximize the sum of adjacent differences, there are really only two possible choices: either we set A_i := 1 or A_i := K.

Why?

Suppose you set A_i := x where 1 \lt x \lt K.
Then,

  • If x \leq A_{i-1} and x\leq A_{i+1}, setting A_i := x-1 further increases the differences between index i and its neighbors while not changing the differences with the rest of the array.
    Repeat this argument till you end up with x = 1.
  • Similarly, if x\geq A_{i-1} and x\geq A_{i+1}, setting A_i := x+1 is better for the sum of adjacent differences. Again, repeating this argument puts us at x = K.
  • That leaves the case where x lies between A_{i-1} and A_{i+1}.
    Here however, notice that replacing x with x+1 doesn’t change the sum of adjacent differences, so you can simply keep doing this till you reach the second case above; after which again going to K is optimal.

So, either 1 or K will be optimal always.

So, there are really only 2N possible replacements: set each element to either 1 or K.
Simply try all 2N of these replacements, and compute the sum of adjacent differences of the new array directly in \mathcal{O}(N) time for a solution in \mathcal{O}(N^2) time, which is fast enough.

It’s also possible to implement a solution that runs in \mathcal{O}(N) time, utilizing the fact that changing A_i only changes the differences |A_i - A_{i-1}| and |A_i - A_{i+1}|.
So, rather than recomputing the differences across the entire array, you can just remove the two existing differences from the sum and add in the new ones, which takes constant time.
This implementation can be seen in the tester’s code below.

TIME COMPLEXITY:

\mathcal{O}(N^2) or \mathcal{O}(N) per testcase.

CODE:

Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int t; cin >> t; while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& ai : a) {
      cin >> ai;
    }

    int64_t tot_var = 0;
    for (int i = 1; i < n; ++i) {
      tot_var += abs(a[i - 1] - a[i]);
    }

    const vector<int> cands = {1, k};

    int64_t mx = tot_var;
    for (int i = 0; i < n; ++i) {
      for (int cand : cands) {
        int64_t delta = 0;
        if (i) {
          delta += abs(cand - a[i - 1]) - abs(a[i] - a[i - 1]);
        }
        if (i + 1 < n) {
          delta += abs(cand - a[i + 1]) - abs(a[i] - a[i + 1]);
        }
        mx = max(mx, tot_var + delta);
      }
    }
    cout << mx << '\n';
  }
}
Editorialist's code (Python) 
def calc(a):
    res = 0
    for i in range(1, len(a)):
        res += abs(a[i] - a[i-1])
    return res

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        x = a[i]
        a[i] = 1
        ans = max(ans, calc(a))
        a[i] = k
        ans = max(ans, calc(a))
        a[i] = x
    print(ans)