Problem:


Score : 400 points

Problem Statement

You are given N integers; the i-th of them is A_i.
Find the maximum possible sum of the absolute differences between the adjacent elements after arranging these integers in a row in any order you like.

Constraints

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the maximum possible sum of the absolute differences between the adjacent elements after arranging the given integers in a row in any order you like.

Sample Input 1

5
6
8
1
2
3

Sample Output 1

21

When the integers are arranged as 3,8,1,6,2, the sum of the absolute differences between the adjacent elements is |3 - 8| + |8 - 1| + |1 - 6| + |6 - 2| = 21. This is the maximum possible sum.

Sample Input 2

6
3
1
4
1
5
9

Sample Output 2

25

Sample Input 3

3
5
5
1

Sample Output 3

8



Sample input:
5
6
8
1
2
3


Sample output:
21

Submission status: Runtime Error

Solution code:
import itertools


def main():
    n = int(input())

    a = []
    for i in range(n):
        a.append(int(input()))
    a.sort()
    if n == 2:
        print(abs(a[0] - a[1]))
        return
    if n == 3:
        tmp1 = abs(a[0] - a[1]) + abs(a[0] - a[2])
        tmp2 = abs(a[0] - a[2]) + abs(a[1] - a[2])
        print(max([tmp1, tmp2]))
        return
    if n < 10:
        ans = 0
        for a in itertools.permutations(a):
            tmp = 0
            for i in range(len(a) - 1):
                tmp += abs(a[i] - a[i + 1])
            ans = max([ans, tmp])
        print(ans)
        return
    ret1 = a[:n // 2 + (1 if n % 2 == 1 else 0)]
    ret2 = a[n // 2 + (1 if n % 2 == 1else 0):]
    ret1 = [ret1[-1]] + ret1[:-2] + [ret1[-2]]
    ret2 = ret2[1:] + [ret2[0]]
    ans = 0

    ans += abs(ret1[-1] - ret2[-1])
    for i in range(len(ret2) - 1):
        ans += abs(ret1[i] - ret2[i])
        ans += abs(ret1[i + 1] - ret2[i])
    if len(ret1) != len(ret2):
        ans += abs(ret1[-2] - ret2[-1])

    # if n % 2 == 0:
    #     print(ans)
    #     return
    ans1 = ans

    ret1 = a[:n // 2 + (0 if n % 2 == 1 else 1)]
    ret2 = a[n // 2 + (0 if n % 2 == 1else 1):]
    # ret1 = ret1[1:] + [ret1[0]]
    ret2 = [ret2[0]] + ret2[2:] + [ret2[1]]
    ans = 0

    ans += abs(ret1[-1] - ret2[-1])
    for i in range(len(ret1) - 1):
        ans += abs(ret2[i] - ret1[i])
        ans += abs(ret2[i + 1] - ret1[i])
    if len(ret1) != len(ret2):
        ans += abs(ret1[-1] - ret2[-2])
    print(max([ans, ans1]))


main()
7541

Submission status: Runtime Error

Solution code:
n = int(input())

a = []
for k in range(n):
    t = int(input())
    a.append(t)

a = np.sort(a)

m = []
nm = []
while True:
    if len(a)%2 == 0:
        break
    m.append(np.median(a))
    nm.append(sum(a==np.median(a)))
    a = a[a != np.median(a)]
    
m = list(reversed(m))
nm = list(reversed(nm))

b = []
for k in range(int(len(a)/2)):
    b.append(a[int(len(a)/2) - k - 1])
    b.append(a[-k-1])

for k in range(len(nm)):
    if nm[k] == 1:
        if len(b) > 1:
            if m[k] - b[0] > b[-1] - m[k]:
                b = [m[k]] + b
            else:
                b = b + [m[k]]
        else:
            b = [m[k]]
    else:
        b = [m[k]] + b + [m[k]]
print(int(np.sum(np.abs(np.diff(b)))))

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A=[int(input()) for x in range(N)]

    A.sort()
    s = 0
    e = N - 1
    L = A[0]
    R = A[e]
    ret1 = R - L
    while True:
        ss = s + 1
        ee = e + 1

        b = max(abs(L - A[ss]), abs(R - A[ss])) > max(abs(L - A[ee]), abs(R - A[ee]))

        if b:
            s += 1
            if abs(L - A[s]) < abs(R - A[s]):
                ret1 += abs(R - A[s])
                R = A[s]
            else:
                ret1 += abs(L - A[s])
                L = A[s]
        else:
            e -= 1
            if s == e: break
            if abs(L - A[e]) < abs(R - A[e]):
                ret1 += abs(R - A[e])
                R = A[e]
            else:
                ret1 += abs(L - A[e])
                L = A[e]
        if s == e: break

    # 出力
    print("{}".format(ret1))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():

    N = int(input())

    A.sort()
    s=0
    e=N-1
    L=A[0]
    R=A[e]
    ret1 = R-L
    while True:
        ss=s+1
        ee=e+1

        b=max(abs(L-A[s]),abs(R-A[s])) > max(abs(L-A[e]),abs(R-A[e]))

        if b:
            s+=1
            if abs(L-A[s]) < abs(R-A[s]):
                ret1 += abs(R-A[s])
                R=A[s]
            else:
                ret1 += abs(L-A[s])
                L=A[s]
        else:
            e-=1
            if s == e: break
            if abs(L-A[e]) < abs(R-A[e]):
                ret1 += abs(R-A[e])
                R=A[e]
            else:
                ret1 += abs(L-A[e])
                L=A[e]
        if s==e: break



    # 出力
    print("{}".format(ret1))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
A.sort()
ary1 = [A[0]]
ary2 = [A[N-1]]
fst = 0
lst = N
fst_flg = False
sum1, sum2 = 0,0
while fst + 1 < lst:
	if fst_flg:
		fst_flg = False
		if fst + 2 != lst:
			fst += 1
			ary1 = [A[fst]] + ary1 + [A[fst+1]]
			ary2 = [A[N-1-fst]] + ary2 + [A[N-1-fst-1]]
			fst += 1
			l = len(ary1)
			sum1 += abs(ary1[0]-ary1[1]) + abs(ary1[l-1]-ary1[l-2])
			sum2 += abs(ary2[0]-ary2[1]) + abs(ary2[l-1]-ary2[l-2])
		else:
			fst += 1
			ary1 = [A[fst]] + ary1
			ary2 = [A[N-1-fst]] + ary2
			sum1 += abs(ary1[0]-ary1[1])
			sum2 += abs(ary2[0]-ary2[1])
	else:
		fst_flg = True
		if fst + 2 != lst:
			lst -= 1
			ary1 = [A[lst]] + ary1 + [A[lst-1]]
			ary2 = [A[N-1-lst]] + ary2 + [A[N-lst]]
			lst -= 1
			sum1 += abs(ary1[0]-ary1[1]) + abs(ary1[l-1]-ary1[l-2])
			sum2 += abs(ary2[0]-ary2[1]) + abs(ary2[l-1]-ary2[l-2])
		else:
			lst -= 1
			ary1 = [A[lst]] + ary1
			ary2 = [A[N-1-lst]] + ary2
			sum1 += abs(ary1[0]-ary1[1])
			sum2 += abs(ary2[0]-ary2[1])
print(max(sum1,sum2))

Submission status: Runtime Error

Solution code:
    
N, = getIntList()
#print(N)
za = []
for i in range(N):
    a = input()
    a = int(a)
    za.append(a)

za.sort()

if N%2==0:
    t = N//2
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res = s1*2 - s0 *2  - za[t] + za[t-1]
else:
    t = N//2 + 1
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res0 = s1 *2 - s0*2 + za[t-1] + za[t-2]
    t = t - 1
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res1 = s1 *2 - s0*2 -  za[t] - za[t+1]
    res = max(res1, res0)

print(res)

Submission status: Runtime Error

Solution code:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        print(*args, **kwargs, file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)
za = []
for i in range(N):
    a = input()
    a = int(a)
    za.append(a)

za.sort()

if N%2==0:
    t = N//2
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res = s1*2 - s0 *2  - za[t] + za[t-1]
else:
    t = N//2 + 1
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res0 = s1 *2 - s0*2 + za[t-1] + za[t-2]
    t = t - 1
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res1 = s1 *2 - s0*2 -  za[t] - za[t+1]
    res = max(res1, res0)

print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2-1], A[N//2]
    del A[N // 2]
    del A[N // 2]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2], A[N//2+1]
    del A[N // 2]
    del A[N // 2]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)