# WAV2- Editorial

Setter: Aryan Garg
Tester & Editorialist: Taranpreet Singh

Cakewalk

Binary Search

# PROBLEM

Given a polynomial with N distinct roots of form \displaystyle P(x) = \prod_{i = 1}^N (x-A_i), you need to determine at different values of x, whether P(x) would be positive, negative or zero.

# QUICK EXPLANATION

• P(x) is zero if and only if x is a root of P(x). This implies x must appear in A
• Otherwise, if there are even number of values in A which are > x, then P(x) > 0.
• If there are odd number of values in A which are > x, then P(x) < 0

# EXPLANATION

### Idea

Letâ€™s see how the sign of polynomial changes for polynomial with roots 2, 4, 6, implying P(x) = (x-2) * (x-4) * (x-6)

• If x \in \{2,4,6\}, then P(x) = 0
• If 6 < x, all three terms of product are positive, so P(x) > 0
• If 4 < x < 6 , (x-2) and (x-4) are positive, but (x-6) is negative, leading to P(x) < 0
• If 2 < x < 4, (x-2) is positive, but (x-4) and (x-6) are negative, leading to P(x) > 0
• If x < 2, then all (x-2), (x-4) and (x-6) are negative, leading to P(x) < 0

We can easily see that if some x, if it is a root of P(x), then P(x) = 0, which is consistent with the definition of root of a polynomial.

Otherwise, we can see that the product of N terms contains c negative terms, where c is the number of values in A strictly greater than x.

• If c is even, P(x) is positive
• If c is odd, P(x) is negative

Hence, all we need to do for each query is for given q_i, check if it is already present in A, and if not, find c, the number of values in A strictly greater than q_i

### Implementation

Method 1
The simplest implementation first sorts the array A in increasing order of values. This way, some suffix of values shall all be greater than value v. We can implement binary search, or use inbuilt lower_bound or upper_bound utilities.

The time complexity of this method is O((N+Q)*log(N))

Method 2
Sort the list of roots of polynomials. Sort the queries as well, while keeping track of indices of queries. Now, Answer queries in increasing order of q_i, by moving a pointer from left to right in the list of roots.

The time complexity of this method is O(N*log(N)+Q*log(Q))

Method 3
This approach sorts the list of roots first in descending order. Now, letâ€™s define a value J = 300 as the jump value. We want to find the first position p with value \geq q_i, the queried value. - - - Starting from p = 0, we keep moving from position p to position p+J until A_{p+J} < q_i is true.

• Then, keep moving p one step to the right until we have A_p \geq q_i.
• Now, if A_p = q_i, then q_i is root of P(x) and answer is zero. Otherwise we can count the number of values greater than q_i.

This approach is more commonly known as sqrt decomposition and the time complexity of this solution is O(N*log(N) + Q*\sqrt N).

# TIME COMPLEXITY

The time complexity is O((Q+N)*log(N) or O(N*log(N)+Q*log(Q)) depending upon implementation.

# SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define fast() {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define ll long long

int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
fast();

int n,q;
cin>>n>>q;
ll a[n];
for(int i = 0; i < n; i++) cin>>a[i];
sort(a, a+n);
bool startPositive = (n & 1) ? 0 : 1;
ll p;
while(q--){
cin>>p;
auto ind = lower_bound(a, a+n, p) - a;
if(a[ind] == p) cout<<0<<'\n';
else{
if(startPositive){
if(ind & 1) cout<<"NEGATIVE\n";
else cout<<"POSITIVE\n";
}
else{
if(ind & 1) cout<<"POSITIVE\n";
else cout<<"NEGATIVE\n";
}
}
}
return 0;
}

Tester's Solution
import java.util.*;
import java.io.*;
class TheWave{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), Q = ni();
int[] A = new int[N];
for(int i = 0; i< N; i++)A[i] = ni();
Arrays.sort(A);
for(int q = 0; q< Q; q++){
int v = ni();
int p = Arrays.binarySearch(A, v);
if(p >= 0)pn(0);
else{
int ins = -p-1;
if((N-ins)%2 == 0)pn("POSITIVE");
else pn("NEGATIVE");
}
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = false;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new TheWave().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}

Method 3 Solution
#include "bits/stdc++.h"
using namespace std;
#define lli long long int
#define pb push_back

