HackerRank Geometry – Hyperspace Travel

Challenge: Hyperspace Travel

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464740365

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/hyperspace-travel/problem

Cerinta

A group of $n$ friends living in an $m$-dimensional hyperspace want to meet up at some central location. The hyperspace is in the form of an $m$-dimensional grid, and each person can only move along grid lines. For example, to go from $(0, 0) \rightarrow (1, 1)$ in a $2$-dimensional space, one possible route is $(0, 0) \rightarrow (0, 1) \rightarrow (1, 1)$ for a total distance traveled of $2$ units.

Given the coordinates, $(X[0, 1, \ldots, m - 1])$, for $n$ friends, find a point at which all $n$ friends can meet such that the total sum of the distances traveled by all $n$ friends is minimal. If there are multiple such points, choose the lexicographically smallest one. The point $P_1[0, 1, \ldots, m - 1]$ is lexicographically smaller than $P_2[0, 1, \ldots, m - 1]$ if there exists such $j \lt m$ that $\forall i \lt j\,P_1[i] = P_2[i]$ and $P_1[j]<P_2[j]$.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and $m$.		
Each line $i$ of the $n$ subsequent lines contains $m$ space-separated integers describing the respective coordinates (i.e., $x_0, x_1, \ldots, x_{m - 1}$) for friend $i$.

Output Format

Print $m$ space-separated integers describing the coordinates of the meeting point.

Constraints

+ $1 \le n \le 10^4$  
+ $1 \le m \le 10^2$  
+ $-10^9 \le x_i \le 10^9$

Cod sursa

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    cols = [[] for _ in range(m)]
    for _ in range(n):
        for j in range(m):
            cols[j].append(int(next(it)))

    ans = []
    k = (n - 1) // 2  # lower median for lexicographically smallest minimizer
    for j in range(m):
        c = cols[j]
        c.sort()
        ans.append(str(c[k]))

    sys.stdout.write(' '.join(ans))

if __name__ == '__main__':
    main()