# MAXFUN - Editorial

Author: Daanish Mahajan
Testers: Felipe Mota and Radoslav Dimitrov
Editorialist: Vichitr Gandas

Cakewalk

# PREREQUISITES:

Observations, Algebra

# PROBLEM:

Given a sequence A_1,A_2,…,A_N. Find the maximum value of the expression |A_x−A_y|+|A_y−A_z|+|A_z−A_x| over all triples of pairwise distinct valid indices (x,y,z).

# QUICK EXPLANATION

Find maximum and minimum element of the given sequence. Answer is always 2*(A_{max} - A_{min}).

# EXPLANATION

As N \le 500, Brute force solution should pass for subtask 1. Iterate over all possible triplets, compute the value of the expression and take maximum of all.

Pseudocode
ans = 0
for x in range(0, n):
for y in range(x+1, n):
for z in range(y+1, n):
value = abs(A[x] - A[y]) + abs(A[y] - A[z]) + abs(A[z] - A[x])
ans = max(ans, value)
print(ans)


Time Complexity: \mathcal{O}(N^3) for iterating over all triples.
Space Complexity: \mathcal{O}(1).
Note: the ans might overflow int in C++. Use long long int instead.

The above solution won’t pass for subtask 2 because N \le 10^5. The answer is always 2*(A_{max} - A_{min}). Lets prove!
Let the three chosen numbers be A_x, A_y, A_z such that A_x \le A_y \le A_z.
Here |A_x−A_y|=-(A_x-A_y) because A_x-A_y \le 0.
Similarly |A_y−A_z|=-(A_y-A_z) and |A_z−A_x|=(A_z-A_x).
Now the expression is,
|A_x−A_y|+|A_y−A_z|+|A_z−A_x|
=-(A_x-A_y)-(A_y-A_z)+(A_z-A_x)
=A_y-A_x+A_z-A_y+A_z-A_x
=2*A_z - 2*A_x
=2*(A_z-A_x)

To maximize the expression 2*(A_z-A_x), A_z should be maximum possible and A_x should be minimum possible. Hence for maximum value of the expression,
A_z = A_{max} and A_x = A_{min}.

Similarly you can consider other cases and prove the same.

Alternate(Geometrical) Approach:
Think all N integers as 1D points on number line. Now if we take any three points A_x, A_y and A_z as shown in below figure

See that clearly expression |A_x−A_y|+|A_y−A_z|+|A_z−A_x| = 2*|A_z-A_x|. Now to maximize, we should choose A_x = A_{min} and A_z = A_{max}.

Time Complexity: \mathcal{O}(N) for finding maximum and minimum element of the sequence.
Space Complexity: \mathcal{O}(1).

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

const int minv = -1e9, maxv = 1e9, maxt = 5, maxn[2] = {100000, 500};
vector<long long int> v;
void solve0(int n){
sort(v.begin(), v.end());
long long int ans = 2 * (v[n - 1] - v[0]);
cout << ans << endl;
}
void solve1(int n){
long long int ans = -1;
for(int i = 0; i < n - 2; i++){
for(int j = i + 1; j < n - 1; j++){
for(int k = j + 1; k < n; k++){
ans = max(ans, abs(v[i] - v[j]) + abs(v[j] - v[k]) + abs(v[k] - v[i]));
}
}
}
cout << ans << endl;
}
int main()
{
int t; cin >> t;
for(int i = 0; i < t; i++){
v.clear();
int n, x; cin >> n;
for(int i = 0; i < n; i++){
cin >> x;
v.push_back(x);
}
if(n <= maxn[1]){
solve1(n);
}else{
solve0(n);
}
}
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
while(t--){
vector<int> a(n);
for(int i = 0; i < n; i++){
if(i != n - 1) a[i] = readIntSp(-1'000'000'000, 1'000'000'000);
}
sort(a.begin(), a.end());
long long ans = 0;
for(int i = 1; i + 1 < n; i++){
ans = max(ans, (long long)(a[i] - a[0]) + (a.back() - a[i]) + a.back() - a[0]);
}
cout << ans << '\n';
}
return 0;
}


Editorialist's Solution
/***************************************************

@author: vichitr
Compiled On: 06 Feb 2021

*****************************************************/
#include<bits/stdc++.h>
using namespace std;

