Overview

This problem asks us to efficiently compute the sum of Manhattan distances between \(N\) cities, each with \(M\)-dimensional coordinates.

Approach

Manhattan distance is expressed as the sum of absolute differences for each dimension:

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

A naive solution would require computing the absolute difference in each dimension for every pair of cities \((i, j)\). This has a time complexity of \(O(N^2 M)\), which is far too slow given the constraint that \(N\) can be up to \(2 \times 10^5\).

However, we can speed up the computation by exploiting a property of Manhattan distance. For each dimension \(k\), the sum of \(|A_{i,k} - A_{j,k}|\) can be computed independently. In other words, we can process each dimension separately.

Furthermore, by sorting the coordinates within each dimension, we can efficiently determine how each coordinate value contributes when compared against all others. Specifically, if a value \(x\) is at position \(i\) in the sorted array:

• \(x\) is treated as the “larger side” in comparisons with the \(i\) elements to its left
• \(x\) is treated as the “smaller side” in comparisons with the \(N - 1 - i\) elements to its right

Therefore, the contribution of value \(x\) is:

\[ x \times (i - (N - 1 - i)) = x \times (2i - N + 1) \]

This allows each dimension to be computed in \(O(N \log N)\).

Algorithm

1. For each dimension \(k = 1, \dots, M\), do the following:

   • Extract the \(k\)-th coordinate of all cities into a list col
   • Sort col
   • For each element col[i] after sorting, compute its contribution when compared against other elements:
     • Number of comparisons with the left side (values smaller than itself): \(i\)
     • Number of comparisons with the right side (values larger than itself): \(N - 1 - i\)
     • Contribution: col[i] * (i - (N - 1 - i))
   • Add this contribution to the running total

2. The sum of contributions across all dimensions is the answer.

Complexity

• Time complexity: \(O(NM \log N)\)
  (Sorting is required for each dimension → \(M\) sorts, each \(O(N \log N)\))
• Space complexity: \(O(NM)\)
  (Storing all coordinates)

Implementation Notes

• sys.stdin.read is used to read input quickly

• The key observation is that each dimension can be computed independently, so the multi-dimensional problem is processed one dimension at a time

• The main technique is computing “how much each element contributes” using a coefficient after sorting

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    # 座標データの読み込み
    coords = []
    idx = 2
    for i in range(N):
        row = list(map(int, data[idx:idx+M]))
        coords.append(row)
        idx += M
    
    total = 0
    
    # 各次元ごとに処理
    for k in range(M):
        # k次元目の座標を取り出す
        col = [coords[i][k] for i in range(N)]
        # ソートする
        col.sort()
        # 各要素が他の要素に対してどれだけ寄与するかを計算
        for i in range(N):
            # col[i] が引かれる回数: (N - 1 - i)
            # col[i] が足される回数: i
            total += col[i] * (i - (N - 1 - i))
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.