PROBLEM LINK:
Author: mehul_dholiya
Tester: abdullah768
Editorialist: mehul_dholiya
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Maths
PROBLEM:
We have to arrange the satellites according to their heights such as the total sum S of differences of heights of adjacent satellites is maximum.
QUICK EXPLANATION:
By using this *((N-1)N) / 2 - 1 + N/2. formula we can calculate the total Maximum sum S.
EXPLANATION:
Let’s take an example, and try to build the permutation with the maximum Permutation Sum for N = 5. We will take a Greedy-like approach, and choose at each step for the next element of the permutation the element which will give us the biggest difference. - for the first step we will have to choose the pair of elements with the biggest difference. It is 1,5 (or 5,1, but now we will take 1,5) with a difference of 4. So, the permutation so far is 1,5. - Now we have to choose the next value, out of 2,3,4. In order to have the biggest difference we will choose 2. So, the permutation is now: 1,5,2 - Next, we have to choose from 3 and 4, and we will choose 4 (it gives a bigger difference). The permutation is now: 1,5,2,4 - We only have the number 3 left, so we will add it to the end of the permutation. So, the solution provided by a Greedy-like approach is 1,5,2,4,3.
The Permutation Sum for the 1,5,2,4,3 permutation is 4+3+2+1 = 10 And if we think of a general solution, we can always create a permutation which looks like: 1, N, 2, (N-1), 3, (N-2), … . For such permutations the Permutation Sum is (N-1) + (N-2) + (N-3) + … + 2 + 1. For computing such sums we have a formula, the result is ((N-1) * N) / 2.
Is ((N-1) * N)/2 the correct solution? Not exactly. Let’s return a little to our example with N = 5, and the permutation: 1,5,2,4,3. At the last step, we added the number 3 to the permutation. With this number, we increased our Permutation Sum with the value of 1 only. We can notice that adding the number 3 at the beginning of the permutation and not at the end, we can increase our Permutation Sum. So, the final version is 3,1,5,2,4, with a Permutation Sum of 2 + 4 + 3 + 2 = 11. And this is the logic that gives us the final, correct, solution. You start the permutation with the number N / 2 (or N/2 + 1 if N is odd) and after that you continue with 1, N, 2, (N-1),… . How does this influence the value of the Permutation Sum? Well, first we no longer have the + 1 at the end of the sum, because we removed the last element, but instead we have an extra N/2.
We can still use the previous formula ((N-1)* N) / 2, but now we have to subtract that 1 that no longer is at the end of the sum and we have to add N/2. So, the final formula of the solution is: ((N-1)*N) / 2 - 1 + N/2.
One more thing to check is what result the formula gives us for small numbers. - For N = 1 we will have 01 / 2 - 1 + 0, which is -1. Not correct. - For N = 2 we will have 12/2 - 1 + 1, which is 1. Correct. - For N = 3 we will have 2*3/2 - 1 + 1, which is 3. Correct. So the only problem is with N = 1, this should be checked separately.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution solution
Tester’s solution solution