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. 