acash's blog

By acash, history, 4 years ago, In English

Lanterns Problem Please forgive me if my ques is not good i am not good at it I am getting precision error on it Test case was huge so i was not able to debug. Mentioned in Prob absolute or relative error doesn't exceed 10 - 9.

example wrong answer 1st numbers differ - expected: '22258199.5000000', found: '22258200.0000000', error = '0.0000000'

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<double>a;
double eps = 1e-9;
bool check(double s,double dist){
    if(a[0]-s>eps)return false;
    if(dist-a.back()-s>eps)return false;
    for(int i=1;i<((int)a.size());i++){
        if(abs(a[i]-a[i-1])-2*s>eps){
            return false;
        }
    }
    return true;
}
int32_t main(){
    int n,d;
    cin>>n>>d;
    a.resize(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
   // for(auto p : a)cout<<p<<endl;
    //exit(0);
    double low=0;
    double high=d;
    int iter=200;
    while(iter--){
        double mid=(low+high)/2;
        if(check(mid,d)){
            high=mid;
        }else low=mid;
    }
    cout<<low<<endl;

}

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks. I have one doubt like most of the people have tried binary search upto certain number of iterations like 50 ,100 etc.I know that log(n) converges very fast but if we try while(high-low>1e-9) getting TLE.And we use this format mostly. why for this particular problem getting TLE? 81978880

    But BS is converging over the invterval through log(n) factor here also and it should have exit when high-low>1e-9 not holds

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      always have a counter when binary searching on a double range