We want to maximize this: (a-b)*(b-c) = ab - ac - b² + bc
But, in the above equations, we will make the ‘b’ a variable, and ‘a’ and ‘c’ constants, and we can use basic calculus (the derivative) to find the ‘b’ that maximizes the above equation, so we have:
f(b) = ab - ac - b² + bc
Remember that we have a local minimum or local maximum when the derivative is equal to zero, in this case, we have a quadratic function in respect to ‘b’, so it is not a local but a global minimum or maximum.
f’(b) = a - 2b + c
We equalize the derivative to 0:
a - 2b + c = 0
a + c = 2b
(a + c) / 2 = b
To check if we have a maximum or minimum we use the double derivative:
f’’(b) = -2
It is negative, so it is a maximum.
I understood the from the given rearranged equation. But can we come up with it on our own, or is some prior knowledge helped to decide how we should rearrange the (a−x)(x−b) to reach the new f(x)?
constraint was upto 3000 only which is also on the verge cause log(3000) = nearby 12 so
12*(3000)^2 = 108 x 10^6 = 10^8 which just might fit in. Its on the line. For N = 6000 it would surely give a TLE if tests are made in that manner.
The complexity of Code is not O(N^2) but still less than O(N^3) but its slightly greater than O(N^2 log (N)) cause you go through iteratively of increment 1.
By AM-GM inequality as already stated in the editorial we will get ((a-b)(b-c))^1/2 <= ((a-b)+(b-c))/2
i.e **(a-b)(b-c)=(a-c)^2/1/4 **
we can split (a-c)^2/1/4 into two multiples and then compare the terms in the left with right
a-b=(a-c)/2 & b-c=(a-c)/2
both of them give b=(a+c)/2 as result
Hmm, yeah I was thinking of searching through the array in this manner I just could not think of how to implement it… thanks for sharing this solution.
I tried to solve it as shown below,
And I got the same output for the given input.
I think it’s logically correct, but I still get wrong answer. Can anyone help me to know where is the wrong?
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner in = new Scanner(System.in);
for(int t = in.nextInt();t>0;t--){
int length = in.nextInt();
int[] a= new int[length];
for(int ai = 0; ai<length; ai++){
a[ai] = in.nextInt();
}
int sum=0,weight;
for(int i = 0; i<length-2;i++){
for(int k =i+2; k<length; k++){
weight = 0;
for(int j = i+1; j<k; j++){
int value = (a[i]-a[j])*(a[j]-a[k]);
if( value > weight )
weight = value;
}
sum += weight;
}
}
System.out.println(sum);
}
}
}