Positive Polynomial Profits
National Olympiad — National round, shared Groups A and B (2010 season)
Submission name: dogfood.cpp
Problem summary
Each investor’s profit is a polynomial of degree one, two or three in a shared price x. For every queried price, count how many polynomials are strictly positive. There may be up to 100000 investors and 100000 queries, so testing every investor at every price is too slow.
Input
F and Q; then F rows giving a coefficient count D and its D real coefficients from highest degree to constant term; then Q queried prices.
Output
For each price, the number of strictly positive profits, in the original query order.
Constraints
1 ≤ F,Q ≤ 100000; 2 ≤ D ≤ 4. Prices and real roots lie in [−100,100]; the leading coefficient is nonzero and has magnitude below 10. No repeated roots. Distinct roots of one polynomial are at least 0.1 apart; roots from different polynomials and root/query pairs are at least 0.0001 apart.
Worked example
An independently prepared example for this explanation.
Input
2 4 3 -1.000000 4.000000 -3.000000 2 1.000000 -2.000000 0.500000 1.500000 2.500000 3.500000
Output
0 1 2 1
Solution analysis
- Sort the queries by price, remembering their original positions. For one polynomial, all positive query positions form only a few consecutive blocks. Add +1 to each block in a difference array instead of updating its queries individually.
- A polynomial is monotone between consecutive roots of its derivative. A line needs no split; a quadratic has one derivative root; a cubic has at most two. Solve only these linear or quadratic derivative equations, then split the sorted queries at the turning points.
- Within one such part, the predicate profit>0 changes at most once. If the first and last queries have the same sign, the whole part has that sign. Otherwise, binary-search the first query whose sign differs from the first query and update the positive prefix or suffix. Evaluate by Horner’s rule; there is no need to approximate the polynomial’s own roots.
- For the sample, −x²+4x−3 is positive only between 1 and 3, while x−2 is positive above 2. At prices 0.5,1.5,2.5,3.5 the two positivity indicators sum to 0,1,2,1. Finally, prefix-sum the difference array and restore the original query order.
Why it works
The derivative split produces monotone polynomial intervals, so each interval contains at most one transition between nonpositive and positive sampled values. Endpoint inspection and binary search therefore identify exactly its positive query block. A difference-array increment adds one exactly to that block. Summing all polynomial contributions counts every profitable investor once for each query, and the saved permutation restores the requested order.
Watch out. The required condition is strictly positive, not nonnegative; the root/query gap avoids ambiguous zero-query cases. Use long double, Horner evaluation and the cancellation-resistant quadratic formula for derivative roots. Handle negative leading coefficients, decreasing parts, no-real-turning-point cubics, duplicate query prices and arbitrary original query order. This numerical method relies on the statement’s root-separation guarantees.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
#include<cmath>
using namespace std;
struct Polynomial{
int count;
array<long double,4>coefficient;
};
long double evaluate(const Polynomial&polynomial,long double x){
long double value=0;
for(int i=0;i<polynomial.count;++i){
value=value*x+polynomial.coefficient[i];
}
return value;
}
vector<long double>turningPoints(const Polynomial&polynomial){
vector<long double>points;
if(polynomial.count==3){
points.push_back(-polynomial.coefficient[1]/(2*polynomial.coefficient[0]));
}
else if(polynomial.count==4){
long double a=3*polynomial.coefficient[0];
long double b=2*polynomial.coefficient[1];
long double c=polynomial.coefficient[2];
long double discriminant=b*b-4*a*c;
if(discriminant>0){
// This quadratic formula avoids subtracting almost equal numbers.
long double q=-0.5L*(b+copysign(sqrt(discriminant),b));
points.push_back(q/a);
points.push_back(c/q);
}
}
sort(points.begin(),points.end());
return points;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int polynomialCount,queryCount;
cin>>polynomialCount>>queryCount;
vector<Polynomial>polynomials(polynomialCount);
for(Polynomial&polynomial:polynomials){
cin>>polynomial.count;
for(int i=0;i<polynomial.count;++i){
cin>>polynomial.coefficient[i];
}
}
vector<pair<long double,int>>queries(queryCount);
for(int i=0;i<queryCount;++i){
cin>>queries[i].first;
queries[i].second=i;
}
sort(queries.begin(),queries.end());
vector<long double>price(queryCount);
for(int i=0;i<queryCount;++i){
price[i]=queries[i].first;
}
vector<int>difference(queryCount+1,0);
for(const Polynomial&polynomial:polynomials){
vector<int>boundaries={0};
for(long double point:turningPoints(polynomial)){
int index=upper_bound(price.begin(),price.end(),point)-price.begin();
boundaries.push_back(index);
}
boundaries.push_back(queryCount);
for(size_t part=1;part<boundaries.size();++part){
int left=boundaries[part-1];
int right=boundaries[part];
if(left==right){
continue;
}
bool firstPositive=evaluate(polynomial,price[left])>0;
bool lastPositive=evaluate(polynomial,price[right-1])>0;
int positiveLeft=left;
int positiveRight=right;
if(firstPositive==lastPositive){
if(!firstPositive){
continue;
}
}
else{
int low=left;
int high=right;
// On a derivative-delimited interval the sign changes at most once.
while(low<high){
int middle=low+(high-low)/2;
bool positive=evaluate(polynomial,price[middle])>0;
if(positive==firstPositive){
low=middle+1;
}
else{
high=middle;
}
}
if(firstPositive){
positiveRight=low;
}
else{
positiveLeft=low;
}
}
++difference[positiveLeft];
--difference[positiveRight];
}
}
vector<int>answer(queryCount);
int current=0;
for(int i=0;i<queryCount;++i){
current+=difference[i];
answer[queries[i].second]=current;
}
for(int value:answer){
cout<<value<<'\n';
}
}