Sum of the two largest differences in the sorted array - 1934A

Explanation.txt

Let's understand the solution provided with an example and explanation:

Suppose we have an array with 4 elements: [1, 3, 5, 8]. We'll sort this array in ascending order: [1, 3, 5, 8].

Now, let's consider the possible cases for the given expression:

|a−b|+|b−c|+|c−d|+|d−a|
|a−b|+|b−d|+|d−c|+|c−a|
|a−c|+|c−b|+|b−d|+|d−a|
We can see that in each case, the sum of absolute differences includes all pairs of adjacent elements.

For the first case:

|1-3| + |3-5| + |5-8| + |8-1| = 2 + 2 + 3 + 7 = 14
For the second case:

|1-3| + |3-8| + |8-5| + |5-1| = 2 + 5 + 3 + 4 = 14
For the third case:

|1-5| + |5-3| + |3-8| + |8-1| = 4 + 2 + 5 + 7 = 18
Now, if we analyze the solutions, we can see that the third case provides the maximum value, which is 18.

Explanation of the solution:

We iterate through each test case.
We take the input array and sort it in ascending order.
Then, we compute the maximum value of the expression using the formula: 2 * (v[n - 1] - v[0]) + 2 * (v[n - 2] - v[1]).
Finally, we output the maximum value for each test case.

The Foumula Explanation:
Let's break down the formula step by step:

v[n - 1]: This represents the largest element in the sorted array. Since the array is sorted in ascending order, the last element (v[n - 1]) is the largest.
v[0]: This represents the smallest element in the sorted array. Similarly, since the array is sorted, the first element (v[0]) is the smallest.
(v[n - 1] - v[0]): This calculates the absolute difference between the largest and smallest elements in the array. This essentially represents the maximum possible difference between any two elements in the array.
v[n - 2]: This represents the second largest element in the sorted array.
v[1]: This represents the second smallest element in the sorted array.
(v[n - 2] - v[1]): This calculates the absolute difference between the second largest and second smallest elements in the array.
2 * (v[n - 1] - v[0]) + 2 * (v[n - 2] - v[1]): Finally, we multiply both differences by 2 and add them together. This is because each absolute difference term appears twice in the expression: once as |ai - aj| and once as |aj - ai|. Multiplying by 2 accounts for this repetition.
So, essentially, the formula calculates the sum of the two largest differences in the sorted array, accounting for the repetition of each difference term in the expression. This gives us the maximum possible value of the given expression for the array.

too-min-too-max-A.cpp

// author: remonhasan, Problem: 1934A (CF)
#include<bits/stdc++.h>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long
#define VI vector < int > v;
#define PI pair < int, int > p;
#define RAB(i, a, b) for (int i = a; i <= b; i++)
#define RSN(i, s, n) for (int i = 0; i < n; i++)
#define PB push_back
#define IS getline(cin, s);
#define nl cout << "\n";
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

void solve() {

  int n;  
  cin >> n;

  vector<int> a(n);
  RSN(i, s, n) cin >> a[i];
  sort(a.begin(), a.end());
  // sum of the two largest differences 
  cout << 2 * (a[n - 1] - a[0]) + 2 * (a[n - 2] - a[1]) << endl;
}

int main() {
  ios;
  int t;
  cin >> t;
  while (t--) {
    solve();
  }

  return 0;
}