# Is there an O(n) solution for this problem?

I have found this problem on CodeForces.The problem is in the following link: https://codeforces.com/problemset/problem/729/C

Problem Starts here:

Vasya is currently at a car rental service, and he wants to reach cinema. The film he has bought a ticket for starts in t minutes. There is a straight road of length s from the service to the cinema. Let's introduce a coordinate system so that the car rental service is at the point 0, and the cinema is at the point s.

There are k gas stations along the road, and at each of them you can fill a car with any amount of fuel for free! Consider that this operation doesn't take any time, i.e. is carried out instantly.

There are n cars in the rental service, i-th of them is characterized with two integers ci and vi — the price of this car rent and the capacity of its fuel tank in liters. It's not allowed to fuel a car with more fuel than its tank capacity vi. All cars are completely fueled at the car rental service.

Each of the cars can be driven in one of two speed modes: normal or accelerated. In the normal mode a car covers 1 kilometer in 2 minutes, and consumes 1 liter of fuel. In the accelerated mode a car covers 1 kilometer in 1 minutes, but consumes 2 liters of fuel. The driving mode can be changed at any moment and any number of times.

Your task is to choose a car with minimum price such that Vasya can reach the cinema before the show starts, i.e. not later than in t minutes. Assume that all cars are completely fueled initially.

Input The first line contains four positive integers n, k, s and t (1 ≤ n ≤ 2·105, 1 ≤ k ≤ 2·105, 2 ≤ s ≤ 109, 1 ≤ t ≤ 2·109) — the number of cars at the car rental service, the number of gas stations along the road, the length of the road and the time in which the film starts.

Each of the next n lines contains two positive integers ci and vi (1 ≤ ci, vi ≤ 109) — the price of the i-th car and its fuel tank capacity.

The next line contains k distinct integers g1, g2, ..., gk (1 ≤ gi ≤ s - 1) — the positions of the gas stations on the road in arbitrary order.

Output Print the minimum rent price of an appropriate car, i.e. such car that Vasya will be able to reach the cinema before the film starts (not later than in t minutes). If there is no appropriate car, print -1.

Problem Ends here.

And the solution I found is the following (the code is not mine, it belongs to the person who posted it on github): https://github.com/spoj-solution/solution/blob/master/src/729C-RoadToCinema.cpp .

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

bool check(const std::vector<long> pos, long t, long cap){

long totalTime(0);
for(long p = 1; p < pos.size(); p++){
long dist = pos[p] - pos[p - 1];
if(cap < dist){return false;}
else if(cap >= 2 * dist){totalTime += dist;}
else{totalTime += 2 * (2 * dist - cap) + (cap - dist);}
if(totalTime > t){return false;}
}

return (totalTime <= t);
}

int main(){

long n, k, s, t; scanf("%ld %ld %ld %ld", &n, &k, &s, &t);
std::vector<std::pair<long, long> > cars(n);
for(long p = 0; p < n; p++){
long c, v; scanf("%ld %ld", &c, &v);
cars[p] = std::make_pair(c, v);
}

std::vector<long> pos(k + 2); pos[0] = 0;
for(long p = 1; p <= k; p++){long x; scanf("%ld", &x); pos[p] = x;}
pos[k + 1] = s;
sort(pos.begin(), pos.end());

long cap(1e9 + 10), m(0), M(1e9 + 10);
while(m <= M){
long test = (m + M) / 2;
if(check(pos, t, test)){cap = test; M = test - 1;}
else{m = test + 1;}
}

long minPrice(-1);
for(long p = 0; p < n; p++){
if(cars[p].second < cap){continue;}
if((minPrice < 0) || cars[p].first < minPrice){minPrice = cars[p].first;}
}

printf("%ld\n", minPrice);

return 0;
}


The solution linked takes O(nlogn) complexity because it uses sorting and binary search. I was wandering if there is an O(n) solution for this problem? If there is what should be done.

• Perhaps you could take the time to include at least the problem (and preferably, the known solution) as part of your post? Codeforces might disappear in the future, but we want this question to endure. – Yuval Filmus Nov 22 '19 at 15:16
• @YuvalFilmus yes of course – user102382 Nov 22 '19 at 15:58