Overview

This problem asks us to rearrange books to minimize the sum of absolute differences in thickness between adjacent books. By sorting and arranging them, the answer becomes the difference between the maximum and minimum values.

Analysis

Key Insight

First, let’s consider a concrete example. Suppose we have books with thicknesses \([3, 1, 4, 1, 5]\).

Sorting this gives \([1, 1, 3, 4, 5]\). The sum of adjacent differences is: $\(|1-1| + |3-1| + |4-3| + |5-4| = 0 + 2 + 1 + 1 = 4\)$

This actually equals \(5 - 1 = 4\) (maximum - minimum).

Why Sorting is Optimal

When arranged in sorted order, each book’s thickness is monotonically increasing (or equal). In this case: $\(\sum_{i=1}^{N-1} |V_{i+1} - V_i| = \sum_{i=1}^{N-1} (V_{i+1} - V_i) = V_N - V_1\)$

In other words, the sum of differences equals “maximum - minimum”.

Why This is Minimum

No matter how we arrange the books, we cannot achieve a value smaller than “maximum - minimum”.

Reason: No matter what path we take from the smallest book to the largest book, the “distance traveled” is at least the “straight-line distance” (maximum - minimum). When arranged in sorted order, there are no unnecessary back-and-forth movements, and we travel exactly the “straight-line distance”.

Conversely, in non-sorted arrangements, values repeatedly increase and decrease, causing the same intervals to be traversed multiple times, which increases the total sum.

Naive Approach

Trying all possible arrangements gives \(N!\) permutations, which would result in TLE even for \(N = 20\) or so. However, from the analysis above, we can see that the answer can be found simply by sorting.

Algorithm

1. Sort the book thicknesses
2. Output the value obtained by subtracting the minimum value (first element) from the maximum value (last element) after sorting

n = int(input())
v = list(map(int, input().split()))
v.sort()
print(v[-1] - v[0])

Complexity

• Time complexity: \(O(N \log N)\) (time required for sorting)
• Space complexity: \(O(N)\) (required to store the array)

Implementation Notes

• After sorting, v[-1] gives the maximum value and v[0] gives the minimum value

• This works correctly even when \(N = 1\) (resulting in \(v[0] - v[0] = 0\))

• Python’s sort() uses Timsort, which is a stable and efficient sorting algorithm

  Source Code

n = int(input())
v = list(map(int, input().split()))
v.sort()
print(v[-1] - v[0])

---

This editorial was generated by claude4.5opus.