Hey buddy,

How are you? Last night I saw you programming on Hackerrank in my burger restauraunt. So I wonder if you can help me out on a problem I've been struggling with for like 10 hours.

It is called "The Challenge" and for some reasons the online judge always gives me TLE (Time Limit Exceeded). My code and the important part of the problem are attached with this email. I omitted the problem statement because it was three A4 sheets long and included a very boring story. 

I want you to send me an AC (Accepted) code so that I can learn from you and figure out why my implementation is so slow.

Your favourite burger cook,

Jim

PS: Tuesday is "Happy Burgers Day" so there is a -${\pi}$% discount on all burgers!

the_challenge.psc

### author: jim
### problem: the challenge
### status: TLE
### a..b : iterate from a to b ( both inclusive )
define n, d as integers
define H as an integer array
define X as a two-dimensional integer array

function m(i, j)
   for k = 1..d
      dist = dist + abs(X[i][k] - X[j][k])

function main()
  read n and d from input
  for i = 1..n
     read H[i]
    for j = 1..d
      read X[i][j]  
  sum = 0
  for i = 1..n
      for j = i+1..n
       sum = sum + H[i] * H[j] * m(i, j)
  print sum mod 1000000009

the_challenge.pdf

Input Format

On the first line, you will be given $n$ and ${d}$, then $n$ lines follow, describing the $n$ points. Each point is described as $(H_i,X_{i1},X_{i2},\ldots,X_{id})$. So the first integer of each line is ${H}_i$, then ${d}$ integers follow which will describe the ${X}$ values of point ${i}$. 

Output Format

Print the answer to the challenge modulo $10^{9}+9$ on a single line.

Constraints

$1\leq d\leq4$
$1\leq n\leq3\cdot10^5$
$1\leq H_i\leq10^6$
$|X_{ij}|\leq10^{6}$

Sample Input

3 3
5 1 2 3
7 2 3 4
8 4 5 6

Sample Output

801

Explanation

Compare point 1 and point 2: Our first term of the sum is $5\cdot7\cdot(|1-2|+|2-3|+|3-4|)=105$.

Compare point 1 and point 3: The second term is $5\cdot8\cdot(|1-4|+|2-5|+|3-6|)=360$

Compare point 2 and point 3: The final term will be $7\cdot8\cdot(|2-4|+|3-5|+|4-6|)=336$

So the answer is $105+360+336=801$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Geometry


Solutions:
modval = 1000000009

def fst(a):
	return a[0]

def snd(a):
	return a[1]

def tail(a):
	return a[1:]

def prodM(a):
	t = 1
	for i in range(len(a)):
		t *= a[i]
		t %= modval
	return t

def sumM(a):
	t = 0
	for i in range(len(a)):
		t += a[i]
		t %= modval
	return t
(n, d) = map(int, input().split(' '))
hs = []
ds = [[], [], [], []]
for i in range(n):
	newA = [0, 0, 0, 0, 0]
	dsi = (list(map(int, input().split(' '))) + [0, 0, 0, 0, 0])[0:5]
	hs.append(dsi[0])
	for j in range(4):
		ds[j].append(dsi[j + 1])
hsTotal = sumM(hs)
total = 0
for di in range(4):
	p0 = sorted(zip(ds[di], hs))
	hsv = list(map(snd, p0))
	dsv = list(map(fst, p0))
	hsSum = 0
	s = 0
	for j in range(n - 1):
		hsSum += hsv[j]
		v = prodM([dsv[j + 1] - dsv[j], hsSum, hsTotal - hsSum])
		s += v
		s %= modval
	total += s
	total %= modval
print(total)


(n, d) = map(int, input().split())
matrix = [[0] * (2 * d + 1) for _ in range(n)]
fps = [0] * n
rps = [0] * n
total = 0
for i in range(n):
	matrix[i][:d + 1] = list(map(int, input().split()))
	matrix[i][d + 1:2 * d + 1] = [matrix[i][0] * item for item in matrix[i][1:d + 1]]
for j in range(d):
	matrix.sort(key=lambda x: x[j + 1])
	for i in range(1, n):
		fps[i] = fps[i - 1] + matrix[i - 1][0]
	for i in range(n - 1, 0, -1):
		rps[i - 1] = rps[i] + matrix[i][0]
	total += sum(((fps[i] - rps[i]) * matrix[i][d + j + 1] for i in range(n)))
	total %= 1000000009
print(total)


MOD = 10 ** 9 + 9

