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)