MAXFUN - Editorial

PROBLEM LINK:

Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest

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

DIFFICULTY:

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

Subtask 1

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.

Subtask 2

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 readString(int l,int r,char endd){
	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){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = readIntLn(1, 5);
	while(t--){
		int n = readIntLn(1, 100000);
		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);
			else a[i] = readIntLn(-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?

1 Like

@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

could you please help me with my code
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 :sob: :sob:

@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

Subtasks

Subtask #1 (30 points): N≤500

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… :blush:

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)));
		}
	}
}