Problem p02804 (python)

Fixed submission:
import time
MOD =  1000000007
MOD2 = 1000000005
MAX = 100001

facs = [1 for _ in range(MAX)]
inv = [1 for _ in range(MAX)]


for i in range(1, MAX):
	facs[i] = (facs[i-1] * i) % MOD

for i in range(1, MAX):
	inv[i] = pow(facs[i], MOD2, MOD)


def get_facs(x):
	return facs[x]


def get_inv(x):
	return inv[x]

def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0
	r = (get_facs(n)*get_inv(k)) % MOD
	r = (r*get_inv(n-k)) % MOD
	return r



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return abs(numbers[0] - numbers[-1])

	score = 0
	for i, x in enumerate(numbers):
		score += ((choose(i, K-1) - choose(N-1-i, K-1)) * x)

	return score%MOD
	
	
print(main())

Buggy submission (verdict: Runtime Error):
import time

# success
# https://atcoder.jp/contests/abc151/tasks/abc151_e
# https://blogarithms.github.io/articles/2019-01/fermats-theorem


MOD =  1000000007
MOD2 = 1000000005
MAX = 100001

facs = [1 for _ in range(MAX)]



"""for i in range(1, MAX):
	facs[i] = (facs[i-1] * i) % MOD"""


def get_facs(n, k):
	if k<n-k:
		k = n-k
	r = 1
	for i in range(k+1, n+1):
		r *= i
	for i in range(2, n-k+1):
		r /= i
	return r

def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0
	return get_facs(n, k)



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return abs(numbers[0] - numbers[-1])

	score = 0
	for i, x in enumerate(numbers):
		score += ((choose(i, K-1) - choose(N-1-i, K-1)) * x)

	return int(score%MOD)
	
	
print(main())

Buggy submission (verdict: Runtime Error):
import time
MOD =  1000000007
MOD2 = 1000000005

facs = [1 for _ in range(50001)]
inv = [1 for _ in range(50001)]


for i in range(1, 50001):
	facs[i] = (facs[i-1] * i) % MOD

for i in range(1, 50001):
	inv[i] = pow(facs[i], MOD2, MOD)


def get_facs(x):
	return facs[x]


def get_inv(x):
	return inv[x]

def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0
	r = (get_facs(n)*get_inv(k)) % MOD
	r = (r*get_inv(n-k)) % MOD
	return r



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]

	score = 0
	for i, x in enumerate(numbers):
		s = ((choose(i, K-1) - choose(N-1-i, K-1)) * x)
		score = int((score+s))

	return int(score%MOD)
	
	
print(main())

Buggy submission (verdict: Runtime Error):
import time
MOD =  1000000007
MOD2 = 1000000005

facs = [1 for _ in range(50001)]
inv = [1 for _ in range(50001)]


for i in range(1, 50001):
	facs[i] = (facs[i-1] * i) % MOD

for i in range(1, 50001):
	inv[i] = pow(facs[i], MOD2, MOD)


def get_facs(x):
	return facs[x]


def get_inv(x):
	return inv[x]

def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0
	r = (get_facs(n)*get_inv(k)) % MOD
	r = (r*get_inv(n-k)) % MOD
	print(n, k, r)
	return r



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]

	score = 0
	for i, x in enumerate(numbers):
		s = ((choose(i, K-1) - choose(N-1-i, K-1)) * x)
		score = int((score+s))

	return int(score%MOD)
	
	
print(main())

Buggy submission (verdict: Runtime Error):
MOD = 1000000007
MOD2 = 1000000005

facs = [1 for _ in range(50001)]
inv = [1 for _ in range(50001)]


for i in range(1, 50001):
	facs[i] = (facs[i-1] * i) % MOD
	inv[i] = pow(i, MOD2, MOD)

# print(facs[:10])
# print(inv[:10])


def choose(n, k):
	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	r = (facs[n]*inv[k]) % MOD
	r = (r*inv[n-k]) % MOD
	# print(r)
	return r



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]

	score = 0
	for i, x in enumerate(numbers):
		s = ((choose(i, K-1) - choose(N-1-i, K-1)) * x)
		score = int((score+s))

	return int(score%MOD)
	
	
print(main())

Buggy submission (verdict: Runtime Error):
MOD = 1000000007
MOD2 = 1000000005

facs = [1 for _ in range(50001)]
inv = [1 for _ in range(50001)]


for i in range(1, 50001):
	facs[i] = (facs[i-1] * i) % MOD
	inv[i] = pow(i, MOD2, MOD)

print(facs[:10])
print(inv[:10])


