Let me describe my algorithm which got me an AC after 3 TLEs.
What exactly we are doing in this problem is: For all combinations of pairs of elements, we are adding up the absolute values of the differences between the elements of the pair. i.e. Consider the sample input
3 10 3 5
Ans (Take only absolute values) = (3-10) + (3-3) + (3-5) + (10-3) + (10-5) + (3-5) = 7 + 0 + 2 + 7 + 5 + 2 = 23
Notice that I have fixed 3, iterated through the remaining elements, found the differences and added them to Ans, then fixed 10, iterated through the remaining elements and so on till the last element
Unfortunately, N(N-1)/2 iterations are required for the above procedure, which wouldn’t be ok for the time limit.
Could we better it?
Let’s sort the array and repeat this procedure. After sorting, the sample input is now
3 3 5 10
Let’s start by fixing the greatest element, 10 and iterating through the array like how we did before (of course, the time complexity is the same)
Ans = (10-3) + (10-3) + (10-5) + (5-3) + (5-3) + (3-3) = 7 + 7 + 5 + 2 + 2 = 23
We could rearrange the above as
Ans = (10)(3)-(3+3+5) + 5(2) - (3+3) + 3(1) - (3)
Notice a pattern? Let’s generalize it.
Suppose we have an array of strengths arr[N] of size N indexed from 0
Ans = (arr[N-1])(N-1) - (arr + arr + … + arr[N-2]) + (arr[N-2])(N-2) - (arr + arr + arr[N-3]) + (arr[N-3])(N-3) - (arr + arr + arr[N-4]) + … and so on
Right. So let’s put this new idea to work. We’ll introduce a ‘sum’ variable. Some basic DP to the rescue.
For i=0 to N-1
sum = sum + arr[i]
Ans = Ans + (arr[i+1]*(i+1)-sum)
That’s it, you just have to sort the array and iterate only once through it. Excluding the sorting part, it’s down to N iterations from N(N-1)/2, I suppose that’s called O(N) time EDIT: That is O(N log N) time overall
Hope it helped!