WA in Is This JEE (ICM2003)

general
, , , , ,
1

I was solving the Is This JEE (ICM2003 Problem - CodeChef) problem and I came up with the following solution using binary search which gives the correct output within the given constraints but gives WA on submitting:-

#include <bits/stdc++.h>
using namespace std;

#define ld long double
const long double pi = 3.14159265359;

ld f(ld x, ld B, ld C)
{
  ld num = x*x + B*x + C;
  ld denom = sin(x);

  return num/denom;
}

int main()
{
    int t;
    cin >> t;

    while(t--)
    {
        ld b, c;
        cin >> b >> c;
        ld x = pi/2-1e-10;
        for(ld j = pi/4; j > 1e-4; j/=2)
        {
            while(((x-j) > 0) && (f(x-j, b, c) > f(x-j-1e-4, b, c)))
                x -= j;
        }
        cout << fixed << setprecision(10) << f(x, b, c) << "\n";
    }
    return 0;
}

What should I do? Where does this program fail? Please help.

2

@everule1 Help please

3

When function attains zero value , break the loop. (As you already got the exact root)
Maybe it’ll work.

4

@rishav_iitkgp It is not helping. What should I do?

5

try

1
2 10
6

Getting 14.8174975814 as the output.

7

Even I used desmos to check some of my output and it all matched.

8

Let me compare it to mine.

9

It seems your answer is correct, just not accurate enough.

10

So how can I increase the accuracy? Any tips or tricks?

11

Using 1e-4 to check the slope is sort of pushing it, use 1e-7.

12

Now I am getting TLE.

13

I think your binary search isn’t efficient enough. Instead, tell me what is
\frac{df(x)}{dx}. Continous subtraction is slow.
Hint: \frac{d}{dx} \frac{f(x)}{g(x)} = \frac{f'(x)g(x) - g'(x)f(x)}{(g(x))^2}

1 Like
14

Understood. Make the derivative 0 then calculate f(x) for the value of x for which the derivative of f(x) is zero. Thanks !

15

But there is another problem. Setting the derivative as 0 gives an equation in x and tan x, i.e. tan x = (x*x+bx+c)/(2x+b). How do I solve this?

16

Binary search.
Refer to this. The equation has no standard form for x.

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
long long int p=1e9 +7;
double slope(double x,double b,double c){
    double ans1=(2*x+b),ans2=x*x;
    ans1*=sin(x);
    ans2+=b*x;
    ans2+=c;
    ans2*=cos(x);
    return ans1-ans2;
}
long long int modpower(long long int b,long long po){
    long long int ans=1;
    while(po){
        if(po%2){
            ans*=b;
            ans%=p;
        }
        b*=b;
        b%=p;
        po/=2;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cout<<fixed<<setprecision(12);
	cin >>t;
	while(t--){
	double b,c,x;
	    cin>>b>>c;
	    x=M_PI/4;
	    double mx=M_PI/2;
	    double mn=0;
	 for(int i=0;i<100;i++){
	    // cout<<x<<" "<<mn<<" "<<mx<<'\n';
	    if(slope(x,b,c)<0){
	        mn=x;
	        x=(x+mx)/2;
	       
	    }
	    else{
	        mx=x;
	        x=(x+mn)/2;
	    }
	    
	 }
	 
	 cout<<((x*x + b*x +c)/sin(x))<<"\n";
	    
	    
	    
	}
	
}
1 Like
17

This means that instead of calculating f(x) using binary search it is more efficient to calculate f’(x) using binary search?

18

Yes. Because then we only need to check the sign, so we can also ignore the denominator. long double divisions are slow, or maybe it’s your implementation. Because I haven’t ever seen a while loop in a for loop for binary search.

19

I have change some of your code to get AC
1.Use more precise PI
2.for(ld j = pi/4; j > 1e-4; j/=2)
use 1e-6 instead of 1e-4 to get more accurate ans as mentioned in problem
3.Use double instead of long double otherwise you will get TLE
code with TLE https://www.codechef.com/viewsolution/30556952
code with AC https://www.codechef.com/viewsolution/30556937

2 Likes
20

Thanks !!! I got an AC and the code took 0.82 sec for execution.