Overview

Given the \(M\)-dimensional coordinates of \(N\) cities, the problem asks to find the sum of Manhattan distances between all distinct pairs of cities.

Analysis

In a naive approach, for every pair of cities \((i, j)\) (\(1 \leq i < j \leq N\)), we compute the absolute difference in each dimension. Since there are \(O(N^2)\) pairs and each pair requires computation across \(M\) dimensions, the total time complexity is \(O(N^2M)\). Since \(N\) can be as large as \(2 \times 10^5\), this method is too slow.

Instead, we consider computing each dimension independently and summing the results at the end. Since the contribution of each dimension to the Manhattan distance can be computed independently, the total sum can be expressed as the sum of the absolute value sums of differences for each dimension.

For each dimension \(k\), we sort the \(N\) coordinate values of the cities and efficiently compute how each element contributes to the sum of absolute differences with all preceding elements.

Algorithm

1. Process each dimension \(k\) (\(1 \leq k \leq M\)) independently.
2. Collect all city coordinate values for dimension \(k\) into a list and sort it.
3. Build a prefix sum array for the sorted list.
4. For each coordinate value \(coord\_list[i]\):
   • The sum of absolute differences with the preceding \(i\) elements can be computed as \(coord\_list[i] \times i - prefix\_sum[i]\).
   • This works because the list is sorted, so absolute values are unnecessary and the sum can be expressed as a simple sum of differences.
5. Sum these values across all dimensions to obtain the total sum.

With this approach, each dimension requires \(O(N \log N)\) for sorting and \(O(N)\) for prefix sum computation and accumulation, resulting in an overall efficient time complexity of \(O(MN \log N)\).

Complexity

• Time complexity: \(O(MN \log N)\)
  • For each dimension, we sort \(N\) elements (\(O(N \log N)\)) and perform linear processing (\(O(N)\)).
  • Since the number of dimensions \(M\) is at most 10, which is small, this is effectively \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • For the list storing coordinate values of each dimension and the prefix sum array.

Implementation Notes

• Processing each dimension independently simplifies the problem.

• Sorting eliminates the need for absolute value computation, allowing algebraic processing.

• Precomputing the prefix sum enables constant-time computation for each element.

• Since values can become very large, be careful of integer overflow (in Python, this is not an issue since arbitrary-precision integers are used automatically).

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    A = []
    index = 2
    for i in range(n):
        row = list(map(int, data[index:index+m]))
        index += m
        A.append(row)
    
    total = 0
    for k in range(m):
        coord_list = [A[i][k] for i in range(n)]
        coord_list.sort()
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i+1] = prefix_sum[i] + coord_list[i]
        
        for i in range(n):
            total += coord_list[i] * i - prefix_sum[i]
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.