 # MXMTRIO - Editorial

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

Simple

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

Tester's Solution
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
print((a[n-1] - a)*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), A[N-2]*(long)(A[N-1]-A));
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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


Feel free to share your approach. Suggestions are welcomed as always. #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 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) * 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;
}

{
StringTokenizer st;

{
}

String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
}
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
{
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}

int res [] = new int [n];
for(int i = 0; i<n; i++)res[i] = nextInt();
return res;
}
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 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)*arr[N-2];
m = (arr[N-2]-arr)*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)*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) {
int t, n, i, p1, p2, maxind, minind, max2ind;
int a;
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;
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;
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