def choose(n, k):
	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	r = (facs[n]*inv[k]) % MOD
	r = (r*inv[n-k]) % MOD
	print(r)
	return r



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]

	score = 0
	for i, x in enumerate(numbers):
		s = ((choose(i, K-1) - choose(N-1-i, K-1)) * x)
		score = int((score+s))

	return int(score%MOD)
	
	
print(main())

Buggy submission (verdict: Runtime Error):
MOD = 1e9 + 7

facs = [0 for _ in range(50009)]
facs[1] = 1
for i in range(2, 50009):
	facs[i] = (facs[i-1] * i) % MOD


def choose(n, k):
	if k==1:
		return n
	if n==0:
		return 0
	if n==k:
		return 1
	try:
		return int((facs[n]/facs[k]/facs[n-k]) % MOD)
	except ZeroDivisionError:
		print(n, k)

def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]

	score = 0
	for i, x in enumerate(numbers):
		score = (score + (choose(i, K-1) - choose(N-1-i, K-1)) * x) % MOD

	return int(round(score))
	
	
print(main())

Buggy submission (verdict: Runtime Error):
MOD = 1e9 + 7

facs = [0 for _ in range(50009)]
facs[1] = 1
for i in range(2, 50009):
	facs[i] = (facs[i-1] * i) % MOD


def choose(n, k):
	if k==1:
		return n
	if n==0:
		return 0
	return facs[n]/facs[k]/facs[n-k]

def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]

	score = 0
	for i, x in enumerate(numbers):
		score = (score + (choose(i, K-1) - choose(N-1-i, K-1)) * x) % MOD

	return int(score)
	
	
print(main())

Buggy submission (verdict: Runtime Error):
MOD = 1e9 + 7

def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]

	table = calculate_table(N+1)
	
	n, k = N-1, K-1
	total, x = 0, n
	while x >= k:
		res = search(numbers[n-x], x-1, k-1, numbers, table)
		total = (total + res) % MOD
		x -= 1

	return total

	
	
def search(minimum, n, k, numbers, table):
	total, x = 0, n
	while x >= k:
		total = (get_table(x, k, table) * (numbers[x-n-1]-minimum) + total) % MOD
		x -= 1
	

	return total


def calculate_table(n0):
	table = [[1], [1, 1]]

	for n in range(2, n0):
		table.append([1 if i==0 or i==n else table[n-1][i-1]+table[n-1][i] for i in range(n+1)])
	
	return table

def get_table(n, k, table):
	return table[n][k]
	
	

print(int(main()))

Buggy submission (verdict: Runtime Error):
MOD = 1e9 + 7
OO = False

def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]


	global table
	table = calculate_table(N+1)
	for i in table:
		if OO: print(i)
	
	n, k = N-1, K-1
	total, x = 0, n
	while x >= k:
		res = search(numbers[n-x], x-1, k-1, numbers)
		if OO: print(f"x: {x} and res: {res}")
		total = (total + res)
		x -= 1

	return total

	
	


def search(minimum, n, k, numbers):
	total, x = 0, n
	while x >= k:
		total = (get_table(x, k) * (numbers[x-n-1]-minimum) + total)
		x -= 1
	
	if OO: print(f"min: {minimum} and n: {n} and k: {k} and total: {total}")
	return total


def calculate_table(n0):
	table = [[1], [1, 1]]

	for n in range(2, n0):
		table.append([1 if i==0 or i==n else table[n-1][i-1]+table[n-1][i] for i in range(n+1)])
	
	return table

def get_table(n, k):
	return table[n][k]
	
	

print(main())

Buggy submission (verdict: Runtime Error):
MOD = 1e9 + 7
OO = False

def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]


	global table
	table = calculate_table(N+1)
	for i in table:
		if OO: print(i)
	
	n, k = N-1, K-1
	total, x = 0, n
	while x >= k:
		res = search(numbers[n-x], x-1, k-1, numbers)
		if OO: print(f"x: {x} and res: {res}")
		total = (total + res)
		x -= 1

	return total

	
	


def search(minimum, n, k, numbers):
	total, x = 0, n
	while x >= k:
		total = (get_table(x, k) * (numbers[x-n-1]-minimum) + total)
		x -= 1
	
	if OO: print(f"min: {minimum} and n: {n} and k: {k} and total: {total}")
	return total


def calculate_table(n0):
	table = [[1], [1, 1]]

	for n in range(2, n0):
		table.append([1 if i==0 or i==n else table[n-1][i-1]+table[n-1][i] for i in range(n+1)])
	
	return table

def get_table(n, k):
	return table[n][k]
	
	

print(main())