int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int N, Q, x;
cin>>N>>Q;
vector<lli> A;
for(int i = 0; i< N; i++){
cin>>x;
A.pb(x);
}
vector<lli>::iterator it;
sort(A.rbegin(), A.rend());
int JUMP = 300;
while(Q-->0){
lli q;
cin>>q;
int pos = 0;
while(pos+JUMP < N && A[pos+JUMP] > q)pos += JUMP;
while(pos < N && A[pos] > q)pos++;
if(pos < N && A[pos] == q)cout<<0<<"\n";
else if(pos%2 == 0)cout<<"POSITIVE"<<"\n";
else cout<<"NEGATIVE"<<"\n";
}
return 0;
}


Feel free to share your approach. Suggestions are welcomed as always.

1 Like

Can someone please explain to me why a binary search results in TLE
https://www.codechef.com/viewsolution/47972482
Whereas a lower_bound results in AC?
https://www.codechef.com/viewsolution/47974833

If I understand correctly the time complexities for both should be the same. Did I miss some optimization in my binary search function?
TIA!

5 Likes

Why does binary search gives TLE.I implemented it in java.Here-java.I wonder whether constraints specifically made to TLE Binary search.

2 Likes

Can someone explain TLE reason here?

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n,q,i,j;
cin>>n>>q;
vector v ;
for(i=0;i<n;i++)
{
ll z;
cin>>z;
v.push_back(z);
}
for(j=1;j<=q;j++)
{
ll z1;
cin>>z1;
if(find(v.begin(), v.end(), z1)==v.end())
{
v.push_back(z1);
auto it=find(v.begin(), v.end(), z1);
ll index=it-v.begin();
if((n-1)%2==(index %2))
cout<<â€śNEGATIVE\nâ€ť;
else
cout<<â€śPOSITIVE\nâ€ť;
}
else
cout<<â€ś0\nâ€ť;
}
return 0;
}

Can someone please explain whatâ€™s wrong with my solution for WAV2 problem

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

Simple Approach

#include <bits/stdc++.h>
using namespace std;
#define test_case \
int t;          \
cin >> t;       \
while (t--)

void initial()
{
std::ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}

int main()
{
initial();
int n, m, k;
cin>>m>>n;
int arr[m];
for(int i=0; i<m; i++){
cin>>arr[i];
}

sort(arr, arr+m);

for(int i=0;i<n;i++){
cin>>k;
int *p = lower_bound(arr, arr+n, k);
cout<<(*p == k ? "0" : (p-arr)%2 ? "NEGATIVE" : "POSITIVE") <<"\n";
}
return 0;
}

2 Likes

here is the binary search implementation â€¦

#include <bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;

int main()
{

int n,q;
cin>>n>>q;
long long int arr[n];
int neg=0;
for(int i=0;i<n;i++){cin>>arr[i];

}
for(int i=0;i<n;i++)if(arr[i]<0)neg++;
sort(arr,arr+n);
while(qâ€“) {

long long int query;
cin>>query;


int start=0,end=n-1;
int mid=(start+end)/2;
int k=-1;

if(arr[0]>query){
if(n%2==0)cout<<"POSITIVE"<<endl;
else cout<<"NEGATIVE"<<endl;


continue; }
else if(arr[n-1]<query){
cout<<â€śPOSITIVEâ€ť<<endl;
continue;
}

while(mid>=0 && mid<n){
mid=(start+end)/2;
if(arr[mid]==query){cout<<â€ś0â€ť<<endl;break;}
else if(arr[mid]<query && mid<n && arr[mid+1]>query){k=mid;break;}
else if(arr[mid]>query && mid>0 && arr[mid-1]<query){k=mid-1;break;}
else if(arr[mid]>query){
end=mid-1;
}
else start=mid+1;
}

 if(k!=-1){
k++;
int temp_neg=neg;
temp_neg+=k;
if((n-k)%2==0)cout<<"POSITIVE"<<endl;
else cout<<"NEGATIVE"<<endl;
}


}
return 0;

}

Your code wonâ€™t work for test cases such as arr = [1, 3, 5, 100, 110] and k = 108 as in this case your p will be equal to 4 which is even so according to your code output will be positive but in reality (108 - 1)(108-3)(108 - 5)(108 - 100)(108 - 110) is negative.

1 Like

Ohkk I got it what you are trying to say and Iâ€™m feeling really bad of me for doing such silly mistake. Ohkk so if I make the brr array of size N like brr[N] then i hope it will give the desired output.

@ojas_17 I think the code for binary search isnâ€™t correct. I have made corrections to some part of your code, you can check it here : Modified code

1 Like

MOST EASY SOLUTION FOR WAVE USING BINARY SEARCH
** int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;

    if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);
}

// We reach here when element is not
// present in array
return l;


}

