PRDTPAIN - Editorial

#pragma GCC optimize ("-O2")
#include<bits/stdc++.h>
using namespace std;
#define int long long /// make
int maxv(int a[],int s,int e,int x,int y)
{
if(s>e)
return INT_MIN;
int mid=(s+e)/2;
if(a[mid]-a[s]<a[e]-a[mid])
return max(maxv(a,mid+1,e,x,y),(x-a[mid])(a[mid]-y));
else if(a[mid]-a[s]>a[e]-a[mid])
return max(maxv(a,s,mid,x,y),(x-a[mid])
(a[mid]-y));
else
return (x-a[mid])*(a[mid]-y);

}
void solve()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=i+2;j<n;j++)
{
// cout<<maxv(a,i,j,a[0],a[n-1])<<endl;
ans+=maxv(a,i,j,a[i],a[j]);
}
}
cout<<ans<<endl;

}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while( t–)
{

 solve();
    
    
}

}

can any one pls find what’s wrong with this soln, i binary searched the jth value keeping i and k as the min and max value in subarray??

What do we mean by convex?

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.

1 Like

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

Yeah, I had the same thoughts about duplicates.

What did I do? I just saved only unique elements.

CodeChef: Practical coding for everyone.

Thanks.

Awesome solution

exactly its O(2* (n^2) )

1 Like

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.

Exactly correct.

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.

for any fixed i, idx won’t increment more than n times.

It can be proved using calculus as well.

I also tried this way, but may be I missed something.

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

check out my interaction with captainxop above

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.

1 Like

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

Can anyone please help what I am doing wrong here
jfyi- pn is print

void solve(int TC, int TTC) throws Exception{
            int n = ni();
            int arr[] = new int[n];
            for(int i=0;i<n;i++){
                arr[i]=ni();
            }
            long ans  = 0 ;
            for(int i=2;i<=n;i++){
                // System.out.println(i);
                for(int x=0,y=x+i;y<=n-1;x++,y++){
                    
                    // find k 
                    int tar  = (arr[x]+arr[y])/2;
                    int si  =x  , ei = y ; 
                    int sml = arr[x] , lg = arr[y];
                    while(si<ei){
                        int mid = (si+ei)/2;
                        if(arr[mid]>tar){
                            lg = Math.min(lg, arr[mid]);
                            ei = mid-1;
                        }else if(arr[mid]<tar){
                            sml = Math.max(sml ,arr[mid]);
                            si = mid+1;
                        }else{
                            sml = lg = arr[mid];
                            break;
                        }

                    }
                    int contr = 0 ;
                    if(sml==lg && sml==tar){
                        contr=((arr[x]-tar)*(tar-arr[y]));
                    }else {
                        int m1 =((arr[x]-sml)*(sml-arr[y]));
                        int m2 =((arr[x]-lg)*(lg-arr[y]));
                        contr= Math.max(m1 , m2);
                    }
                    // pn("for : "+ tar+"with (" +x+" , "+y +") prev smaller: "+sml+" next  larger : "+lg+" contri : "+contr);
                    ans+=contr;
                
                
                }
                // System.out.println();
             }
             pn(ans);

            
        }```

I’ve also tried O(n^2*log n) and O(n^2) solutions in Python and both TLEd.

Below is my approach using binary search, but it is giving WA. Can anyone suggest any test case where it is failing or anything wrong in my approach.

#include <bits/stdc++.h>
#define ll long long
#define uli unsigned long long int
#define vec(name, type, size, initialization) vector<type> name(size, initialization)
#define cin(arr, size) for(int i=0; i<size; ++i) cin >> arr[i]
#define cout(arr, size) for(int i=0; i<size; ++i) cout<<arr[i]<<" "

using namespace std;

const int MAX = 3000;
vec(arr, ll, MAX, 0);

// function to return the optimal index(j) in (arr[i] - arr[j]) * (arr[j] - arr[k])..
int searchCloser(int l, int r, int key) {
    if(l == r) return l;
    
    int index = -1;
    int diff = INT_MAX;
    
    while(l <= r) {
        int mid = l + (r - l) / 2;
        
        if(arr[mid] == key) {
            return mid;
        }
        
        // element with minimun difference with ideal key is the answer..
        int curr_diff = abs(key - arr[mid]);
        
        if(curr_diff <= diff) {
            index = mid;
            diff = curr_diff;
        } else {
            break;
        }
        
        if(arr[mid] < key) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    
    return index;
}

void solve() {
   int n;
   cin >> n;

   cin(arr, n);
   
   ll sum = 0;
   
   for(int i = 0; i < n; ++i) {

       for(int k = i + 2; k < n; ++k) {
           
           int ideal_elem = (arr[i] + arr[k]) / 2;
           
           int j = searchCloser(i + 1, k - 1, ideal_elem);
           ll curr_res = 1ll * (arr[i] - arr[j]) * (arr[j] - arr[k]);

           sum += curr_res;
       }
   }
    cout << sum << endl;
}


int main(void) 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    
    return 0;
}