def solve(Xs):
	Xs_ = list(zip(*Xs))
	H = Xs_[0]
	result = 0
	for d in range(1, len(Xs_)):
		V = list(zip(Xs_[d], H))
		V.sort()
		HXj = [0]
		Hj = [0]
		for (xj, hj) in V:
			HXj.append(HXj[-1] + hj * xj)
			Hj.append(Hj[-1] + hj)
		for (i, (xi, hi)) in enumerate(V):
			result += hi * (Hj[i] * xi - HXj[i])
		result %= MOD
	return result
(n, d) = map(int, input().split())
Xs = [tuple(map(int, input().split())) for _ in range(n)]
print(solve(Xs))


(n, d) = map(int, input().split())
data = tuple(zip(*(map(int, input().split()) for _ in range(n))))
res = 0
for i in range(d):
	wsum = wxsum = 0
	for (x, w) in sorted(zip(data[1 + i], data[0])):
		wx = w * x
		res = (res + wx * wsum - w * wxsum) % 1000000009
		wsum += w
		wxsum += wx
print(res)


(n, d) = map(int, input().split())
A = [[] for i in range(d)]
for i in range(n):
	line = [int(x) for x in input().split()]
	for k in range(d):
		A[k].append((line[k + 1], line[0]))
mod = 1000000009
sum = 0
for B in A:
	B.sort()
	(sXH, sH) = B[0]
	sXH = sXH * sH % mod
	for i in range(1, n):
		(X, H) = B[i]
		sum = (sum + H * (sH * X - sXH)) % mod
		sXH = (sXH + X * H) % mod
		sH = (sH + H) % mod
print(sum)


P = 1000000009

def quadratic(H, X):
	n = len(H)
	(X, H) = zip(*sorted(zip(X, H), reverse=True))
	diff = [sum(H[1:])]
	for i in range(1, n):
		diff.append(diff[-1] - H[i - 1] - H[i])
	return sum((H[i] * X[i] * diff[i] for i in range(n))) % P
(n, d) = map(int, input().split())
H = [None] * n
X = [None] * n
for i in range(n):
	row = list(map(int, input().split()))
	H[i] = row[0]
	X[i] = row[1:]
print(sum((quadratic(H, [x[j] for x in X]) for j in range(d))) % P)


P = 1000000009

def quadratic(H, X):
	n = len(H)
	(X, H) = zip(*sorted(zip(X, H), reverse=True))
	diff = [sum(H[1:])]
	for i in range(1, n):
		diff.append(diff[-1] - H[i - 1] - H[i])
	return sum((H[i] * X[i] * diff[i] for i in range(n))) % P
(n, d) = map(int, input().split())
H = [None] * n
X = [None] * n
for i in range(n):
	row = list(map(int, input().split()))
	H[i] = row[0]
	X[i] = row[1:]
print(sum((quadratic(H, [x[j] for x in X]) for j in range(d))) % P)


import sys
MOD = 1000000009

def solve(n, d, X):
	result = 0
	for i in range(1, d + 1):
		X.sort(key=lambda x: x[i])
		term_1 = X[0][0]
		term_2 = X[0][0] * X[0][i]
		for j in range(1, n):
			result += X[j][0] * X[j][i] * term_1
			result -= X[j][0] * term_2
			result %= MOD
			term_1 = (term_1 + X[j][0]) % MOD
			term_2 = (term_2 + X[j][0] * X[j][i]) % MOD
	return result % MOD
(n, d) = list(map(int, sys.stdin.readline().split()))
X = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
print(solve(n, d, X))


modval = 1000000009

def fst(a):
	return a[0]

def snd(a):
	return a[1]

def tail(a):
	return a[1:]

def prodM(a):
	t = 1
	for i in range(len(a)):
		t *= a[i]
		t %= modval
	return t

def sumM(a):
	t = 0
	for i in range(len(a)):
		t += a[i]
		t %= modval
	return t
(n, d) = map(int, input().split(' '))
hs = []
ds = [[], [], [], []]
for i in range(n):
	newA = [0, 0, 0, 0, 0]
	dsi = (list(map(int, input().split(' '))) + [0, 0, 0, 0, 0])[0:5]
	hs.append(dsi[0])
	for j in range(4):
		ds[j].append(dsi[j + 1])
hsTotal = sumM(hs)
total = 0
for di in range(4):
	p0 = sorted(zip(ds[di], hs))
	hsv = list(map(snd, p0))
	dsv = list(map(fst, p0))
	hsSum = 0
	s = 0
	for j in range(n - 1):
		hsSum += hsv[j]
		v = prodM([dsv[j + 1] - dsv[j], hsSum, hsTotal - hsSum])
		s += v
		s %= modval
	total += s
	total %= modval
print(total)


modval = 1000000009

def fst(a):
	return a[0]

def snd(a):
	return a[1]

def tail(a):
	return a[1:]

