SECRECP - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan Jaddouh

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

DIFFICULTY:

PREREQUISITES:

Math , Binary search, greedy

PROBLEM:

There is a circular road of length L. Chef is at point 0. There are n people who want to catch chef.Coordinates of the n people are given. Maximum velocity of chef(v_c) and the n people is given (let maximum velocity of $i$th person be v_i). Find the minimum time needed by people to catch the chef.

EXPLANATION

Case 1: A single person can chase and catch the chef without any help.
For a single person with velocity v_x and distance d away from chef, he can only catch chef without any help when v_x>v_c. Time needed to catch will be d/(v_x-v_c).

So we can iterate over the n people and take minimum over the time needed for each person to catch chef individually.

Case 2: Apart from Case 1, if chef is getting caught chef needs to be surrounded from both the directions by two different people.

So now, the aim of the people will be to close down chef from both directions as early as possible which can also said as minimum time needed for two people to meet such that both are travelling in opposite directions and one of them crosses 0.

Let i th person distance from zero in clockwise direction be x_i.Let i th person distance from zero in anticlockwise direction be y_i.

Now, we want to find min_{i \neq j}((x_i+y_j)/(v_i+v_j)).

Let us binary search on the answer. Let us see how to check if a there is some pair that can meet in atleast t time.

For that to be possible ((x_i+y_j)/(v_i+v_j)) \leq t.

(t*v_i - x_i) + (t*v_j - y_j) \geq 0.

So now we can sort people based (t*v_i-x_i) and (t*v_j-y_j) in descending order. And if first person on both lists are different, we choose them for opposite directions respectively. Otherwise, we try 1st of first list and 2nd on second list and vice versa.If these pairs cannot satisfy, no other pair can satisfy. So we need to just check for these pairs.

Now, if we see, we did not need to sort the lists, we just need the maximum two elements in each list which can be done in O(n) time.

TIME COMPLEXITY

O(6*n*log(L)). First case takes O(n) time and second case, each iteration of binary search takes O(n) time.

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
            
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            assert(cnt>0);
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
 
int T;
int n;
long long L;
long long Vc;
long long v[100100];
long long x[100100];
int sm_n=0;
double _ = 0;
int main(){
    //freopen("00.txt","r",stdin);
    //freopen("00o.txt","w",stdout);
    T=readIntLn(1,1000);
    while(T--){
        n=readIntSp(2,100000);
        L=readIntSp(2,1000000);
        Vc=readIntLn(1,1000000);
        for(int i=0;i<n;i++){
            if(i==n-1){
                x[i]=readIntLn(1,L-1);
            } else {
                x[i]=readIntSp(1,L-1);
            }
        }
        for(int i=0;i<n;i++){
            if(i==n-1){
                v[i]=readIntLn(1,1000000);
            } else {
                v[i]=readIntSp(1,1000000);
            }
        }
        double ans =1ll<<60;
        for(int i=0;i<n;i++){
            if(v[i] > Vc){
                ans = min(ans , x[i] / (v[i] - Vc + _) );
                ans = min(ans , (L-x[i]) / (v[i] - Vc + _) );
            }
        }
        double l = 0 , r= ans;
        for(int i= 0; i<100;i++){
            double md= (r+l)/2;
            bool chk = false;
            double a=1ll<<60,b=1ll<<60;
 
            for(int i=0;i<n;i++){
                if(a + x[i] - md * v[i] < 0)chk=true;
                if(b + L-x[i] - md * v[i] < 0)chk=true;
 
                a = min(a, L-x[i] - md * v[i]);
                b = min(b, x[i] - md * v[i]);
            }
            if(chk){
                r=md;
            } else {
                l=md;
            }
        }
        cout<<fixed;
        cout.precision(10);
        cout<<r<<endl;
    }
    assert(getchar()==-1);
} 
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
int n,l,sp;
int pos[1234567],v[1234567];
int check(double mid){
    int i;
    vector< pair<double,int> > vec;
    rep(i,n){
        vec.pb(mp(mid*v[i]-pos[i],i));
    }
    pair<double,int> a1,b1,a=max(vec[0],vec[1]),b=min(vec[0],vec[1]);
    
    f(i,2,n){
        if(a<vec[i]){
            b=a;
            a=vec[i];
        }
        else if(b<vec[i]){
            b=vec[i];
        }
    }
    vec.clear();
    a1=a;
    b1=b;
    rep(i,n){
        vec.pb(mp(mid*v[i]+pos[i]-l,i));
    }
    a=max(vec[0],vec[1]),b=min(vec[0],vec[1]);
    f(i,2,n){
        if(a<vec[i]){
            b=a;
            a=vec[i];
        }
        else if(b<vec[i]){
            b=vec[i];
        }
    }
    if(a.ss!=a1.ss){
        if(a.ff+a1.ff>=0)
            return 1;
        return 0;       
    }
    else{
        if(a.ff+b1.ff>=0)
            return 1;
        if(b.ff+a1.ff>=0)
            return 1;
        return 0;
    }
    return 0;
}
main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        
        cin>>n>>l>>sp;
        int i;
        rep(i,n){
            cin>>pos[i];
        }
        rep(i,n){
            cin>>v[i];
        }
        double mini=inf;
        rep(i,n){
            if(v[i]<=sp){
                continue;
            }
            mini=min(mini,min(pos[i],l-pos[i])*1.0/(v[i]-sp));
        }
        double low = 0;
        double high = 2e6,mid;
        int iter=70;
        while(iter--){
            mid=(low+high)/2;
            if(check(mid)){
                high=mid;
            }
            else{
                low=mid;
            }
        }
        cout<<setprecision(30)<<min(mini,low)<<endl;
 
 
    }
    return 0;   
}

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

3 Likes

i had a similar approach but I did not use binary search…still I was able to do it in the given time but I got WA…Can anyone please help me point out where I was going wrong??

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

int main() {
double t,n,l,Vchef;
cin >> t;
while(t–)
{
cin >> n >> l >> Vchef;
vector x(n),v(n);
for (int i=0;i<n;i++)
cin >> x[i];
for (int i=0;i<n;i++)
cin >> v[i];

	double result=100000000;
	
	for(int i=0;i<n;i++)
    {
        if(v[i]-Vchef>1e-6)
        {
            double ds=min(x[i],l-x[i]);
            result=min(result,ds/(v[i]-Vchef));
        }
    }
	
	for (int i=0;i<n;i++)
	{
	    for (int j=0;j<n;j++)
	    {
	        if(i==j) continue;
	        result=min(result,(x[i]+l-x[j])/(v[i]+v[j]));
	    }
	}
	cout << result << endl;
}
return 0;

}