The problem statement is described here.

The first impulse would be to calculate all the match revenues and then sum up… but it would be O(n^2) which isn’t good enough for the second subtask.

The key to the problem lies in an observation. Let’s consider an examples and then generalise it.

Let us take a different example than the given sample case.

4

3 10 7 5

Now the revenues for each match are :

10-5 +10-7 + 10-3 + 7-5 + 7-3 + 5-3 = 23

but wait that’s not what we will do… Look at it in the following manner :

10 * (3-0) + 7*(2-1) + 5*(1-2) + 3(0-3)

If you didn’t get the above expression, take all 10’s common in previous expression and similarly for all rest.

Now note that if we sort them the order is : 3 5 7 10

And Indices are 0 1 2 3

Thus more formally we may write :

Total revenue = ∑ {strength[i] * ( i – (n-i-1))} = ∑ {strength[i] * (2*i – n +1)}

This can be coded for a O(n+n log(n) ) = O(n log(2n)) solution which is sufficient for our purpose. Be wary that we need to sort the array first before we use the above logic.

Thus you should now be able to code it easily passing both the subtasks.

Happy Coding.

### Like this:

Like Loading...

*Related*