Minimum Dissatisfaction

Concepts Used

Sorting, Mathematics

Difficulty Level

Hard

Problem Statement (Simplified):

For a given of N students, we are given two values P_{i} and Q_{i}. Find the minimum possible sum of P_{i}(j-1) + Q_{i}(N-j) for all students where j will be any position of student where sum is minimum. We have to rearrange students such that we recieve the minimum sum.

Test case

    Input:
    4
    2 4
    3 3
    7 1
    2 3

    Output:
    25

    Explanation:
    In the given example it is optimal to put Student in this order: (4,2,1,3).

    The first person is in the position of 4, then his dissatisfaction will be equal to 2∗(4−1)+4∗(4−4)=6.
    The second person is in the position of 2, then his dissatisfaction will be equal to 3∗(2−1)+3∗(4−2)=9.
    The third person is in the position of 1, then his dissatisfaction will be equal to 7∗(1−1)+1∗(4−1)=3.
    The fourth person is in the position of 3, then his dissatisfaction will be equal to 2∗(3−1)+3∗(4−3)=7.
    The total dissatisfaction will be 6+9+3+7=25.

Solving Approach :

Bruteforce Approach:

1) We can rearrange all students in different arrangements, for each arrangement we calculate P_{i}(j-1) + Q_{i}(N-j) value for each student and find sum for all students. Then we print the maximum sum possible from all arrangements.
2) This approach takes O(N!) time to arrange all students in different possible arrangements, also it takes O(N) to find total sum for each possible arrangements.
3) We can see this approach is highly inefficient and cannot solve problem in given time. So we use mathematics to solve this problem.

Efficient Approach:

1) Let’s focus on the formula to use here that is P_{i}(j-1) + Q_{i}(N-j), if we break this formula,
(P_{i}\times j) - P_{i} + (Q_{i}\times N) - (Q_{i}\times j))
We take terms containing j as common term,
(P_{i}-Q_{i})\times j + (Q_{i}\times N) - P_{i}
2) As we know (Q_{i}\times N - P_{i}) is constant and does not depend on any external factor, so we’ll count this right at the time of input and add this in final sum.
3) First part that is (P_{i}-Q_{i})\times j have one unknown variable i.e. j, where j will be the final position after rearranging stdents. We can minimize this whole part if (P_{i}-Q_{i}) is max imum and j is minimum, so we maintain an array the sort the array (P_{i}-Q_{i}) for this part. We sort the array in a non-increasing order, so that first index of array contains largest value possible for (P_{i}-Q_{i}).
4) After sorting we add all the values of (P_{i}-Q_{i})\times (index+1) where index is the index at which (P_{i}-Q_{i}) lies.

Example

Lets assume values to be the ones given in test case i.e.
4
2 4
3 3
7 1
2 3
First we find the sum of (Q_{i}\times N - P_{i}) for all students and then store in a sum variable.

For student 1:
(Q_{i}\times N - P_{i})
(4\times 4 - 2)
(16 - 2)
14
sum = 14

For student 2:
(Q_{i}\times N - P_{i})
(3\times 4 - 3)
(12 - 3)
9
sum = 14+9
sum = 23

For student 3:
(Q_{i}\times N - P_{i})
(1\times 4 - 7)
(4 - 7)
-3
sum = 23+(-3)
sum=20

For student 4:
(Q_{i}\times N - P_{i})
(3\times 4 - 2)
(12 - 2)
10
sum = 20+10
sum = 30

As we have covered the second part, we now calculate the first part i.e. (P_{i}-Q_{i}) for all students and store these values in a array A,

For student 1:
(P_{i}-Q_{i})
(2-4)
-2
A = [-2]

For student 2:
(P_{i}-Q_{i})
(3-3)
0
A = [-2,0]

For student 3:
(P_{i}-Q_{i})
(7-1)
6
A = [-2,0,6]

For student 4:
(P_{i}-Q_{i})
(2-3)
-1
A = [-2,0,6,-1]

Now, we have got array A as [-2,0,6,-1], we sort this array in non-decreasing order which makes current array as [6,0,-1,-2], thus we add A[i]\times(i+1) into sum, so
sum = 30 + (6\times1) + (0\times2) + (-1\times3) + (-2\times4))
sum = 30 + (6) + (0) + (-3) + (-8)
sum = 30 - 5
sum = 25

Hence both parts has been calculated, we print the final sum i.e. 25.

Video Explanation

MINDSTF Explanation (Youtube)

Solutions

#include <stdio.h>
#include<stdlib.h>

long long compare(const void * a, const void * b) 
{ 
    return ( *(long long*)b - *(long long*)a ); 
} 

int main()
{
    long long n;
    scanf("%lld",&n);
    long long arr[n], sum = 0;
    for(long long i=0; i<n; i++)
    {
        long long int a,b;
      scanf("%lld %lld",&a,&b);
        arr[i] = a-b;
        sum += b*n - a;
    }

    qsort((void*)arr, n, sizeof(arr[0]), compare); 

    for(long long i=0; i<n; i++)
        sum += arr[i]*(i+1);

    printf("%lld",sum);
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    ll n;
    cin>>n;
    ll arr[n], sum = 0;
    for(ll i=0; i<n; i++)
    {
        ll int a,b;
        cin>>a>>b;
        arr[i] = a-b;
        sum += b*n - a;
    }

    sort(arr, arr+n, greater<ll>());

  cout<<endl;
    for(ll i=0; i<n; i++)
        sum += arr[i]*(i+1);

    cout<<sum;

    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
      long arr[]= new long[n];
      long sum = 0;
      for(int i=0; i<n; i++)
      {
          long a = sc.nextLong(),b = sc.nextLong();
          arr[i] = a-b;
          sum += b*n - a;
      }

    Arrays.sort(arr,0,n);

    int i, k;
    long t;
      for (i = 0; i < n / 2; i++) { 
          t = arr[i]; 
          arr[i] = arr[n - i - 1]; 
          arr[n - i - 1] = t; 
        } 

    for(i=0; i<n; i++)
          sum += arr[i]*(i+1);

    System.out.println(sum);
  }
}

n = int(input())
arr = []
sum = 0

for i in range(n):
	
	a, b = map(int, input().split())
	arr.append(a - b)
	sum += b * n - a

arr.sort(reverse = True)

for i in range(n):
	sum += arr[i] * (i + 1)

print(sum)

Space Complexity
O(N) space is taken to maintain a First Part Array.

[forminator_quiz id="1316"]

This article tried to discuss the concept of Sorting, Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting, Mathematics you can check out .