Stick lengths

Abridged problem statement

You are given an array $a$ of length $n$. Choose an array $c$ such that $a[i]+c[i]=a[j]+c[j]$ for all $(i,j)$, and $\sum|c[i]|$ is minimized.

Solution

Let’s fix the final value each $a[i]$ ends up with: call this $x$. Then, our goal is to choose an $x$ that minimizes $\sum|a[i]-x|$.

Here’s a plot of the value of $\sum|a[i]-x|$ against $x$ for $a=[0,1,4,5,7,10,12,13]$:

We can make some inferences from this graph. To begin with, it looks like the graph decreases first, then becomes flat, and then increases. In addition to this, the minimum value seems to be attained at all values from $x=5$ to $x=7$.

Let us try generalising these observations. Define $f(x)=\sum|x-a[i]|$, and examine the value of $f(x+1)-f(x)$:

• Changing $x$ to $x+1$ brings us closer to all $a[i]>x$.
• It also brings us farther from all $a[i] \le x$.

That is,

So, define $c(v)=|\{i; a[i] \le v\}|$, then $f(x+1)-f(x) = c(x) - [n-c(x)] = 2c(x) - n$. Therefore, $f(x+1)<f(x)$ when $c(x)<\frac{n}{2}$. Since $c(x)$ is an integer, this becomes $c(x)\le\lfloor\frac{n-1}{2}\rfloor$.

In other words, as long as there are less than $\lfloor\frac{n-1}{2}\rfloor$ elements to our left, $f(x+1)$ is better than $f(x)$. After that, $f(x+1)$ is worse (or just as good as) $f(x)$. So we pick $x$ such that there are exactly $\lfloor\frac{n-1}{2}\rfloor$ elements to the left of it in our array.

Such a value is called a median of the array. Hence, the minimum is attained when $x$ is a median of $a$. If $n$ is even, every value between the two medians is optimal.

Code

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &i : a) {
    cin >> i;
  }
  sort(a.begin(), a.end());
  int64 ans = 0;
  for (int &i : a) {
    ans += abs(a[(n - 1) / 2] - i);
  }
  cout << ans << '\n';
}