#### 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.
```

**See original problem statement here**

#### 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 learn html online and 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

## Solutions

#include#include 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

#includeusing namespace std; #define ll long long int main() { ll n; cin>>n; ll arr[n], sum = 0; for(ll i=0; i >a>>b; arr[i] = a-b; sum += b*n - a; } sort(arr, arr+n, greater ()); cout<

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

### Space Complexity

O(

`N`

) space is taken to maintain a`First`

`Part`

`Array`

.