2026 ICPC Asia Pacific Championship

H. Reflect Sort

The key observations are:

• operations do not affect $d_i=|a_{i+1}-a_{i}|$

  This observation shows that the $a_n$ is minimal if and only if $a_1$ is minimal, and is obtained by $a_1+\sum_{i=1}^{n-1} d_i$.

• suppose two numbers $a_i, a_j, i\lt j$, we can either make $a_1\gets a_1+2(a_i-a_j)$ or $a_1\gets a_1-2(a_i-a_j)$

  To get $a_1\gets a_1-2(a_i-a_j)$, we do $\texttt{(i,prefix)}\to \texttt{(j,prefix)}$. To get $a_1\gets a_1 + 2(a_i-a_j)$, we do $\texttt{(i,suffix)}\to\texttt{(i,prefix)}\to\texttt{(j,prefix)}$.

This means that we just need to minimize $a_1$ by adding or subtracting $\binom{n}{2}$ pairs of $2(a_i-a_j)$, which is sufficient to use only $(n-1)$ pairs, i.e. $2(a_{i+1}-a_i)$

Suppose $g=\gcd_i 2|a_{i+1}-a_i|$, this is equivalent to $a_1\gets a_1 \mod g$. Be careful of $g=0$ case and $g|a_1$ case. Time complexity $O(n\log V)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <bits/stdc++.h>

int main() {
  int n;
  std::cin >> n;
  std::vector<long long> a(n), d;
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    if (i >= 1)
      d.push_back(std::abs(a[i - 1] - a[i]));
  }

  auto f = 0ll;
  for (auto x : d)
    f = std::gcd(f, x * 2);

  auto begin = f == 0 ? a[0] : (a[0] % f == 0 ? f : a[0] % f);
  std::cout << begin + std::accumulate(d.begin(), d.end(), 0ll) << "\n";
}