SPRTD - Editorial

editorial
, , ,
1

PROBLEM LINK:

Code Battle: Philosopher’s Code- PHIL21TS

Author: Jaskaran Singh
Tester: Akshit Monga, Jaskaran Singh, Deepanshu Jindal
Editorialist: Deepanshu Jindal

DIFFICULTY:

Medium

PREREQUISITES:

DP, Recursion

PROBLEM:

We are given an array s of integers of length N. Let an operation lambda d[i] be defined as d[i]=max(s1,s2,...,si)−min(s1,s2,...,si).

We need to calculate the minimum value of d[1]+ d[2]+ d[3]+ ....+ d[n]

Note : Reordering of array is allowded.

QUICK EXPLANATION:

Sort the array. Try to write a recursive relation for finding minimum sum of d[p] for some valid array indexes i, j such that i \leq p \leq j < N. Optimize recursive solution using memo table.

EXPLANATION:

  1. As we can reorder the array, and everytime we need to find the difference between maximum and minimum element of array, so firstly we will sort this array.

  2. Create a memo table dp of size N * N. For any valid index i, j: dp[i][j] denotes the sum of minimum cost of operation lambda d[p] where i \leq p \leq j

  3. Hence, we can derive the recursive relation dp[i][j] = s[j] - s[i] +min(dp[i+1][j], dp[i][j-1])

COMPLEXITIES:

Time Complexity: O(N^2)
Auxillary Space Complexity: O(N^2)

SOLUTIONS:

Setter's Solution in python 
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0]*n
for i in range(n):
  dp[i] = [0]*n
for i in range(1, n):
  for j in range(n-i):
    dp[j][j+i] = min(dp[j][j+i-1], dp[j+1][j+i])+a[j+i]-a[j]
print(dp[0][n-1])
Tester's Solution in python 
'''Author- Akshit Monga'''
from sys import stdin, stdout
input = stdin.readline
t = 1
for _ in range(t):
  n=int(input())
  a=[int(x) for x in input().split()]
  a=sorted(a)
  dp = [[0 for j in range(n)] for i in range(n)]
  for l in range(n - 2, -1, -1):
    for r in range(l + 1, n):
      dp[l][r] = a[r] - a[l] + min(dp[l + 1][r], dp[l][r - 1])
  print(dp[0][n-1])
Solution in C++ 
#include<bits/stdc++.h>
using namespace std;

#define int long long
int dp[2005][2005];

void fast(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

int getMinCost(int i, int j, int a[]){
  if(i>j)return 0;
  if(i==j)return 0;
  if(dp[i][j] != -1) return dp[i][j];
  int a1 = getMinCost(i+1, j, a);
  int a2 = getMinCost(i, j-1, a);
  dp[i][j]=a[j] - a[i] + min(a1, a2);
  return dp[i][j];
}

 void solve(){
    memset(dp, -1, sizeof(dp));
    int n;
    cin>>n;
    int a[n];
    for(int i = 0;i < n; i++) cin>>a[i];
    sort(a, a+n);
    int ans = getMinCost(0, n-1, a);
    cout<<ans<<endl;
}

int32_t main() {
  fast();
  solve();
  return 0;
}