int32_t main() {
IOS;IOS1;IOS2;

int n,q;
cin>>n>>q;
int arr[n];
for(int i=0;i<n;i++)cin>>arr[i];
while(qâ€“)
{
int i;
cin>>i;
int res=binarySearch(arr,0,n-1,i);
if(arr[res]==i)cout<<0<<endl;
else{
if((res)%2==0)
cout<<â€śPOSITIVEâ€ť<<endl;
else cout<<â€śNEGATIVEâ€ť<<endl;
}
}
return 0;

}**

1 Like

I think you made the logic too complicated. It only needs to use binary search get index, if index ďĽžďĽť0. Means exist in array. res is 0. Otherwise calculate the negative counts with opposite index. See my Java approach Solution: 47989244 | CodeChef

in python lang

n,Q= map(int,input().split())

a = list(map(int,input().split()))

a.sort()

for i in range(Q):

q = int(input())

if q in a:

print('0')

else:

d = 0

for j in a:

if q < j:

d+=1

if d%2 == 0:

print("POSITIVE")

else:

print("NEGATIVE")

I have spent 2.5 hr mugging up in this question still getting WA
I binary searched for the upper bound .
HERE is my code.

#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

I am back with another issue. Are the test cases Weak?

The Code getting AC Verdict
#include <array>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <utility>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

#define FOR(x, N)					for(int x = 0; x < N; x++)
#define inverse(a, p)				power(a, p - 2, p)

typedef unsigned long long int ull;
typedef long long int ll;

const int dc[] = {1, 0, 0, -1, -1, -1, 1, 1};
const int dr[] = {0, 1, -1, 0, -1, 1, -1, 1};

const ll shit	= ((ll)(998244353));
const ll mod	= ((ll)(1e9 + 7));
const ll hell	= ((ll)(1e9 + 9));
const ll inf	= ((ll)(1e18 + 3));

static inline ll gcd(ll a, ll b) {
for(ll rem; b > 0; rem = a % b, a = b, b = rem);
return a;
}
static inline ll lcm(ll a, ll b) {
return (a * b) / gcd(a, b);
}
static inline ll mul(ll a, ll b, ll p) {
return ((a % p * b % p) % p + p) % p;
}
static inline ll add(ll a, ll b, ll p) {
return ((a % p + b % p) % p + p) % p;
}
static inline ll sub(ll a, ll b, ll p) {
return ((a % p - b % p) + p) % p;
}
static inline ll SUM(ll a, ll b) {
return a + b;
}
static inline ll AND(ll a, ll b) {
return a & b;
}
static inline ll XOR(ll a, ll b) {
return a ^ b;
}
static inline ll OR(ll a, ll b) {
return a | b;
}

#define nax 2000003

void preCompute() {
return;
}

template <typename T>
int binarySearch(vector<T> &a, T key) {
int lb = 0;
int ub = a.size() - 1;
while(lb <= ub) {
int mid = (lb + ub) / 2;
if(a[mid] == key) {
return mid;
}
else if(a[mid] < key) {
lb = mid + 1;
}
else {
ub = mid - 1;
}
}
return -1;
}

template <typename T>
int bisect_left(vector<T> &a, T key) {
int ind = binarySearch(a, key);
double k = key;
if(ind != -1) {
k = ((double)(key)) - 0.5;
}
int lb = 0, ub = a.size() - 1;
while(lb <= ub) {
int mid = (lb + ub) / 2;
if(a[mid] < k) {
lb = mid + 1;
}
else {
ub = mid - 1;
}
}
return lb;
}

void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n);
for(auto &x: a) {
cin >> x;
}
sort(a.begin(), a.end());
for(; q > 0; q--) {
int x;
cin >> x;
if(binarySearch(a, x) != -1) {
cout << 0 << '\n';
continue;
}
int pos = bisect_left(a, x);
int neg_count = pos;
if(neg_count % 2) {
cout << "NEGATIVE" << '\n';
}
else {
cout << "POSITIVE" << '\n';
}
}
}

int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t = 0;
t++;
if(!t) cin >> t;
preCompute();
FOR(test, t) {
// cout << "Case #" << (test + 1) << ": ";
solve();
}
return 0;
}


Input

5 6
1 3 5 100 120
-2
2
4
80
107
5


Expected Output (Edited)

NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0


Codeâ€™s Output

POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
0


Now that the problem had more than 3282 + 4109 = 7391 successful submissions during the contest, can we accept this?

So did they take some action already?

They didnâ€™t and I guess they never do. And I canâ€™t resist myself from pointing out mistakes.

Your codeâ€™s time complexity is O(N*Q) and your product variable is bound to overflow. Check the constraints.

There isnâ€™t a binary search operation in your code @amandikshit10. Your time complexity is O(N*Q).

1 Like