ELEVATORS - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: cstuart
Testers: mexomerf, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

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[500005], B[500005];

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 readStringLn(int l, int r) { return readString(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[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}
 
// -------------------- Input Checker End --------------------

int solve(){
 		int n = readIntSp(1, 3e5);
 		int m = readIntSp(1, 3e5);
 		static int sum_n = 0;
 		static int sum_m = 0;
 		sum_m += m;
 		sum_n += n;
 		assert(sum_n <= 3e5);
 		assert(sum_m <= 3e5);
 		int h = readIntLn(1, 1e9);
 		vector<int> a(n), b(n);
 		for(int i = 0; i < n; i++){
 			a[i] = readIntSp(1, 1e9);
 			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
    int t = readIntLn(1,1e5);
    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[1])
	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