MXMTRIO - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: S.Manuj Nanthan
Tester: Nishank Suresh
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

Sorting

PROBLEM

You are given an array A containing N elements. For any ordered triplet (i, j, k) such that i, j, and k are pairwise distinct and 1 \le i, j, k \le N, the value of this triplet is (A_i-A_j)\cdot A_k. You need to find the maximum value among all possible ordered triplets.

Note: Two ordered triplets (a, b, c) and (d, e, f) are only equal when a = d and b = e and c = f. As an example, (1, 2, 3) and (2, 3, 1) are two different ordered triplets.

QUICK EXPLANATION

  • Sort the array A in increasing order.
  • The maximum possible value among all possible triplets is (A_N-A_1) * A_{N-1}.

EXPLANATION

The slow approach would be to iterate over all triplets and take maximum, but that would take O(N^3) time which won’t work.

Since we want to maximize the value of (A_i - A_j) * A_k, and all elements in A are positive, it is best to maximize both (A_i-A_j) and A_k. There are two options

  • Select largest and smallest element in A as A_i and A_j, and choose second maximum element in A as A_k. The value of trio is (A_N-A_1)*A_{N-1}
  • Choose the maximum element as A_k and choose the second maximum element, and the minimum element as A_i and A_j, getting a triplet of value (A_{N-1}-A_1)*A_N.

Since A_{N-1} \leq A_N, we can prove that (A_N-A_1)*A_{N-1} \geq (A_{N-1}-A_1)*A_N.

Hence, the maximum value we can obtain is (A_N-A_1)*A_{N-1} after sorting array A.

Bonus

  • What if A contains negative values as well?
  • Assume constraint i \lt j \lt k while choosing triplets. Can we still sort?

TIME COMPLEXITY

The time complexity is O(N*log(N)) per test case due to sorting.

SOLUTIONS

Setter's Solution
test_cases = int(input())
for _ in range(test_cases):
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    print(A[N-2]*(A[N-1]-A[0]))
Tester's Solution
for _ in range(int(input())):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    print((a[n-1] - a[0])*a[n-2])
Editorialist's Solution
import java.util.*;
import java.io.*;
class MXMTRIO{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        int[] A = new int[N];
        for(int i = 0; i< N; i++)A[i] = ni();
        Arrays.sort(A);
        long ans = Math.max(A[N-1] *(long) (A[N-2]-A[0]), A[N-2]*(long)(A[N-1]-A[0]));
        pn(ans);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new MXMTRIO().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

#include
#include
using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
int n,i,x;
cin>>n;
list l;
for(i=0;i<n;i++)
{
cin>>x;
l.push_back(x);
}
l.sort();
l.reverse();
list::iterator it=l.begin();
int a,b,c;
a=*it;
it++;
b=*it;
it=l.end();
it–;
c=*it;
//cout<<a<<" “<<b<<” “<<c<<”\n";
long long int r1,r2;
r1=(a-c)*b;
r2=(b-c)*a;
cout<<((r1>r2)?r1:r2)<<"\n";
}
return 0;
}

Pls help me to figure out my mistake.

1 Like

My code written below was returning WA for some sub-cases even though the algorithm used was same. Its honestly really frustrating, can someone please tell why this was returning WA, i couldn’t figure it man.


import java.util.*;
import java.io.*;
public class Main  {
    static FastReader in =  new FastReader();
    static final Random random=new Random();
    static long mod=1000000007L;
    static HashMap<String,Integer>map=new HashMap<>();
    
    
    static void solve() {
   	 StringBuilder st = new StringBuilder();
   	 int N = in.nextInt();
   	 int ar[] = new int[N];
   	 for(int i =0; i<N; i++){
   	     ar[i] = in.nextInt();
   	 }
    Arrays.sort(ar);
    long val1 = (ar[N-1]-ar[0]) * ar[N-2];
   	 print(val1);
   	 map.clear();
    }
    
 
    public static void main(String args[]) throws IOException {
        int t=in.nextInt();
        StringBuilder res=new StringBuilder();
        int cse=1;
        loop:
        while(t-->0)
        {
        	solve();
        }
 
    }
 

 
    static int max(int a, int b)
    {
        if(a<b)
        	return b;
        return a;
    }
 
 
    static void ruffleSort(int[] a) {
        int n=a.length;
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n), temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
 
    static < E > void print(E res)
    {
        System.out.println(res);
    }
 
 
    static  int gcd(int a,int b)
    {
        if(b==0)
        {
            return a;
        }
        return gcd(b,a%b);
    }
 
    static int lcm(int a, int b)
    {
        return (a / gcd(a, b)) * b;
    }
 
 
    static int abs(int a)
    {
        if(a<0)
            return -1*a;
        return a;
    }
 
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
 
        int [] readintarray(int n) {
            int res [] = new int [n];
            for(int i = 0; i<n; i++)res[i] = nextInt();
            return res;
        }
        long [] readlongarray(int n) {
            long res [] = new long [n];
            for(int i = 0; i<n; i++)res[i] = nextLong();
            return res;
        }
    }
 
}
 
 
 
 
1 Like

long val = (int * int );
(int * int ) > Integer.MAX_VALUE (will cause overflow)
long val is then assigned overflow value

try this
long val = (long * long)
(long * long ) (no overflow )

I guess it will work :sweat_smile:

2 Likes

Change int to long in array declaration.

1 Like