def prodM(a):
	t = 1
	for i in range(len(a)):
		t *= a[i]
		t %= modval
	return t

def sumM(a):
	t = 0
	for i in range(len(a)):
		t += a[i]
		t %= modval
	return t
(n, d) = map(int, input().split(' '))
hs = []
ds = [[], [], [], []]
for i in range(n):
	newA = [0, 0, 0, 0, 0]
	dsi = (list(map(int, input().split(' '))) + [0, 0, 0, 0, 0])[0:5]
	hs.append(dsi[0])
	for j in range(4):
		ds[j].append(dsi[j + 1])
hsTotal = sumM(hs)
total = 0
for di in range(4):
	p0 = sorted(zip(ds[di], hs))
	hsv = list(map(snd, p0))
	dsv = list(map(fst, p0))
	hsSum = 0
	s = 0
	for j in range(n - 1):
		hsSum += hsv[j]
		v = prodM([dsv[j + 1] - dsv[j], hsSum, hsTotal - hsSum])
		s += v
		s %= modval
	total += s
	total %= modval
print(total)


modval = 1000000009

def fst(a):
	return a[0]

def snd(a):
	return a[1]

def tail(a):
	return a[1:]

def prodM(a):
	t = 1
	for i in range(len(a)):
		t *= a[i]
		t %= modval
	return t

def sumM(a):
	t = 0
	for i in range(len(a)):
		t += a[i]
		t %= modval
	return t
(n, d) = map(int, input().split(' '))
hs = []
ds = [[], [], [], []]
for i in range(n):
	newA = [0, 0, 0, 0, 0]
	dsi = (list(map(int, input().split(' '))) + [0, 0, 0, 0, 0])[0:5]
	hs.append(dsi[0])
	for j in range(4):
		ds[j].append(dsi[j + 1])
hsTotal = sumM(hs)
total = 0
for di in range(4):
	p0 = sorted(zip(ds[di], hs))
	hsv = list(map(snd, p0))
	dsv = list(map(fst, p0))
	hsSum = 0
	s = 0
	for j in range(n - 1):
		hsSum += hsv[j]
		v = prodM([dsv[j + 1] - dsv[j], hsSum, hsTotal - hsSum])
		s += v
		s %= modval
	total += s
	total %= modval
print(total)


modval = 1000000009

def fst(a):
	return a[0]

def snd(a):
	return a[1]

def tail(a):
	return a[1:]

def prodM(a):
	t = 1
	for i in range(len(a)):
		t *= a[i]
		t %= modval
	return t

def sumM(a):
	t = 0
	for i in range(len(a)):
		t += a[i]
		t %= modval
	return t
(n, d) = map(int, input().split(' '))
hs = []
ds = [[], [], [], []]
for i in range(n):
	newA = [0, 0, 0, 0, 0]
	dsi = (list(map(int, input().split(' '))) + [0, 0, 0, 0, 0])[0:5]
	hs.append(dsi[0])
	for j in range(4):
		ds[j].append(dsi[j + 1])
hsTotal = sumM(hs)
total = 0
for di in range(4):
	p0 = sorted(zip(ds[di], hs))
	hsv = list(map(snd, p0))
	dsv = list(map(fst, p0))
	hsSum = 0
	s = 0
	for j in range(n - 1):
		hsSum += hsv[j]
		v = prodM([dsv[j + 1] - dsv[j], hsSum, hsTotal - hsSum])
		s += v
		s %= modval
	total += s
	total %= modval
print(total)


modval = 1000000009

def fst(a):
	return a[0]

def snd(a):
	return a[1]

def tail(a):
	return a[1:]

def prodM(a):
	t = 1
	for i in range(len(a)):
		t *= a[i]
		t %= modval
	return t

def sumM(a):
	t = 0
	for i in range(len(a)):
		t += a[i]
		t %= modval
	return t
(n, d) = map(int, input().split(' '))
hs = []
ds = [[], [], [], []]
for i in range(n):
	newA = [0, 0, 0, 0, 0]
	dsi = (list(map(int, input().split(' '))) + [0, 0, 0, 0, 0])[0:5]
	hs.append(dsi[0])
	for j in range(4):
		ds[j].append(dsi[j + 1])
hsTotal = sumM(hs)
total = 0
for di in range(4):
	p0 = sorted(zip(ds[di], hs))
	hsv = list(map(snd, p0))
	dsv = list(map(fst, p0))
	hsSum = 0
	s = 0
	for j in range(n - 1):
		hsSum += hsv[j]
		v = prodM([dsv[j + 1] - dsv[j], hsSum, hsTotal - hsSum])
		s += v
		s %= modval
	total += s
	total %= modval
print(total)