MVALUE - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter:
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Easy-medium

PREREQUISITES

Observation

PROBLEM

Given an array A containing N integers, find the maximum value of a*b+a-b where a, b are distinct elements of array.

QUICK EXPLANATION

  • Rewriting a*b+a-b = (a-1)*(b+1) +1, we can fix a and see that for b, we only need to consider either minimum or maximum of all elements of array excluding element a.
  • It can be done by computing the minimum, second minimum, maximum and second maximum element of array, or just by simply sorting the array.

EXPLANATION

As mentioned in quick explanation, we can rewrite the expression.
a*b+a-b = a*(b+1) - (b+1)+1 = (a-1)*(b+1)

Hence, we need to maximise (a-1)*(b+1) where a and b are two distinct elements of array.

Now, a naive way to do this would be to try all pairs of numbers, and taking maximum of value resulted by any pair.

Here, if the elements of array were positive, Just taking the last two elements would have been sufficient. But there are negative elements too, and the product of two negative element can also lead to a higher positive product.

So we try to fix a. We can see that once a is fixed, it is optimal to choose b which would maximise value of (a-1)*(b+1)+1. So

  • if (a-1) > 0, we’d aim to select the largest element in array, so that the value of b+1 can be maximised, therefore (a-1)*(b+1)+1 is maximised.
  • if (a-1) < 0, we’d aim to select the smallest element in array, so that the value of b+1 can be minimised, therefore (a-1)*(b+1)+1 is maximised.
  • if (a-1) < 0, then answer is atleast zero.

Hence, all we need to do is to sort the array, fix a to be each element one by one, and choose most optimum b. Taking maximum over all these candidates gives the maximum value of a*b+a-b

Bonus

Write a solution for above problem which checks minimum number of pairs.

TIME COMPLEXITY

The time complexity can be O(N) or O(N*log(N)) depending upon implementation, per test case.
The memory complexity is O(N) per test case, can be reduced to O(1).

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>

using namespace std;


const int maxt = 10;
const int maxn = 1e5;
const int maxv = 1e9;

int main()
{   
    int t; cin >> t;
    vector<long long> v;    
    while(t--){
        v.clear();
        int n; cin >> n; 
        for(int i = 0; i < n; i++){
            int x; cin >> x;
            v.push_back(x);
        }
        sort(v.begin(), v.end());
        long long ans = LLONG_MIN;
        ans = max(ans, (v[0] + 1) * (v[1] - 1) + 1);
        ans = max(ans, (v[n - 2] + 1) * (v[n - 1] - 1) + 1);
        cout << ans << endl;
    }
} 
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#include <limits>

