Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given $N$ points in $D$-dimensional space. The $i^{th}$ point has $D$ coordinates - $x_{i, 1}, x_{i, 2}, \ldots, x_{i, D}$.

Consider a weighted undirected complete graph with these $N$ points as its vertices. Weight of the edge between points $i$ and $j$ is $|x_{i,1} - x_{j, 1}| + |x_{i,2} - x_{j, 2}| + \ldots + |x_{i, D} - x_{j,D}|$.

Find the weight of the [maximum spanning tree] of this graph.

------ Input: ------

The first line contains two integers $N, D$.
The $i$-th of the next $N$ lines contains a description of the $i$-th point. It has $D$ integers: $x_{i, 1}, x_{i, 2}, \ldots, x_{i,D}$.

------ Output: ------
Output a single line which contains a single integer - the Maximum Spanning Tree Weight

------ Constraints  ------
$1 ≤ D ≤ 5$
$1 ≤ N ≤ 200\,000$
$0 ≤ x_{i, j} ≤ 100\,000$

------ Subtasks ------
10 points, $N ≤ 5000$

90 points, $N ≤ 200\,000$

----- Sample Input 1 ------ 
2 2  

1 1  

2 2
----- Sample Output 1 ------ 
2

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Tree algorithms

Mathematics

Spanning trees

Data structures


Solutions:
distance = lambda X, Y: sum((abs(x - y) for (x, y) in zip(X, Y)))
parent = []
rank = []

def findRoot(node):
	global parent
	while parent[node] != node:
		parent[node] = parent[parent[node]]
		node = parent[node]
	return node

def unionRoot(node1, node2):
	global parent, rank
	root1 = findRoot(node1)
	root2 = findRoot(node2)
	if root1 != root2:
		if rank[root1] > rank[root2]:
			parent[root2] = root1
		elif rank[root2] > rank[root1]:
			parent[root1] = root2
		else:
			parent[root1] = root2
			rank[root2] += 1
		return True
	else:
		return False

def kruskal(n, edges):
	global parent, rank
	parent = [node for node in range(n)]
	rank = [0] * n
	length = 0
	edges = sorted(edges, key=lambda x: x[0])
	n -= 1
	for (c, u, v) in edges:
		if unionRoot(u, v):
			length += c
			n -= 1
			if n == 0:
				break
	return length

def specialsum(mask, X):
	result = 0
	for (i, x) in zip(mask, X):
		if i == '0':
			result += x
		else:
			result -= x
	return result

def solve(N, D, points, specialdists):
	extrema = set([])
	for i in range(2 ** (D - 1)):
		(i_min, i_max) = (-1, -1)
		(d_min, d_max) = (float('inf'), -float('inf'))
		for index in range(N):
			d = specialdists[index][i]
			if d <= d_min:
				d_min = d
				i_min = index
			if d >= d_max:
				d_max = d
				i_max = index
		extrema.add((i_min, i))
		extrema.add((i_max, i))
	edges = []
	for (i, point) in enumerate(points):
		for (j, k) in extrema:
			if i != j:
				dist = abs(specialdists[i][k] - specialdists[j][k])
				edges.append((-dist, i, j))
	return -kruskal(N, edges)
(N, D) = list(map(int, input().strip().split()))
points = []
specialdists = []
for point in range(N):
	coordinates = list(map(int, input().strip().split()))
	special = []
	for i in range(2 ** (D - 1)):
		mask = bin(i)[2:]
		mask = '0' * (D - len(mask)) + mask
		special.append(specialsum(mask, coordinates))
	specialdists.append(special)
	points.append(coordinates)
if N == 1:
	print(0)
else:
	print(solve(N, D, points, specialdists))


DEBUG = False
from random import randrange

def gen_one(D, limit, limit_int=100):
	return [tuple([randrange(limit_int) for _ in range(D)]) for _ in range(limit)]

def dist(a, b):
	ret = 0
	for (av, bv) in zip(a, b):
		ret += abs(av - bv)
	return ret

def prims(pts, dist_func=dist, extra_info=False):
	root = pts[0]
	front = list(range(1, len(pts)))
	front_dist = [0] + [dist_func(root, pt) for pt in pts[1:]]
	ret = 0
	min_edge = None
	while len(front) > 0:
		best = 0
		best_dist = front_dist[front[0]]
		for ind in range(1, len(front)):
			cand = front[ind]
			if front_dist[cand] > best_dist:
				best_dist = front_dist[cand]
				best = ind
		pt = pts[front[best]]
		front[best] = front[-1]
		front.pop()
		for f in front:
			front_dist[f] = max(front_dist[f], dist_func(pts[f], pt))
		ret += best_dist
		if min_edge is None or min_edge > best_dist:
			min_edge = best_dist
	if not extra_info:
		return ret
	else:
		return min_edge

