WAV2- Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Aryan Garg
Tester & Editorialist: Taranpreet Singh

DIFFICULTY

Cakewalk

PREREQUISITES

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;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        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());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

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

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }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. :slight_smile:

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! :slight_smile:

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

please help in my code why they give TLE?
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")

Someone please help me to figure out whats wrong in my code.
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