Overview

This problem asks you to compute the sum of Manhattan distances between all pairs of \(N\) cities efficiently by calculating independently for each dimension, using sorting and prefix sums.

Analysis

Naive Approach and Its Issues

The first idea that comes to mind is to directly compute the Manhattan distance for every pair of cities \((i, j)\).

for i in range(N):
    for j in range(i+1, N):
        for k in range(M):
            total += abs(A[i][k] - A[j][k])

In this method, the number of city pairs is \(\frac{N(N-1)}{2}\), and for each pair we need to compute across \(M\) dimensions, so the time complexity is \(O(N^2 M)\). When \(N = 2 \times 10^5\), this amounts to approximately \(2 \times 10^{11}\) operations, which will result in TLE (Time Limit Exceeded).

Key Insight: We Can Separate by Dimension

Looking carefully at the definition of Manhattan distance, it is the sum of absolute differences across each dimension. In other words, the desired value can be transformed as follows:

\[\sum_{1 \leq i < j \leq N} \sum_{k=1}^{M} |A_{i,k} - A_{j,k}| = \sum_{k=1}^{M} \sum_{1 \leq i < j \leq N} |A_{i,k} - A_{j,k}|\]

We can compute each dimension \(k\) independently!

Efficient Computation in One Dimension

For dimension \(k\), let the coordinate values be \(x_1, x_2, \ldots, x_N\), and sort them to get \(y_1 \leq y_2 \leq \cdots \leq y_N\).

After sorting, we can remove the absolute value: \(|y_i - y_j| = y_i - y_j\) (when \(i > j\)).

Considering the contribution of \(y_i\) to the total sum: - There are \(i-1\) elements smaller than \(y_i\) - For each such pair, we add \(y_i - y_j\) - Therefore, the contribution of \(y_i\) is \((i-1) \times y_i - (y_1 + y_2 + \cdots + y_{i-1})\)

Using a prefix sum, this can be computed in \(O(1)\).

Concrete Example

For coordinates \([3, 1, 4]\): 1. After sorting: \([1, 3, 4]\) 2. \(i=0\): contribution = \(0 \times 1 - 0 = 0\) 3. \(i=1\): contribution = \(1 \times 3 - 1 = 2\) (difference of pair \((1,3)\)) 4. \(i=2\): contribution = \(2 \times 4 - 4 = 4\) (sum of differences of pairs \((1,4)\) and \((3,4)\))

Total = \(0 + 2 + 4 = 6 = |3-1| + |3-4| + |1-4|\) ✓

Algorithm

1. For each dimension \(k = 1, 2, \ldots, M\), do the following:
   • Collect the \(k\)-th dimension coordinates of all cities into an array
   • Sort that array
   • While updating the prefix sum, compute for each element “the sum of differences with all smaller elements”
   • Add to the total sum
2. Output the final total sum

Complexity

• Time complexity: \(O(MN \log N)\)
  • Sorting takes \(O(N \log N)\) per dimension, and prefix sum computation takes \(O(N)\)
  • This is repeated for \(M\) dimensions
• Space complexity: \(O(N)\)
  • Array to store coordinates for each dimension

Implementation Notes

• Overflow prevention: Since coordinate absolute values can be up to \(10^6\) and the number of cities up to \(2 \times 10^5\), the total sum can become very large. In Python, there is no integer overflow so this is not a concern, but in other languages you need to use 64-bit integer types.

• Timing of prefix sum updates: By updating the prefix sum after computing the contribution of the \(i\)-th element, we can correctly obtain “the sum of all preceding elements.”

  Source Code

def solve():
    N, M = map(int, input().split())
    A = []
    for _ in range(N):
        row = list(map(int, input().split()))
        A.append(row)
    
    total = 0
    
    # 各次元ごとに独立に計算
    for j in range(M):
        # j番目の座標成分を取り出してソート
        coords = [A[i][j] for i in range(N)]
        coords.sort()
        
        # ソート後、i番目の要素は、それより前のi個の要素との差の絶対値の和に寄与
        # coords[i] - coords[k] (k < i) の総和を効率的に計算
        # = i * coords[i] - (coords[0] + coords[1] + ... + coords[i-1])
        prefix_sum = 0
        for i in range(N):
            # coords[i]は、前のi個の要素それぞれとのペアで、coords[i] - coords[k]を寄与
            total += i * coords[i] - prefix_sum
            prefix_sum += coords[i]
    
    print(total)

solve()

---

This editorial was generated by claude4.5opus.