PROBLEM LINK:
Author: valiant_vidit
Tester: hellb0y_suru
Tester: vikiwarrior
Editorialist: valiant_vidit
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Given a function f(x)=(x-k_{1})*(x-k_{2})*(x-k_{3})*(x-k_{4})+C
You to find all roots of f(x) between [L,R].
- the values of k_{1} , k_{2},k_{3},k_{4} are integers and given for each test file.
- In a given range (L, R) ,there exists more than one roots of a function.
- In a given range ( L , R), there exists only either a maxima or a minima.
- the value of the constant C will be given in each test case.
QUICK EXPLANATION:
It is a kind of a good implementation of binary search in a given range.
EXPLANATION:
By observing point 2 and point 3 given in the question, it can be clearly stated that there exists only 2 roots in a given range.
First of all one should find the maxima/minima of function,for this one should
differentiate the function .
As stated that in a give range there is only one maxima/minima so we can say that the
derivative of a function will be one to one in a given range,so we can apply binary search
in a given range to find only root of derivative function in given range,by which we will be able to find the only maxima/minima lying in the given range.
After finding the only maxima/minima let say it is at x=k,we can apply 2 binary searches
i.e., b/w [L,k] and b/w [k,R], by which we can easily find the 2 roots of function in range.
Points to be noted that will applying binary search we should check firstly that the curve is increasing or decreasing and accordingly we can apply it by checking the values of left ,right and mid as positive or negative , we can break the search when the difference of left and right is less than the desired error.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define loop(a,b,i) for(ll i=a;i<b;i++)
#define loop1(a,b,i) for(ll i=a;i>b;i--)
#define endl '\n'
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
const double pi = std::acos(-1);
using namespace std;
const ll mod = 1000000000+7;
ll power(ll x, ll y, ll md)
{
ll res=1;x=x%md;if (x==0)return 0;while (y>0) {
if (y&1)res=(res*x)%md;y=y>>1;x=(x*x)%md;
}return res;
}
ll m_mul(ll a, ll b) {
a=a%mod;b=b%mod;return (a*b+mod)%mod;
}
ll m_add(ll a, ll b) {
a=a%mod; b=b%mod;return (a+b+mod)%mod;
}
ll a10, a11, a12, a13;
double fx(double x, ll c)
{
double res=(x-a10)*(x-a11)*(x-a12)*(x-a13)+c;
return res;
}
double dfx(double x)
{
double res=(x-a11)*(x-a12)*(x-a13)+(x-a12)*(x-a13)*(x-a10)+(x-a10)*(x-a11)*(x-a13)+(x-a10)*(x-a11)*(x-a12);
return res;
}
double g_incd(double i, double j)
{
double sl=-1.0;
while (i<=j)
{
double mid=(i+j)/2;
if (abs(i-j)<=1e-4)
{
sl=(round(mid*10000))/10000;break;
}
if (dfx(mid)>0)
{
j=mid-1e-5;
}
else if (dfx(mid)<0)
{
i=mid+1e-5;
}
}
return sl;
}
double g_decd(double i, double j)
{
double sl=-1.0;
while (i<=j)
{
double mid=(i+j)/2;
if (abs(i-j)<=1e-4)
{
sl=(round(mid*10000))/10000;break;
}
if (dfx(mid)<0)
{
j=mid-1e-5;
}
else if (dfx(mid)>0)
{
i=mid+1e-5;
}
}
return sl;
}
double g_inc(double i, double j, ll c)
{
double sl=-1.0;
while (i<=j)
{
double mid=(i+j)/2;
if (abs(i-j)<=1e-4)
{
sl=(round(mid*10000))/10000;break;
}
if (fx(mid, c)>0)
{
j=mid-1e-5;
}
else if (fx(mid, c)<0)
{
i=mid+1e-5;
}
}
return sl;
}
double g_dec(double i, double j, ll c)
{
double sl=-1.0;
while (i<=j)
{
double mid=(i+j)/2;
if (abs(i-j)<=1e-4)
{
sl=(round(mid*10000))/10000;break;
}
if (fx(mid, c)<0)
{
j=mid-1e-5;
}
else if (fx(mid, c)>0)
{
i=mid+1e-5;
}
}
return sl;
}
int main() {
ll tc;
// freopen("inpp07.txt","r",stdin);
// freopen("@outpp07.txt","w",stdout);
cin>>a10>>a11>>a12>>a13;
cin>>tc;
while (tc--)
{
double l, r;ll c, fl;ll gp=0;
cin>>l>>r>>c;
///////////////////////
if (dfx(l)<0&&dfx(r)>0)
fl=0;
else if (dfx(l)>0&&dfx(r)<0)
fl=1;
double i=l-1e-3;
double j=r+1e-3;
double sl=0.0;
if (fl==0)
{
sl=g_incd(i, j);
}
else
{
sl=g_decd(i, j);
}
double l1=l-1e-3, r1=sl;
double l2=sl, r2=r+1e-3;
double root1=0.0, root2=0.0;
if (fl==0)
{
root1=g_dec(l1, r1, c);
root2=g_inc(l2, r2, c);
}
else
{
root1=g_inc(l1, r1, c);
root2=g_dec(l2, r2, c);
}
cout<<root1<<" "<<root2<<endl;
}
// your code goes here
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define MOD 1000000007
#define oo 1000000000000000000
#define forr(i,n) for(ll i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0) ; cout.tie(0);
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define pb push_back
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
template<typename...T>
void read(T&... args){
((cin >> args), ...);
}
ll valueOfIndex(ordered_set&s , ll i){ return *(s.find_by_order(i)); }
ll indexOfValue(ordered_set&s , ll x){ return s.order_of_key(x); }
ll add(ll a, ll b,ll p=MOD) { a%=p; b%=p; return (a+b + p)%p;}
ll mul(ll a, ll b,ll p=MOD) { a%=p; b%=p; return (a*b + p)%p;} // __int128
ll power(ll x,ll n,ll p=MOD){ if(x==0) return 0; if(n==0 || x==1) return 1LL;
ll r = (power(x,n/2,p))%p; if(n&1) return mul(mul(r,r,p) , x,p); else return mul(r,r,p);
}
bool h1 = 1 , h2 = 1;
double k1,k2,k3,k4;
double binc(double s, double e){ // inc
double ans;
while(s<=e){
double m = (s+e)/2;
double v =(m-k1)*(m-k2)*(m-k4)+(m-k1)*(m-k3)*(m-k4)+(m-k1)*(m-k2)*(m-k3)+(m-k2)*(m-k4)*(m-k3);
if(v>=0.00){
ans = m;
e = m - 0.00001;
}
else s = m + 0.00001;
}
return ans;
}
double bdec(double s, double e){ // dec
double ans;
while(s<=e){
double m = (s+e)/2;
double v =(m-k1)*(m-k2)*(m-k4)+(m-k1)*(m-k3)*(m-k4)+(m-k1)*(m-k2)*(m-k3)+(m-k2)*(m-k4)*(m-k3);
if(v>=0.00){
ans = m;
s = m + 0.00001;
}
else e = m - 0.00001;
}
return ans;
}
/*
double getMid(double s, double e){
double value=(s-k1)*(s-k2)*(s-k4)+(s-k1)*(s-k3)*(s-k4)+(s-k1)*(s-k2)*(s-k3)+(s-k2)*(s-k4)*(s-k3);
if(value<0){
return binc(s,e);
}
else return bdec(s,e);
}
*/
double b1(double s, double e, double c){ // inc
double temp1 = (s-k1)*(s-k2)*(s-k3)*(s-k4) + c;
double temp2 =(e-k1)*(e-k2)*(e-k3)*(e-k4) + c;
if((temp1>0 && temp2>0) || (temp2<0 && temp1<0)){
h1=0;
return -1;
}
double ans;
while(s<=e){
double m = (s+e)/2;
double v =(m-k1)*(m-k2)*(m-k3)*(m-k4) + c;
if(v>=0.00){
ans = m;
e = m - 0.00001;
}
else s = m + 0.00001;
}
return ans;
}
double b2(double s, double e, double c){ // dec
double temp1 = (s-k1)*(s-k2)*(s-k3)*(s-k4) + c;
double temp2 =(e-k1)*(e-k2)*(e-k3)*(e-k4) + c;
if((temp1>0 && temp2>0) || (temp2<0 && temp1<0)){
h2=0;
return -1;
}
double ans;
while(s<=e){
double m = (s+e)/2;
double v =(m-k1)*(m-k2)*(m-k3)*(m-k4) + c;
if(v>=0.00){
ans = m;
s = m + 0.00001;
}
else e = m - 0.00001;
}
return ans;
}
void what( double &l, double &g , double &c){
double s = l , e = l + 0.789;
double temp1 = (s-k1)*(s-k2)*(s-k3)*(s-k4) + c;
double temp2 =(e-k1)*(e-k2)*(e-k3)*(e-k4) + c;
if(temp1 < temp2){
g = 1;
}
else g = 0;
}
void __sol(){
double l,r,c,g,gp=0.001;
cin >> l >> r >> c;
what(l,g,c);
h1=1 , h2=1;
if(g==0){
double mid = binc(l,r);
double r1 = b2(l-gp,mid+gp,c) , r2 = b1(mid-gp , r+gp,c);
if(h1) printf("%.3f ", r1);
if(h2) printf("%.3f ", r2);
cout << "\n";
}
else{
double mid = bdec(l,r);
double r1 = b1(l-gp , mid+gp,c) , r2 = b2(mid-gp , r+gp,c);
if(h1) printf("%.3f ", r1);
if(h2) printf("%.3f ", r2);
cout << "\n";
}
// cout << (109.98-10)*(109.98-60)*(109.98-110) + 100 << "\n";
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
// fastio
cin >> k1 >> k2 >> k3 >> k4;
ll tc=1; cin >> tc;
while(tc--) __sol();
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
#define endl '\n'
using namespace std;
const ll mod = 1000000000+7;
double a,b,c,d;
double fun(double x,double k)
{
double ans= x*x*x*x-(a+b+c+d)*x*x*x+(a*b+a*c+a*d+b*c+b*d+c*d)*x*x+(-a*b*c-a*c*d-a*b*d-b*c*d)*x+a*b*c*d+k;
return ans;
}
double dfun(double x)
{
double ans= (4*x*x*x)-(3*(a+b+c+d)*x*x)+(2*(a*b+a*c+a*d+b*c+b*d+c*d)*x)-(a*b*c+a*c*d+a*b*d+b*c*d);
return ans;
}
double decslope(double l,double r)
{
double ans=0.0;
while(true)
{
double mid=(l+r)/2;
if( (dfun(mid)*dfun(mid+0.001)<0) || (dfun(mid)*dfun(mid-0.001)<0)|| dfun(mid)==0 )
{
ans=mid;
break;
}
else if(dfun(mid)>0)
{
l=mid;
}
else if(dfun(mid)<0)
{
r=mid;
}
}
return ans;
}
double incslope(double l,double r)
{
double ans=0.0;
while(true)
{
double mid=(l+r)/2;
if( (dfun(mid)*dfun(mid+0.001)<0) || (dfun(mid)*dfun(mid-0.001)<0)|| dfun(mid)==0 )
{
ans=mid;
break;
}
else if(dfun(mid)>0)
{
r=mid;
}
else if(dfun(mid)<0)
{
l=mid;
}
}
return ans;
}
double incfun(double l,double r,double cc)
{
double ans=0.0;
while(true)
{
double mid=(l+r)/2;
if( (fun(mid,cc)*fun(mid+0.001,cc)<0) || (fun(mid,cc)*fun(mid-0.001,cc)<0)|| fun(mid,cc)==0 )
{
ans=mid;
break;
}
else if(fun(mid,cc)>0)
{
r=mid;
}
else if(fun(mid,cc)<0)
{
l=mid;
}
}
return ans;
}
double decfun(double l,double r,double cc)
{
double ans=0.0;
while(true)
{
double mid=(l+r)/2;
if( (fun(mid,cc)*fun(mid+0.001,cc)<0) || (fun(mid,cc)*fun(mid-0.001,cc)<0)|| fun(mid,cc)==0 )
{
ans=mid;
break;
}
else if(fun(mid,cc)>0)
{
l=mid;
}
else if(fun(mid,cc)<0)
{
r=mid;
}
}
return ans;
}
int main() {
ll t;
cin>>a>>b>>c>>d;
cin>>t;
while(t--)
{
double l,r,k;
cin>>l>>r>>k;
//finding maxima/minima
double m;
double le=l,ri=r;
double peak;
if(dfun(l)<dfun(r))
{
peak=incslope(l,r);
}
else
{
peak=decslope(l,r);
}
// cout<<peak<<endl;
// cout<<decfun(peak,r,k)<<" ";
// roots finding
if(fun(l,k)<fun(peak,k)&&fun(l,k)*fun(peak,k)<=0)
{
cout<<incfun(l,peak,k)<<" ";
}
if(fun(r,k)<fun(peak,k)&&fun(r,k)*fun(peak,k)<=0)
{
cout<<decfun(peak,r,k)<<" ";
}
if(fun(l,k)>fun(peak,k)&&fun(l,k)*fun(peak,k)<=0)
{
cout<<decfun(l,peak,k)<<" ";
}
if(fun(r,k)>fun(peak,k)&&fun(r,k)*fun(peak,k)<=0)
{
cout<<incfun(peak,r,k)<<" ";
}
cout<<endl;
// cout<<peak<<endl;
// cout<<dfun(l)<<"dsc"<<dfun(r)<<endl;
//cout<<dfun(2.38281-0.001)<<endl;
}
return 0;
}