Is there any proof that max is always (An - A1)*An-1 and not (An-1 - A1)*An . I did the problem using the first one and it worked. But during submitting I was not totally sure.
I know it looks right by intuition but is there any proof that the first is always smaller or equal to the second?

1 Like

yes even i also thought the same thing and solved like this but it got wrong can anyone tell me my mistake pls…

#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T–){
int N; int k; int m;
cin>>N;
int arr[N];
for(int i=0;i<N;i++){
cin>>arr[i];
}
sort(arr,arr+N);
k = (arr[N-1]-arr[0])*arr[N-2];
m = (arr[N-2]-arr[0])*arr[N-1];
cout<<max(k,m)<<endl;

}


return 0;

}

Use long instead of int, it will work

I got it. It’s silly actually a simple expansion is the answer, first becomes AnAn-1 - An-1A1 and second AnAn-1 - AnA1. It’s obvious now.

1 Like

can u plzz explain why we have to do this

but why … Ai is less than 10^6 and int can store 10^6

Alternate approach- we don’t even need to sort the array.

  1. Let’s say we don’t know anything, then either-

(Max-min)*Second_max
or
(Second_max-min)*max will be the maximum

  1. We can find max, second_max and min all in linear O(N) time in something like this -
//max2 is second max, max is maximum and min is minimum
int max=Integer.MIN_VALUE,max2=Integer.MIN_VALUE,min=Integer.MAX_VALUE;

for (int i = 0; i < a.length; i++) {
	if(a[i]>=max)
		{
       // if we find a number greater than max we give value of max to max2 
		max2=max;
		max=a[i];
		}
	else if(a[i]>=max2)
		{
         // if we have accidently stored max value in first attempt we would still need
         //to look for second highest... so this part
		max2=a[i];
		}
    if(a[i]<min)
	{
    //finding min here
		min=a[i];
	}
				
}

then we check for maximum among two possibilities and print it; resMax is a long variable-

if(  (	(	(long)	max-min)*max2 	)> 	(	(long)	max2-min)*max 	)	
				resMax=(	(long)	max-min)*max2 ;
				
			else
				resMax=(	(long)	max2-min)*max  ;
			
			
			
out.println(resMax);

Full solution (JAVA)- Solution: 55434891 | CodeChef

3 Likes

can anybody say what is my mistake
#include

#include <bits/stdc++.h>

using namespace std;

#define Code ios_base::sync_with_stdio(false);

#define By cin.tie(NULL);

#define Shubh cout.tie(NULL);

#define ll long long

#define fl(i,n) for(int i=0;i<n;i++)

#define rl(i,m,n) for(int i=n;i>=m;i–)

#define ff first

#define ss second

#define pb push_back

#define mp make_pair

#define pi 3.141592653589793238

#define vr(v) v.begin(),v.end()

#define rsv(v) v.end(),v.begin()

#define vec vector

#define endl “\n”

//Maximum Trio

int main(){

Code By Shubh

int t;cin>>t;

while(t--){

    ll n;

    cin>>n;

    int a[n];

    fl(i,n){

        cin>>a[i];

       

    }

    sort(a,a+n);

    long ans =(long)((a[n-1]-a[0])*a[n-2]);//(value > integer) so typecast to long

   

    cout<<ans<<endl;

}

return 0;

}

1 Like

I did the same thing in my solution, but I got WA in 4 subtasks. I don’t know why (I might be making some blunder somewhere, but I am unable to find it). Here is my code (C language):

#include <stdio.h>

int findmax(int a[], int n);
int findmax2(int a[], int n, int l);
int findmin(int a[], int n);

int main(void) {
	// your code goes here
	int t, n, i, p1, p2, maxind, minind, max2ind;
	int a[300000];
	scanf("%d", &t);
	while(t--){
	    scanf("%d", &n);
	    for(i=0; i<n; i++){
	        scanf("%d", &a[i]);
	    }
	    maxind=findmax(a, n);
        minind=findmin(a,n);
        max2ind=findmax2(a, n, maxind);
        p1=(a[maxind]-a[minind])*(a[max2ind]);
        printf("%d\n", p1);
	}
	return 0;
}

int findmax(int a[], int n)
{
    int j, max, l;
    max=a[0];
    l=0;
    for(j=1; j<n; j++){
        if(a[j]>=max){
            max=a[j];
            l=j;
        }
    }
    return l;
    
}
int findmax2(int a[], int n, int l)
{
    int i, k=0, max2=0;
    for(i=0;i<n;i++){
        if(i==l) continue;
        else{
            if(a[i]>=max2){
                k=i;
                max2=a[i];
            }
        }
    }
    return k;
}

int findmin(int a[], int n)
{
    int i, min;
    int ind=0;
    min=a[0];
    for(i=1; i<n; i++){
        if(a[i]<min){
            min=a[i];
            ind=i;
        }
    }
    return ind;
}

Suppose-

(An - A1)An-1 > (An-1 - A1)An
(An
An-1) - (A1
An-1) > (An-1An )- (A1An)

  • (A1An-1) > - (A1An)
  • (An-1) > - (An)

(An-1) < (An)

which is true .

This is the most optimal solution and should have been the official solution.

Can be solved in O(n) time.

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

1 Like

I guess r1 and r2 are initialized as long long but are still assigned value int only.

r1 = 1LL*(a-c)*b;
r2 = 1LL*(b-c)*a;

may be this will correct your mistake