Help me to optimise this

https://www.codechef.com/submit/NOMATCH
https://www.codechef.com/viewsolution/34748584

bro what you have to do is just sort the array and take the diff of first and last element then 2nd and 2nd last element and so on.
https://www.codechef.com/viewsolution/34750375

1 Like

Using next permutation would be too slow for this problem I think. A better solution would be to note that if you want the maximum absolute difference, then the ideal solution would be to take the difference of biggest and smallest elements, since the ideal permutation would be to pair the biggest numbers with the smallest numbers.

Example: {1,-3,2,-3} would be paired as {-3,2,-3,1} giving |-3-2| + |-3-1| = 9

You can use sorting and just take the absolute difference of the smallest and biggest elements. Refer to my solution below if you still have any doubt!

https://www.codechef.com/viewsolution/34750131

1 Like

On top of that, using next_permutation this way will also land on a WA. You are not considering permutations that occur before the given permutation. To use next_permutation and solve this problem, you have to sort the array first to go through all permutations.

Of course this will give you TLE, but it’s at least right. (Just putting it out there so you don’t make this mistake while using next_permutation).

1 Like

I couldn’t get you what u mean by ‘not considering permutations that occur before the given permutation’ .can u explain with an example.

Consider the given array: A = 5\; 4\; 3\; 2\; 1. Then there is no next permutation for this. This is the last permutation. So you’ll just be considering this array for calulating S.

got it