The Sports Festival (Codeforces 1509C)
Tags: Greedy, dp

The student council is preparing for the relay race at the sports festival.The council consists of $$$n$$$ members. They will run one after the other in the race, the speed of member $$$i$$$ is $$$s_i$$$. The discrepancy $$$d_i$$$ of the $$$i$$$-th stage is the difference between the maximum and the minimum running speed among the first $$$i$$$ members who ran. Formally, if $$$a_i$$$ denotes the speed of the $$$i$$$-th member who participated in the race, then $$$d_i = \max(a_1, a_2, \dots, a_i) - \min(a_1, a_2, \dots, a_i)$$$.You want to minimize the sum of the discrepancies $$$d_1 + d_2 + \dots + d_n$$$. To do this, you are allowed to change the order in which the members run. What is the minimum possible sum that can be achieved?

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$)  — the number of members of the student council.The second line contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$)  – the running speeds of the members.

Output: Print a single integer  — the minimum possible value of $$$d_1 + d_2 + \dots + d_n$$$ after choosing the order of the members.

Note: In the first test case, we may choose to make the third member run first, followed by the first member, and finally the second. Thus $$$a_1 = 2$$$, $$$a_2 = 3$$$, and $$$a_3 = 1$$$. We have:  $$$d_1 = \max(2) - \min(2) = 2 - 2 = 0$$$.  $$$d_2 = \max(2, 3) - \min(2, 3) = 3 - 2 = 1$$$.  $$$d_3 = \max(2, 3, 1) - \min(2, 3, 1) = 3 - 1 = 2$$$. The resulting sum is $$$d_1 + d_2 + d_3 = 0 + 1 + 2 = 3$$$. It can be shown that it is impossible to achieve a smaller value.In the second test case, the only possible rearrangement gives $$$d_1 = 0$$$, so the minimum possible result is $$$0$$$.

Sample Inputs:
3
3 1 2

1
5

6
1 6 3 3 6 3

6
104 943872923 6589 889921234 1000000000 69

Sample Outputs:
3

0

11

2833800505

Solution (Python):
import sys
input = lambda : sys.stdin.readline().strip()
inf = 10 ** 20

def count(a):
    ans = 0
    dmin = 10 ** 20
    dmax = -10 ** 20
    for i in range(len(a)):
        dmin = max(dmin, a[i])
        dmax = min(dmax, a[i])
        d = dmax - dmin
        ans += d
    return ans

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    dp = []
    for i in range(n):
        dp.append([inf] * n)
        dp[i][i] = 0
    for sz in range(1, n):
        for j in range(sz, n):
            i = j - sz
            dp[i][j] = a[j] - a[i] + min(dp[i][j - 1], dp[i + 1][j])
    print(dp[0][n - 1])
f = 0
if f:
    for _ in range(int(input())):
        main()
else:
    main()

Solution (Python):
def main():
    N = int(input())
    a = list(map(float, input().split()))
    a.sort()
    dp = [0.0] * N ** 2
    for gap in range(1, N):
        for l in range(N - gap):
            r = l + gap
            dp[l * N + r] = a[r] - a[l] + min(dp[(l + 1) * N + r], dp[l * N + r - 1])
    return int(dp[N - 1])
try:
    ans = main()
    print(ans)
except Exception as e:
    print(e)
    traceback.print_exc()

Solution (Python):
def main():
    N = int(input())
    a = list(map(float, input().split()))
    a.sort()
    dp = [[0.0] * N for _ in range(N)]
    for gap in range(1, N):
        for l in range(N - gap):
            r = l + gap
            dp[l][r] = a[r] - a[l] + min(dp[l + 1][r], dp[l][r - 1])
    return int(dp[0][N - 1])
try:
    ans = main()
    print(ans)
except Exception as e:
    print(e)
    traceback.print_exc()