# 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