Minimum Loss

Optimized Approach(Maths + Sorting):

We can see that we need to calculate the minimum loss of P_i*(j-1) + Q_i(N-j) for all student i standing at position j.  Let’s Simplify this equation : 

R = P_i*(j-1) + Q_i(N-j)

R = P_i*j - P_i + Q_i*N - Q_i*j 

Taking j common from P_i*j - Q_i*j

R = j(P_i-Q_i) + (Q_i*N - P_i)

Let x = Q_i*N - P_i

Let y = j(P_i-Q_i)

We can clearly see that Q_i*N - P_i is constant for any student, i. We can directly add this part into our total loss. 

So our main aim is to minimize the value of (Q_i-P_i)*j. Since (Q_i-P_i) is also fixed for any student i, so to minimize the x we need to multiply the highest value of (Q_i-P_i) for any i, with the smallest j, and similarly second highest value of (Q_iP_i) with the second smallest j. We can achieve this by calculating (Q_i-P_i) for every i, then sorting them in ascending order. 

Finally, We will calculate the result of (P_i-Q_i)*j + (Q_i*N - P_i), and sum them for all values i. It is guaranteed that this will be the smallest possible value of the total loss. 

Let’s Dry run for the above sample test case. 

4

2 4

3 3

7 1

2 3

Let’s denote X = Q_i*N - P_i and Y = P_i-Q_i, we will calculate x and y for each and every student, starting with student 1. Let say totalLoss = 0 holds the final Output, We will add the value of X into the total sum as X is constant in nature. 

For Student 1:

P_i = 2, Q_i = 4 

X = Q_i*N - P_i = (4*4 - 2) = 14

Y =  P_i-Q_i = 2 - 4 = -2

totalLoss  = 0 + 14 

For Student 2:

P_i = 3, Q_i = 3 

X = Q_i*N - P_i = (3*4 - 3) = 9

Y =  P_i-Q_i = 3 - 3 = 0

totalLoss = 14 + 9 = 23

For student 3: 

P_i = 7, Q_i = 1 

X = Q_i*N - P_i = (1*4 - 7) = -3

Y =  P_i-Q_i = 7 - 1 = 6

totalLoss = 23 - 3 = 20 

For Student 4:

P_i = 2, Q_i = 3

X = Q_i*N - P_i = (3*4 - 2) = 10

Y =  P_i - Q_i = 2 - 3 = -1

TotalLoss = 20 + 10 = 30

Now we got the Y array as [-2,0,6,-1] and TotalLoss = 30. We will sort the array Y in descending order so that the highest value will be multiplied by the lowest j, after sorting the array will look like [6,0,-1,-2]. 

Now we will add Y*j into the total Sum. starting with j = 1

TotalLoss = 30 + (6*1) + (0*2) + (-1*3) + (-2*4) = 25. 

So minimum loss is 25. 

Now the logic should be clear, now let’s implement the above logic into the C++ code. 

Implementation in C++

// c++ code for finding the minimum loss
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    // this will store the value of p-q as explained above
    int Y[n];
    // it will store the sum of minimum loss
    int totalLoss = 0;
    for(int i=0;i<n;i++){
        int p,q;
        cin >> p >> q;
        Y[i] = p-q;
        // adding q*n - p into the total sum
        // because this is the constant part
        totalLoss += q*n - p;
    }
    // sorting the array that stores p-q in descending order
    sort(Y,Y+n,greater<int>());
    // adding (p-q)*j into the totalSum
    for(int j=0;j<n;j++){
        totalLoss += Y[j]*(j+1);
    }
    // printing the totalSum, which is minimum loss
    cout << totalLoss << endl;
}

Output: 

25

Complexity Analysis

Time Complexity: O(NlogN)

Explanation: (NlogN) is used for sorting the Y array into descending order. 

Space Complexity: O(N)

Explanation: It is used by Y array, for storing the value of {P-Q}. 

Frequently asked questions

Q1. Which sorting algorithm is used when we sort using STL? 

Ans. The sorting algorithm used in STL sort() is IntroSort. Introsort is a hybrid sorting algorithm that uses three sorting algorithms to minimize the running time. These algorithms are quicksort, Heapsort, and Insertion Sort.

Q2. What is the greedy approach? 

Ans. It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution. 

Q3. How many permutations if there are some identical elements? 

Ans. Repetitions in the array are taken care of by dividing the permutation by the factorial of identical objects. 

Key takeaways

In this article, we discussed the problem of finding the minimum sum under the given constraints. We discussed the two approaches, i.e., brute force and optimized approach using maths and sorting. We hope you understand the problem and solution properly. Now you can do more similar questions. 

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading. 

Until then, Keep Learning and Keep Coding.