FLUSHOT - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

The problem can be solved with a binary search approach. Given a value D, we can efficiently determine if there is a way to move each person with distance at most D or not. The idea is that we can assume that the left-most person moved as far left as they can. Then, the second person moves as far left as they can up to distance D or until they are T units next to the first person. Basically, the first person moves to x’ _ 1 := max(0, x _ 1-D) and every subsequent person i moves to x’ _ i := max(x’_ {i-1}+T, x _ i-D). If this max ever moves someone more than D units to the right, then we report that distance D is not sufficient. Otherwise, we report that distance D is ok. Of course, if

distance D suffices then any distance D’ >= D will also work so the binary search approach will succeed.

The output precision was chosen to be 4 decimals because the input precision was 3 decimals and one can argue that the solution is always
an integer multiple of 0.0005. It’s a fun exercise.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes

Beautiful question!!

1 Like

What is the mistake in this code ?

int koko(double mid,vector&a,double t){

// vector<double>temp;

int n=a.size();

double zero=0;

double ans=max(zero,a[0]-mid);

// temp.push_back(ans);

for(int i=1;i<n;++i){

 if((ans+t)>a[i]+mid)

 return 0;

 ans=max(ans+t,a[i]-mid);

}

return 1;

}

void solve()

{

 int n;

 cin>>n;

 double t;

 cin>>t;

 vector<double>a(n);

 for(int i=0;i<n;++i)

 cin>>a[i];  

 double low=0;

 double high=1000000;

 double mid=0;

 double ans=0.0;

 while(low<high){

 mid=(low+high)/2;

 if(koko(mid,a,t)){

  ans=mid;

  high=mid-(1e-5);

 }

 else

 low=mid+1e-5;

 }

cout<<fixed<<setprecision(4)<<ans<<endl;

return;

}