def bin_array(D):
	if D > 1:
		for arr in bin_array(D - 1):
			yield (arr + [False])
			yield (arr + [True])
	else:
		yield [False]
		yield [True]

def gen_box_pts(pts):
	root = pts[0]
	dim = []
	for d in root:
		dim.append([d, d])
	for pt in pts:
		for (i, d) in enumerate(pt):
			if d < dim[i][0]:
				dim[i][0] = d
			if d > dim[i][1]:
				dim[i][1] = d
	ret = []
	for incs in bin_array(len(root)):
		pt = []
		for (ind, inc) in enumerate(incs):
			if inc:
				pt.append(dim[ind][1])
			else:
				pt.append(dim[ind][0])
		ret.append(tuple(pt))
	return ret

def biggest_dist(root, pts):
	best_dist = -1
	for pt in pts:
		cand = dist(root, pt)
		if cand > best_dist:
			best_dist = cand
	return best_dist

def biggest_dist_cached_distances(root, pts, pts_dists, dist_limit):
	cands = [(dist(root, pt), i) for (i, pt) in enumerate(pts)]
	(best_dist, best_ind) = max(cands)
	if best_dist > dist_limit:
		for (d, i) in cands:
			if d > dist_limit and i != best_ind and (d > pts_dists[best_ind][i]):
				pts_dists[best_ind][i] = d
				pts_dists[i][best_ind] = d
	return best_dist

def biggest_dist_index(root, pts):
	best_dist = -1
	for (index, pt) in enumerate(pts):
		cand = dist(root, pt)
		if cand > best_dist:
			best_dist = cand
			best = index
	return best

def solve(pts):
	D = len(pts[0])
	if len(pts) <= 2 ** D:
		return prims(pts)
	if DEBUG and len(pts) < 10:
		print(pts)
	box_pts = gen_box_pts(pts)
	if DEBUG:
		print(box_pts)
	boundry = []
	for corner in box_pts:
		i = biggest_dist_index(corner, pts)
		b = pts[i]
		pts[i] = pts[-1]
		pts.pop()
		boundry.append(b)
	if DEBUG:
		print(boundry)
	cached_dist = [[dist(i, j) for j in boundry] for i in boundry]
	min_edge = prims(boundry, extra_info=True)
	extra_dist_func = lambda x, y: cached_dist[x][y]
	if DEBUG:
		print(cached_dist)
	if DEBUG:
		print(min_edge)
	ret = 0
	for pt in pts:
		d = biggest_dist_cached_distances(pt, boundry, cached_dist, min_edge)
		if DEBUG:
			print('Max corner dist for {} is {}'.format(pt, d))
		ret += d
	if DEBUG:
		print(cached_dist)
	prim_tree = prims(list(range(len(boundry))), dist_func=extra_dist_func)
	if DEBUG:
		print(prim_tree)
	ret += prim_tree
	return ret

def loop():
	(N, _) = map(int, input().split())
	pts = list((tuple(map(int, input().split())) for _ in range(N)))
	print(solve(pts))
loop()

def test_all():
	big_test()

def test2D():
	for _ in range(100):
		if not test(2, 5, 5):
			break
	for _ in range(100):
		if not test(2, 10, 100):
			break
	for _ in range(100):
		if not test(2, 100, 1000):
			break

def test3D():
	for _ in range(100):
		if not test(3, 9, 5):
			break
	for _ in range(100):
		if not test(3, 10, 100):
			break
	for _ in range(100):
		if not test(3, 100, 1000):
			break

def test5D():
	for _ in range(100):
		if not test(5, 33, 5):
			break
	for _ in range(100):
		if not test(5, 100, 100):
			break
	for _ in range(10):
		if not test(5, 1000, 1000):
			break

def test1D():
	for _ in range(100):
		if not test(1, 5, 5):
			break
	for _ in range(100):
		if not test(1, 10, 100):
			break
	for _ in range(100):
		if not test(1, 100, 1000):
			break

def big_test():
	pts = gen_one(5, 200000, 100000)
	s = solve(pts)
	return s

def test(D, num_pts, limit):
	try:
		pts = gen_one(D, num_pts, limit)
		pts1 = pts[:]
		p = prims(pts)
		s = solve(pts1)
		ret = p == s
		if not ret:
			print(pts)
			print(p)
			print(s)
	except:
		print(pts)
		print(p)
		print(s)
	return ret

def cur_bad25():
	pts = [(0, 3), (0, 2), (4, 3), (4, 0), (1, 0)]
	pts1 = pts[:]
	p = prims(pts)
	print(p)
	s = solve(pts1)
	print(s)