WAV2 problem

Can someone please help me out in finding what’s wrong with my solution for WAV2

#include
using namespace std;
int main()
{
int N, Q;
cin >> N >> Q;
int arr[N];
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
for (int i = 0; i < Q; i++)
{
int k, brr[4], prod = 1;
cin >> k;
for (int j = 0; j < N; j++)
{
brr[j] = k - arr[j];
}
for (int j = 0; j < N; j++)
{
prod = prod * brr[j];
}
if (prod > 0)
cout << “POSITIVE” << endl;
else if (prod < 0)
cout << “NEGATIVE” << endl;
else
cout << 0 << endl;
}
return 0;
}

It is slow use binary search instead

1 Like

First please enclose your code in triple``` ticks like this

This is a sample code 

Also descibe the problem weatrher you are getting WA or TLE…

Second thing that your code will not pass the time constraints bro you have used one loop inside the another 1sec = 10^8 operations. O(NQ) will be 10^10…
1≤N,Q≤2⋅105
|ai|≤109
for each valid i* a1,a2,…,aN

  • are pairwise distinct
  • |xi|≤109
    for each valid i

So optimise your code .
If you use Binary search then time comlexity will be O(Qlog(N)) which will pass the tiem constarints.
Hint you can use binary search for finding the index/no of elements greater or smaller than it if the elements in array are distinct using binary search.
Idea :(x-x1)
(x-x2)…polynomial
Now we know that x-x1>0 if x>x1 so if we find the no elements in ary greater than qi (Each query ) we know that it will contribute to -ve value …count them using binary search …
Link :to my code Solution: 48001759 | CodeChef

1 Like

Thanks for showing this approach and solution bro👍🏻

1 Like

I used binary but got TLEcan you please help me with the code attached. I used the binary approach in which I first search whether num is in the array or not then found the index of the number in the array then used the fact that alternative roots are pos and neg code is here Help is highly appreciated

int find_index(vector<int> v, int n, int K)
int binarySearch(vector<int> v, int low, int high, int key)

These two functions should take v by reference instead of value - otherwise, v will be copied each time they are called!

2 Likes

Same happened to me also .I did write binary search myself and got tle. Changed the same to lower_bound (Which uses binary search BTW) then my solution got accepted. I will attach my submissions link. It wasted my time, I was so close on solving 3rd question but no time due to this issue.

https://www.codechef.com/viewsolution/47967041

https://www.codechef.com/viewsolution/47968472

But the time complexity is still O((n+q)logn) so why TLE I mean I did call by referrence now but why I was getting TLE before. Can you please explain @ssjgz :smiley:

Not if you pass by value it isn’t - you call binarySearch Q times, and copying v takes O(N) each time.

1 Like

Ahhh ok Thankyou so much I think the same will not happen if we use arrays right?

I don’t think you can pass C-style arrays by value, so that’s correct.

1 Like

#include <stdio.h>

int main()
{int N,Q,product=1;
scanf("%d %d",&N,&Q);
int a[N],x[Q];
for(int i=0;i<N;i++)
{
scanf("%d",&a[i]);

}
for(int a=0;a<Q;a++)
{
scanf("%d",&x[a]);
}for(int b=0;b<Q;b++)
{
for(int j=0;j<N;j++)
{
product=product*(x[b]-a[j]);

}

if(product>0)
{
printf(“POSITIVE\n”);

}
else if(product==0)
{
printf(“0\n”);

}
else if(product<0)
printf(“NEGATIVE\n”);

product=1;

}

return 0;

}

hey i solved the wave problem of polynomial in c & i got the correct output but it says time limit exceeded i.e is 1.01 seconds

for(int b=0;b<Q;b++)
{
for(int j=0;j<N;j++)
{
product=product*(x[b]-a[j]);

}
}
2 for loops ,one nested inside other …
O(Q*N) = 10^10 operations …(worst case )
In 1 sec only 10^8 is allowed ,optimise your code buddy .
Use binary search …