@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";
}
please anyone tell what is the issue in my code
it is running for example test cases but giving wrong answer.
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* 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
{
InputReader input = new InputReader(System.in);
int t = input.nextInt();
for (int a = 0; a < t; a++){
int n = input.nextInt();
int[] arr = new int[n];
for(int j = 0; j < n; j++){
arr[j] = input.nextInt();
}
long ans = 0;
for(int i = 0; i < n; i++){
for(int j = i+2; j < n; j++){
int k = upperBound(arr,i,j,(arr[i] + arr[j])/2);
k = Math.min(k,j-1);
long weight = Math.max( (arr[i] - arr[k])*(arr[k] - arr[j]), (arr[i] - arr[k-1])*(arr[k-1] - arr[j]) );
ans += weight;
}
}
System.out.println(ans);
}
// int[] arr = {1,2,3,4,5,5,5};
// System.out.println(upperBound(arr,0,arr.length-1,5));
}
public static int upperBound(int[] arr, int low, int hi, int element){
int ans = -1;
while(low <= hi){
int mid = (low+hi)/2;
if (arr[mid] <= element){
low = mid+1;
}else{
ans = mid;
hi = mid-1;
}
}
if (ans == -1){
return hi+1;
}
return ans;
}
}
class InputReader{
BufferedReader reader;
StringTokenizer tokenizer;
InputReader(InputStream stream){
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next(){
if (tokenizer == null || !tokenizer.hasMoreTokens()){
try{
tokenizer = new StringTokenizer(reader.readLine());
}catch (IOException e){
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt(){
return Integer.parseInt(next());
}
public String nextLine(){
try{
return reader.readLine();
}catch (IOException e){
throw new RuntimeException(e);
}
}
}
Can someone please help me where am I going wrong in this code please
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* 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
{
Scanner sc = new Scanner(System.in);
long o = sc.nextLong();
while(o > 0){
int n = sc.nextInt();
int a[] = new int[n];
for(int i = 0;i < n;i++){
a[i] = sc.nextInt();
}
long ans = 0;
for(int i = 0;i < n;i++){
for(int j = i + 2;j < n;j++){
int s = (a[i] + a[j])/2;
int id = Arrays.binarySearch(a, i + 1, j - 1, s);
if(id > 0){
ans += (a[i] - a[id]) * (a[id] - a[j]);
}else{
id = (id + 1) * -1;
long t1 = (a[i] - a[id]) * (a[id] - a[j]);
// System.out.println(id);
long k = 0;
if(id - 1 > i){
k = (a[i] - a[id - 1]) * (a[id - 1] - a[j]);
}
if(id + 1 < j){
k = (long)Math.max(k, (a[i] - a[id + 1]) * (a[id + 1] - a[j]));
}
ans += (long)Math.max(t1, k);
// System.out.println(k);
// System.out.println((long)Math.max(t1, k) + " ");
}
}
}
System.out.println(ans);
o--;
}
}
}
Thanks in advance
Its actually b=(a+c)/2
You can conclude this by making a quadratic equation in b with a and c as roots and maximum value occuring at b=(a+c)/2.