 # ELEVATORS - Editorial

Author: cstuart
Testers: mexomerf, rivalq
Editorialist: iceknight1093

TBD

Binary search

# PROBLEM:

N people want to move up in a building; the i-th person from floor A_i to B_i.
There are M elevators, each one starts at floor 1 and takes 1 second to move up one floor. They cannot move downwards.
A person takes H seconds to enter or exit an elevator.

What’s the minimum time needed for everyone to reach their destinations?

# EXPLANATION:

The problem screams binary search: after all, if everyone can reach their destinations in \leq x seconds, they can also reach their destinations in \leq x+1 seconds.

So, if we were able to check quickly enough (say, in \mathcal{O}(N)) whether everyone can reach their destinations in \leq x seconds, we can binary search to find the smallest x for which this is possible.

Let’s make a couple of observations to facilitate this check.

Intuition

Note that the time at which the i-th person reaches their destination is completely determined by the last elevator they take; this person will reach at time B_i - 1 + H\cdot x, where x is the number of times someone got on/off this elevator before this.

In particular, this means that there exists an optimal solution where each person will only ever use one elevator.

Proof

Consider an optimal solution where a person first uses elevator E_1 and then switches to E_2.
If they had instead started on E_2 and keeps the remainder of their trip the same, they’ll still reach the destination at the exact time as before, while E_1 now has 2 less stops and so might reach its destination earlier; it certainly won’t reach any later.

So, we’ve preserved optimality while reducing the number of elevator changes.
Repeat this process to obtain a solution where nobody changes elevators.

Now, let’s look at the process from another angle: given an elevator, which set of people do we assign to it?
We’ve already seen that the only things that matter are the B_i values and the number of stops.

In particular, if we assign k people to an elevator and the highest B_i value among them is M, then the last person to get out will be at time M-1 + 2\cdot H\cdot k.

The last observation above leads to a rather natural greedy strategy.

First, sort the people in increasing order of B_i. Now, suppose we want to check whether everyone can reach in \leq x seconds.

• First, assign B_N to an elevator. This is guaranteed to be the largest B_i value in this elevator, so we can freely choose upto k-1 more people, where B_N-1+2\cdot H\cdot k \leq x.
• Of course, it’s best to choose the k-1 people with largest remaining B_i values, since that is optimal for the other elevators.
• Then, we can repeat this process on the remaining array. That is, pick the person with largest remaining B_i, then assign as many more people to that elevator as possible while choosing the largest possible B_i values.

This is rather simple to implement: simply iterate over the B_i in decreasing order while maintaining the current time taken by the elevator.
If adding a new person to it keeps the time \leq x, do so. Otherwise, start a new elevator.

This gives us a \mathcal{O}(N) check function, following which the entire problem is solved in \mathcal{O}(N\log{10^{18}}) using binary search.

Note that the largest possible answer is about 6\cdot 10^{14} so make sure to set the upper limit of the binary search correctly.

# TIME COMPLEXITY:

\mathcal{O}(N\log {10^{18}}) per testcase.

# CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll T, N, M, H, A, B;

bool test(ll x)
{
ll cur_id = 0;

for (ll i = 0; i < M; i++)
{
ll P = (x - B[cur_id] + 1) / (2 * H);
cur_id += P;

if (P <= 0)
{
return false;
}

if (cur_id >= N)
{
return true;
}
}

return false;
}

void solve()
{
cin >> N >> M >> H;

for (ll i = 0; i < N; i++)
{
cin >> A[i] >> B[i];
}

sort(B, B + N, greater<ll>());

// binary search
ll lower = 0, upper = (ll)1e18, ans = (ll)1e18;

while (lower <= upper)
{
ll mid = (lower + upper) / 2;

if (test(mid))
{
ans = min(ans, mid);
upper = mid - 1;
}
else
{
lower = mid + 1;
}
}

cout << ans << "\n";
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

cin >> T;

for (ll t = 0; t < T; t++)
{
solve();
}

return 0;
}

Tester's code (C++)
// Jai Shree Ram

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

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC

template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, 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)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
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 readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------

int solve(){
static int sum_n = 0;
static int sum_m = 0;
sum_m += m;
sum_n += n;
assert(sum_n <= 3e5);
assert(sum_m <= 3e5);
vector<int> a(n), b(n);
for(int i = 0; i < n; i++){
b[i] = readIntLn(a[i] + 1, 1e9);
}

sort(all(b));

auto check = [&](int x){
int t = 0;
int cnt = 1;
for(int i = 0; i < n; i++){
if(t + 2*h + b[i]  - 1 <= x){
t += 2*h;
}else{
t = 2*h;
cnt++;
}
}

return cnt <= m;
};
int l = 2*h + b[n - 1] - 1, r = 1e18;
int ans = r;
while(l <= r){
int m = (l + r)/2;
if(check(m)){
ans = m;
r = m - 1;
}else{
l = m + 1;
}
}
cout << ans << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
while(t--){
solve();
}
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n, m, h = map(int, input().split())
floors = []
for i in range(n):
a, b = map(int, input().split())
floors.append((a, b))
floors.sort(key=lambda x : x)
lo, hi = 0, 10 ** 18
while lo < hi:
mid = (lo + hi)//2
need = 0
cur = mid+1
reach = True
for a, b in floors:
if cur + b + 2*h <= mid: cur += 2*h
else:
if b+2*h > mid:
reach = False
break
else:
cur = 2*h
need += 1
if reach == False or need > m: lo = mid+1
else: hi = mid
print(lo - 1)

1 Like