You can check my solution using set.
https://www.codechef.com/viewsolution/43248600
m=max(m,(arr[n-1]*arr[n-2])+((arr[n-1]-arr[n-2])));
This is the wrong bit, when you know that this is for negative numbers, you should try and put some into it.
eg, for -6, -7 :
→ (-7 * -6) + (-7 - (-6)) = 42 + (-1) // your solution
whereas,
→ (-7 * -6) + (-6 - (-7)) = 42 + (+1), which is clearly greater
so all you need to do is make it (arr[n-2]-arr[n-1]);
Thanks 
@sanjeev0007 a,b can be theh same value but they have to be a different elements in the array, e.g if the array has two 10 than a,b both can be 10, in your example you can choose the 3rd, and the 4th item of the array.
#include<bits/stdc++.h>
#define int long long int
using namespace std;
void solve()
{
int n;cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
int ans = arr[n-1]*arr[n-2]+arr[n-1]-arr[n-2];
cout<<ans<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}
can anyone tell me why is this getting wa
why it is given a and b are distinct elements, i thought if 2 same elements are present in array then i have to chose the smaller one apart from same number.
numbers in array are negative also and it may happen that two negative number produce product greater than 2 positive number.
import java.util.;
import java.lang.;
import java.io.*;
import java.math.BigInteger;
/* 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{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
while(t-->0){
int n=Integer.parseInt(br.readLine());
long arr[]=new long[n];
String t1[]=br.readLine().split(" ");
for(int i=0;i<n;i++){
arr[i]=Long.parseLong(t1[i]);
}
Arrays.sort(arr);
long a=arr[n-1];
long b=arr[n-2];
long x=arr[1];
long y=arr[0];
long sum=Math.max(a*b+a-b,x*y+x-y);
System.out.println(sum);
}
}
}
1 Like
or just sort athe array by Arrays.sort() and then take the same.
absolutely right ,have to be different element but can be same value .
I totally forgot the negative side of numbers!, my bad.
Why so?
Only reason I marked it easy-med because the idea to rewrite expression is what I believed many would miss. Otherwise I’d only mark it easy if (a-1)*(b+1) was given.
Do you mean to say that this problem has the same difficulty as this problem or am I mistaken somewhere?
Also, I don’t think that VSTRING was anyways easier than this problem. At least the numbers don’t seem to agree.
Sorry If there’s different criteria for assigning these difficulties that I’m not aware of.
1 Like
where a and b are two are 2 distinct elements of the array.
This was quite misleading. I assume 2 distinct elements by magnitude and got W.A.
However nice question and video editorial is too good.
I found problem VSTRING much easier when compared to problem MVALUE. Because as soon as I read the problem VSTRING, I know what to do and had proof for the same within a minute. But that was not the same for MVALUE as it took me time to prove my solution.
Coming to the difficulty tag for the problem, I think the targeted audience also affects the difficulty tag. As in this problem MVALUE, the targeted audience was Division 3 whereas, in problem INDEP, the targeted audience was different.
@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();
}
}
`
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!
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";
}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 
).
First observation we can make is that for unordered pair (a, b), there are two possible outcomes:
- (a \cdot b) + a - b, and
- (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:
- (a \cdot b) + a - b, and
- (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:
- a > 0 \implies maximize x, since the array is sorted b is the first value before a
- 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.
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.
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))