MVALUE - Editorial

editorial
, , , ,
42

@taran_1407 I have computed all possible values of expression and found max value from it. On submitting I got RE (SIGSEGV). Can you suggest some changes in my code? Why I got this error?

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

#define ll long long int
#define MOD 1000000009

void solve()
{
ll n;
cin >> n;
ll arr[n];
for(ll i=0; i<n; ++i){
cin >> arr[i];
}

sort(arr, arr+n, greater<ll>());
ll mx = LLONG_MIN;
ll dp[n][n];
memset(dp,0,sizeof(dp));
for(ll i=0; i<n; ++i){
    for(ll j=i; j<n; ++j){
        if(i != j){
            dp[i][j] = (arr[i]*arr[j]) + arr[i] - arr[j];
            if(dp[i][j] > mx){
                mx = dp[i][j];
            }
        }
    }
}

cout << mx << endl;

}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// int lol=1;
int t;
cin >> t;
// while(lolā€“){
while(tā€“){
solve();
}

}
`

43

I think simply remove abs from both and also
ans1 = a[0]*a[1] + a[1]-a[0];
because a[0] can be contain more abs value then a[1] and we simply wants max value thatā€™s why!

44

why Im still getting WA

int T;
    cin>>T;
    
    while(T--)
    {
        long long int N;
        cin>>N;
        
        long long int a[N];
        
        for(int i=0;i<N;i++)
            cin>>a[i];
            
        sort(a,a+N);
        
        long long int max1=a[0]*a[1]+a[0]-a[1];
        long long int max2=a[N-1]*a[N-2]+a[N-1]-a[N-2];
        
        int max=max1>max2?max1:max2;
        
        cout<<max<<"\n";
    }
45

I have an alternate thinking way, for the less math savvy ones even if this is a simple mathematical expansion. This approach can be generalized for other problems of finding maximas or minimas, so this problem could be used as an introduction to this format of thinking (it can save you a lot of time, especially if you are bad at rewriting expressions, and itā€™s actually quite intuitive :slight_smile:).

First observation we can make is that for unordered pair (a, b), there are two possible outcomes:

  1. (a \cdot b) + a - b, and
  2. (a \cdot b) + b - a

Itā€™s obvious that for case a > b we should opt for the first equation, otherwise move to the second one. This way we can narrow down the list of possible candidates for each a, simply by sorting the array and considering only the lower elements as b.

Let the final array be [b_1, b_2, ..., b_n], in increasing order. Let us consider what happens for b and b', such that b' > b. We can express b' as b' = b + x. Again, we have two equations:

  1. (a \cdot b) + a - b, and
  2. (a \cdot (b + x)) + a - (b + x) = (a \cdot b) + a - b + (x \cdot (a - 1))

A thing to notice is that when we subtract the first from the second equation we are left with:

(a \cdot b) + a - b + (x \cdot (a - 1)) - ((a \cdot b) + a - b) = x \cdot (a - 1)

Since x \geq 0, the final value is dependent only on a - 1, so we have two cases:

  1. a > 0 \implies maximize x, since the array is sorted b is the first value before a
  2. a \leq 0 \implies minimize x, since the array is sorted b is the first value in the array

So we can always uniquely determine the final index and weā€™ve proven it is optimal. :slight_smile:

This idea can be useful in much more advanced problems which have to do with minimality/maximality, one of which is CodeForces 1428E (not an easy problem per se, but the key to the solution is adapting the provided idea), so if any of you are curious hereā€™s the link - Problem - 1428E - Codeforces.

46

Is the third case (arr[n-1], arr[0]) really necessary ? I didnā€™t use it but i still got AC using the below logic

p1=(arr[0]*arr[1])+arr[1]-arr[0]
p2=arr[n-1]*arr[n-2]+arr[n-1]-arr[n-2]
print(max(p1,p2))