DSA sheet / Sorting and searching
Stick Lengths
Do these first: Distinct Numbers
The problem in brief
You have n sticks (up to 200 000) with given lengths up to 10^9. Making a stick longer or shorter by d costs d. Print the minimum total cost to make every stick the same length.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1074.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
The final common length is a single number. Write the total cost as a function of that number. What kind of function is it?
-
Each stick contributes |a_i - L|. Sketch the sum of absolute values against L for two or three sticks.
-
Where does the slope of that graph change sign? Think about how many sticks are below L and how many above.
-
The best L is a value in the middle of the sorted lengths. Which one exactly, and does it matter for even n?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
You are minimising f(L) = sum of |a_i - L| over all sticks. Each |a_i - L| is a V-shape, so f is a sum of V-shapes: piecewise linear and convex. The minimum is where the slope crosses zero. Moving L up by one costs one for every stick at or below L and saves one for every stick above it. As long as more sticks are above than below, raising L helps; the balance point is the median.
So the answer is: sort, take the middle element as L, add up the distances. A brute-force approach would try all L, which you can use in testing on tiny inputs to confirm the median claim, but is hopeless at 10^9. For an even count, any L between the two middle values is equally good, so either middle element works.
The habit: turn “make everything equal” into a one-variable cost function, spot convexity, and locate the optimum at a balance point, here the median (for squared costs it would be the mean).
Intuition
Picture the sticks as points on a line and one meeting place for all of them. To minimise total walking, pick the median: if you stand anywhere else, shifting toward the median moves more people closer than farther.
Approach
- Sort the lengths.
- Take L = a[n / 2] (integer division; any of the two middle elements works for even n).
- Sum |a_i - L| over all i and print it.
Pitfalls: total cost can reach 2 * 10^5 * 10^9 = 2 * 10^14 so use 64-bit. You do not need to test values other than the median.
Complexity
O(n log n) for the sort, O(n) for the sum; O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
long long mid = a[n / 2], cost = 0;
for (long long x : a) cost += llabs(x - mid);
cout << cost << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
a = sorted(map(int, data[1:1 + n]))
mid = a[n // 2]
print(sum(abs(x - mid) for x in a))
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
long[] a = new long[n];
for (int i = 0; i < n; i++) {
st.nextToken();
a[i] = (long) st.nval;
}
Arrays.sort(a);
long mid = a[n / 2], cost = 0;
for (long x : a) cost += Math.abs(x - mid);
System.out.println(cost);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const a = Float64Array.from(data.slice(1, 1 + n)).sort();
const mid = a[Math.floor(n / 2)];
let cost = 0;
for (const x of a) cost += Math.abs(x - mid);
console.log(cost);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).