#ifdef HOME
#define NOMINMAX   
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

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) {
		    assert(cnt > 0);
		    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;
	    }
	    // 		if(g == '\r')
	    // 			continue;

	    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(int argc, char** argv) 
{
#ifdef HOME
    if(IsDebuggerPresent())
    {
	    freopen("../MVALUE_0.in", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T = readIntLn(1, 10);
    forn(tc, T)
    {
	    int N = readIntLn(2, 100'000);
	    vector<int64_t> A(N);
	    forn(i, N)
	    {
		    if (i + 1 == N)
			    A[i] = readIntLn(-1'000'000'000, 1'000'000'000);
		    else
			    A[i] = readIntSp(-1'000'000'000, 1'000'000'000);
	    }
	    sort(A.begin(), A.end());
	    int64_t res = numeric_limits<int64_t>::min();
	    forn(i, N - 1)
	    {
		    int64_t act1 = A[i] * A[i + 1] + A[i] - A[i + 1];
		    int64_t act2 = A[i+1] * A[i] + A[i+1] - A[i];
		    res = max<int64_t>(res, max<int64_t>(act1, act2));
	    }
	    printf("%lld\n", res);
    }
    
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class MVALUE{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        long[] A = new long[N];
        for(int i = 0; i< N; i++)A[i] = nl();
        Arrays.sort(A);
        long ans = Long.MIN_VALUE;
        for(int i = 0; i< N; i++){
            int lo = 0, hi = N-1;
            if(i == lo)lo++;
            if(i == hi)hi--;
            if(A[i]-1 < 0)ans = Math.max(ans, (A[i]-1)*(A[lo]+1)+1);
            if(A[i]-1 > 0)ans = Math.max(ans, (A[i]-1)*(A[hi]+1)+1);
            if(A[i]-1 == 0)ans = Math.max(ans, 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 MVALUE().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;
        }
    }
}

VIDEO EDITORIAL:

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

7 Likes

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;

   int a[n];
   for(int i=0;i<n;i++){
       cin>>a[i];
   }

   long long int ans1,ans2,ans3,ans;

   sort(a,a+n);
   ans1 = a[0] * a[1] + abs(a[0]-a[1]);
   ans2 = a[n-1] * a[n-2] + abs(a[n-1]-a[n-2]);

   ans = ans1>ans2?ans1:ans2;

   cout<<ans<<endl;
}

}

Can anybody tell what’s wrong with this…

1 Like

Honestly, I’ve completely lost my faith in CodeChef difficulty tags now.

5 Likes

I also did the same and getting wrong ans

if input is 6 5 3 4 2 7 7, then what will be value of a,b?

Why is that so?

Just take array of long long int

a = 7 and b = 7

Nice problem. What I did wrong was initialized ans=INT_MIN instead of ans=LLONG_MIN.

def func(a,b):
    s = a*b
    y = max(a,b)-min(a,b)
    return (s+y)
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    arr.sort()
    pos,neg =  0,0
    for i in arr:
        if i>0:
            pos+=1
        elif i<0:
            neg+=1
    if pos>=2 and neg>=2:
        ans = max(func(arr[0],arr[-1]),func(arr[-1],arr[-2]),func(arr[0],arr[1])) # Check maximum of last two positive no.s,,first and last elements , and smallest and 2nd smallest negative numbers
    elif pos>=2:
        ans = max(func(arr[0],arr[-1]),func(arr[-1],arr[-2]))
    elif neg>=2:
        ans = func(arr[0],arr[1])
    else:
        if arr.count(0)>=2:   # if there are atleast two zeroes then I can make the answer as 0
            ans = max(0,func(arr[0],arr[1]))  
        else:
            ans = func(arr[0],arr[1])
    print(ans)

Can anyone tell me in which testcase is my code going wrong?

Can anyone tell the mistake in it?
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
long long maxi = -9999999999;
long long mini = 9999999999;
long long secondMaxi = maxi;
long long secondMini = mini;
// cout<<maxi<<" "<<mini<<endl;
for(int i=0;i<n;i++)
{
long long element;
cin>>element;
if(element>=maxi){ secondMaxi = maxi ;maxi = element;}
else if (element > secondMaxi) secondMaxi = element;

     if(element<=mini){ secondMini = mini; mini = element;}
     else if(element < secondMini) secondMini = element;
 }
 

 
 if( ((mini*secondMini) > (maxi*secondMaxi))and (mini<0 and secondMini<0))
 {
    
     cout<< mini*secondMini + (secondMini+ mini)<<endl;
 }
 else
 {
     cout<< maxi*secondMaxi+ maxi-secondMaxi<<endl;
 }

}
}

#include <iostream>
using namespace std;

int main() {
	// your code goes here
		int t;
		cin >> t;
		while(t-->0){
		      int size;
		      cin >> size;
		      long long largest=0, secondLargest=0;
		      long long arr[size];
		      cin >> arr[0] >> arr[1];
		      if(arr[0]>arr[1]){
    	            largest=arr[0];
		            secondLargest=arr[1];
		      }
		      else{
		            largest=arr[1];
		            secondLargest=arr[0];
		      }
		      for(int i=2;i<size;i++){
		             cin >> arr[i] ;
		             if(arr[i]>largest){
		                      secondLargest=largest;
		                      largest=arr[i];
		             }
		      }
		      printf("%ld\n",((largest*secondLargest)+(largest-secondLargest)));
		}
	return 0;
}

//in which step i am making mistake. can u plz check

just want to know , if it can be solved using dynamic programming?

If you check some of the solutions to this problem, you will see that your code doesnot account for negative values.
since something like (-5)*(-4) +(-4) - (-5) = 21, for an array 1, 2, 3, -4, -5 would be the correct choice

In 2nd case where you calculated the value of ans2, you dont have to take abs value,
just take max(a[n-1]-a[n-2],a[n-2]-a[n-1])

what is wrong in my code plzz help…!!
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–){
long long int n,m=INT_MIN;
cin>>n;
long long int arr[n];
for(long long int i=0;i<n;i++) cin>>arr[i];
sort(arr,arr+n);
m=max(m,(arr[n-1]*arr[n-2])+((arr[n-1]-arr[n-2])));
m=max(m,(arr[n-1]*arr[0])+((arr[n-1]-arr[0])));
m=max(m,(arr[0]*arr[1])+((arr[1]-arr[0])));
cout<<m<<"\n";
}

}

Blockquote

better watch the video editorial. he explained it really well. no need of for loop. Just sort it. That’s all. May be you will get where you are making mistake after watching it.

is it t– or t- can u please check it? looks like t-

got it. didn’t read the constraint properly. Thanks for the reply.

t=int(input())
for i in range(t):
n=int(input())
arr=list(map(int,input().split()))
arrf=[]
for i in range(0,n):
if i<(n-1):
expr=arr[i]*arr[i+1]+max(arr[i]-arr[i+1],arr[i+1]-arr[i])
arrf.append(expr)
elif(i==(n-1)):
expr=arr[i]*arr[0]+max(arr[i]-arr[0],arr[0]-arr[i])
arrf.append(expr)
print(max(arrf))

can anyone please tell me error in above code