void solve(){
int n; cin >> n;
int a[n];
for(int i = 0; i < n; i++)
cin >> a[i];
int minElement = a[0];
int maxElement = a[0];
for(int i = 1; i < n; i++){
minElement = min(minElement, a[i]);
maxElement = max(maxElement, a[i]);
}
long long int ans = 2LL * (maxElement - minElement);
cout << ans <<'\n';
}

signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1;
cin >> t;
for(int i = 1; i <= t; i++)
{
solve();
}
return 0;
}


# VIDEO EDITORIAL:

2 Likes

long long int ans = 2LL * (maxElement - minElement);

What does the LL indicates??
This was in editorialist’s solution

LL stands for long long , which is data type to store large integers

1 Like

so why LL needs in 2?
It is already there in –
long long int ans

why do we need extra? Please explain;

We are storing in long long. But first just to calculate also, it should be a long long. Notice that (maxElement-minElement) is an integer but multiplying it with 2 might overflow int, hence i have used 2LL so that multiplication 2 * (maxElement - minElement) is also long long.

2 Likes

Thanks

In the setter’s solution, why are we using another function for cases in which n<=500?
Can’t this case be managed by the function solve0() itself?
Do we always need to solve all the subtasks separately?

What are the test cases ? I did just that and the given input yields correct output but on submission it still shows W.A.

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

int main()
{
int T;
cin >> T;
cin >> ws;
for(int j = 0; j<T;j++)
{
unsigned int n;
cin >> n;
cin >> ws;
unsigned int a[n];
for(unsigned int i = 0; i<n; i++)
{
unsigned int f;
cin >> f;
cin >> ws;
a[i] = f;
}
sort(a,a + n);
long long int ans = 2*(a[n-1]-a[0]);
cout << ans << endl;
}
}


This wasn’t accepted. What did i do wrong?

@xlazer array elements can be negative too. Why did you take unsigned? Also take a case where a[n-1] = INTMAX and a[0] = INTMIN. Your expression 2*(a[n-1]-a[0]) will overflow int. making it 2ll*(a[n-1]-a[0]) should work.

1 Like

Yes thanks! It’s working

Sam getting correct with the given test case and I got only 30 points
#include <stdio.h>

int main(void) {
int t,a[10000],N;
long int mx,mn;
scanf("%d",&t);
while(t<=5&&t>=1)
{scanf("%d",&N);
if(N<=500&&N>0)
{for(int i=0;i<N;i++)
{scanf("%ld",&a[i]);}
mx=a[0];mn=a[0];
for(int i=0;i<N;i++){
if(a[i]>mx)
mx=a[i];
if(a[i]<mn)
mn=a[i];

}}
printf("%ld\n",2*(mx-mn));
t--;}return 0;}

@surya_2002 because you are solving only subtask1 and that’s 30 points.

this condition is only for subtask1.

no but my logic and execution is correct right so why can’t I get remaining 70 points??

No, you can’t because you are not finding any solution for N > 500.

can u give me test cases??
actually N<=500 in the constraint
and also N must not be greater than 500

brooo
pls clarify my doubt

@surya_2002
Dude, thats subtask-1, and that is for 30 points only.

See the constraints & subtasks section in the problem.

### Constraints

• 1≤T≤5
• 3≤N≤10^5
• |A_i|≤10^9| for each valid i

Subtask #2 (70 points): original constraints

See the subtask 2 is original constraints which is 3≤N≤10^5. So for all these cases, value of N can be upto 10^5. And in this case, you are not finding any solution hence not getting those 70 points.

ok thanx ill try again…

Kindly point out the bug in this code. It’s not passing either of the subtasks. Thanks in advance!

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// Take input of testCases and start loop
Scanner scan = new Scanner (System.in);
int testCases = scan.nextInt();
for (int j=0; j<testCases; j++){
scan.nextLine();
// Take input of list of numbers and store in arr
int arrSize =scan.nextInt();
scan.nextLine();
int[] arr = new int[arrSize];
for (int i=0; i<arrSize; i++){
arr[i]=scan.nextInt();
}
Arrays.sort(arr);
// find max and min
int min=arr[0];
int max=arr[arrSize-1];
// Print 2 * max-min
System.out.println(Math.abs(2*(max-min)));
}
}
}