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;
}
@itachikesh is correct. This is O(N^2) - it’s a simple application of a two-pointer technique O(N) for each of the N starting indices. It is certainly not greater than O(N^2 log (N)) as @amitcode1311 suggests.
1 Like
Please guys, help me.
Can someone tell me where am i going wrong in this code??
Tried finding the AM-GM using binary search.
https://www.codechef.com/viewsolution/54244899
exactly, it was inspired by the two-pointer technique.
solved problem was just of using long instead of int
Hi ,
My expectation is that you are doing wrong in searchCloser function’s first else statement where you have give a break statement let me explain why its wrong :
Consider a subarray is [1, 3, 5, 8 , 11, 13 ]
- l=0 , r = 5 this implies key = 7 and mid = 2
- As now arr[2]= 5 which is smaller than 7 so , values will change as index=2, diff = 2
now updation of values of Binary search l = 3 and r = 5 - Now again 2nd iteration of while mid = 4 , arr[mid] = 11 m curr_diff = 7-11 = 4
so now you check that as is greater than already found value of diff that is 2 you break the loop there , and print the answer considering 2 as optimal diff but hold on a second -
Point of problem
take 4th value 8 = > (1-8)* (8-13)= 7 * 5 = 35
considering your value 5=> (1-5) * (5-13) = 8 * 4= 32
I think this is the wrong, mine aproach for this question was to find the just smaller and just larger value than the key value and making answer from both of them and printing the largest one
can anyone help me figure out the flaw for which i m still getting WA here …?
while(tc--){
lli n,temp,sum=0,i,len=3;
cin>>n;
Vlli v;
rep(i,n){
cin>>temp;
v.pb(temp);
}
auto it=v.begin();
auto kt=v.begin();
for(len=3;len<=v.size();len++){
for(it=v.begin(),kt=v.begin();kt<v.end()-1;it++){
kt = it + len - 1;
if(len>=4){
auto jt = upper_bound(it+1,kt,((*it)+(*kt)/2));
jt=min(jt,kt-1);
sum+=max((abs((*it)-(*jt))*abs((*jt)-(*kt))),(abs((*it)-(*jt-1))*abs((*jt-1)-(*kt))));
}
else if(len==3){
auto jt = it+1;
sum+=(abs((*it)-(*jt))*abs((*jt)-(*kt)));
}
}
}
cout<<sum<<"\n";
}