PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Daanish Mahajan
Tester: Felipe Mota
Editorialist: Vichitr Gandas
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Sorting, Binary Search, Priority Queue or Multisets
PROBLEM:
Given a hallway of length N, you have M workers to clean the floor with each worker responsible for [L_i, R_i] segment (segments might overlap). What’s the minimum amount of time required to clean the floor. Every unit of length should be cleaned by at least one worker. If the workers can clean 1 unit of length in unit time and can start from any position within their segment and can also choose to move in any direction. Also, the flow of each worker should be continuous, i.e., they can’t skip any portion and jump to the next one, though they can change their direction.
QUICK EXPLANATION:
Idea is to binary search on the time. To check if time t would be enough or not, we need to start from location 1 and then keep moving in right direction until we reach N. For this, initially sort the segments in increasing order of L_i and maintain current set of R_i s sorted in increasing order using a priority queue or multiset. So at current location curLocation, we check if we have any R_i such that we can move ahead. We move to the new location of min(R_i, curLocation + t). Finally if we are able to reach the location N, we can finish in time t.
EXPLANATION:
As mentioned in quick explanation, to find the minimum time to finish, we will use the idea of binary search. We can binary search on time so now we need to check if a particular time t is enough or not.
Let’s sort the segments initially in increasing order of L_i. So that we can start from location 1 and keep moving in right direction. Because moving in left is not helpful for us. All left side segments are already covered.
Lets also maintain current set of segments S in increasing order of R_i. This will help us to move right. This can be done using a priority queue or multiset.
Now lets start with curLocation = 1 and iterate over all workers in sorted order. If the current worker’s L_i \leq curLocation, we will include it in our current set. And then iterate over our current set of segments S. For any segment [L,R] in S, we will update curLocation = min(R, curLocation + t). And we will erase the current segment [L,R] from S. We will keep removing elements from S until we find one segment which updates our current location or S becomes empty. If we don’t find any such segment which updates our location, we will break current iteration loop over workers. Because now we won’t able to clean whole floor.
This way we will process all workers and finally check if curLocation = N, then we can finish in time t and we will try for smaller t, otherwise we will try for larger t.
TIME COMPLEXITY:
O(n \cdot \log{n} \cdot \log{m}) per test case
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define pii pair<int, int>
using namespace std;
struct myComp {
constexpr bool operator()(pair<int, int> const& a, pair<int, int> const& b)const noexcept
{
return a.second > b.second;
}
};
const int maxt = 1e5;
const int maxn = 1e9;
const int maxm = 1e5;
const int maxtm = 2e5;
int n, m;
bool can(vector<pii> &v, int &x){
int st = 1, ptr = 0; bool upd = true;
priority_queue<pii, vector<pii>, myComp> pq;
while(st < n && upd){
while(ptr < m && v[ptr].first <= st){
pq.push(v[ptr]); ptr++;
}
upd = false;
while(pq.size() != 0){
pii p = pq.top(); pq.pop();
if(p.second <= st)continue;
st = min(st + x, p.second);
upd = true;
break;
}
}
return st == n;
}
int main()
{
int t; cin >> t;
int tm = 0;
while(t-- > 0){
cin >> n >> m;
tm += m;
vector<pii> v;
for(int i = 0; i < m; i++){
int l, r;
cin >> l >> r;
v.pb(make_pair(l, r));
}
sort(v.begin(), v.end());
int ans = -1, l = 1, r = maxn;
while(l <= r){
int m = (l + r) >> 1;
if(can(v, m)){
ans = m;
r = m - 1;
}else{
l = m + 1;
}
}
cout << ans << endl;
}
assert(tm <= maxtm);
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
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){
if(is_neg){
x= -x;
}
if(!(l <=x &&x <=r)){
cout << l << ' ' << x << ' ' << r << '\n';
}
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,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = readIntLn(1, TEN(5));
int sum_m = 0;
while(t--){
int n = readIntSp(1, TEN(9)), m = readIntLn(1, TEN(5));
sum_m += m;
vector<pair<int,int>> p;
for(int i = 0; i < m; i++){
int l = readIntSp(1, TEN(9)), r = readIntLn(1, TEN(9));
assert(l < r);
p.push_back({l, r});
}
sort(p.begin(), p.end());
int lo = 1, hi = TEN(9) + 1, ans = -1;
while(lo <= hi){
int mid = (lo + hi)>>1;
int at = 1, got_p = 0;
bool ok = true;
multiset<pair<int,int>> que;
while(at < n && ok){
while(got_p < m && p[got_p].first <= at){
que.insert({p[got_p].second, p[got_p].first});
got_p++;
}
int cur_at = at;
while(cur_at == at && !que.empty()){
auto in = *que.begin(); que.erase(que.begin());
swap(in.first, in.second);
cur_at = max(cur_at, min(in.second, cur_at + mid));
}
if(cur_at == at)
ok = false;
at = cur_at;
}
if(at != n)
ok = false;
if(ok) ans = mid, hi = mid - 1;
else lo = mid + 1;
}
cout << ans << '\n';
}
assert(1 <= sum_m && sum_m <= 2 * TEN(5));
assert(getchar() == -1);
return 0;
}
Editorialist's Solution
/***************************************************
@author: vichitr
Compiled On: 23 Apr 2021
*****************************************************/
#include<bits/stdc++.h>
using namespace std;
bool check(vector<pair<int, int>>& seg, int x, int n, int m){
int curLocation = 1;
multiset<int> S;
int i = 0;
while(curLocation < n){
// if L <= current location, include in cur set S
while(i < m and seg[i].first <= curLocation){
S.insert(seg[i].second);
i++;
}
int cur = curLocation;
// check for any R such that we can move right
while(cur == curLocation and !S.empty()){
int R = *S.begin();
S.erase(S.begin());
curLocation = max(curLocation, min(R, curLocation + x));
}
// if we dont find any segment to move right
// break it. because we can't finish now
if(curLocation == cur)
break;
}
return curLocation == n;
}
void solve(){
int n, m; cin >> n >> m;
vector<pair<int, int>> seg(m);
for(int i = 0; i < m; i++){
cin >> seg[i].first >> seg[i].second;
}
sort(seg.begin(), seg.end());
int ans = -1, s = 1, e = 1e9;
while(s <= e){
int mid = (s + e) / 2;
if(check(seg, mid, n, m)){
ans = mid;
e = mid - 1;
}
else
s = mid + 1;
}
cout << ans << '\n';
}
signed main()
{
int t = 1;
cin >> t;
for(int i = 1; i <= t; i++)
{
solve();
}
return 0;
}