PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Daanish Mahajan
Tester: Manan Grover
Editorialist: Nandini Kapoor
DIFFICULTY:
Simple
PREREQUISITES:
PROBLEM:
Chef’s college is conducting online exams, where his camera will be monitored by one or more invigilators during the exam. Chef failed to prepare for the exam on time and decided to google the answers during the exam. The exam starts at time 0 and ends at time F. Chef needs a total of K minutes of googling during the exam in order to pass it. Invigilators monitor his camera at N times of the form [S_i,E_i] (where 0\leq Si \leq Ei\leq F), during which he can’t google. Chef was resourceful enough to get hold of these times and now he wants to know if he’ll be able to pass the exam if he googles the answers during the times when no one is looking at his camera.
QUICK EXPLANATION:
We need to find sum of minutes within time intervals wherein no invigilator is looking at Chef’s camera, i.e. count all minutes that do not lie in any of the given N intervals.
Following the order of appearance of the intervals (i.e. sorted order), if the immediate next interval starts strictly after all of the previous intervals have ended, then the time between these 2 points can be used for googling.
If the sum of such times is greater than or equal to the amount of time Chef needs for googling during the exam then he shall pass otherwise he wouldn’t have enough time and would fail.
EXPLANATION:
We have to find the number of minutes wherein no invigilation takes place, which can be obtained with the help of intervals where no invigilation is being done (As between times x and y i.e. interval [x, y], there lie a total of y-x minutes). The un-invigilated intervals are of the form [x, y], where the immediate previous interval of invigilation ended at x minutes and the immediate next one starts at y.
Any two invigilation intervals, [a, b] (b \geq a) and [x, y] (y \geq x) can be of the following forms (considering x \geq a, i.e. second interval starts after or at the same time as the first one):
- CASE 1: x \leq b and y \leq b, whereby the latter interval lies completely within the former.
- between the occurrence of the 2 intervals there is no time where invigilation isn’t happening. The intervals can collectively be written as [a, b].
- CASE 2: x \leq b and y \gt b, whereby some of the latter interval’s initial minutes are also some of the former one’s final minutes.
- no un-invigilated period between the two intervals. They can be collectively written as [a, y].
- CASE 3: x \gt b, whereby the latter interval occurs entirely after the former.
- the time interval between the two that is not invigilated is [b, x], i.e. x-b minutes of time for Chef to google.
to identify which of the above cases they belong to, we need to sort the intervals by their starting points (in increasing order) and then while traversing them, keep track of the maximum time an interval has ended at so far. The third case only occurs when the immediate next interval to the current one (in the sorted list of intervals) has starting time greater than the ending time of any other previously occurred interval. We maintain a variable to hold the total minutes Chef has had for googling so far and whenever the third case is encountered we add minutes to this variable.
To establish this we use a set of pairs (vector can also be used provided that it is sorted after pushing all pairs), thus storing the given intervals by their starting points (conflict in position of equal starting points in the sorted order is resolved by sorting as per the ending point of the intervals, but it is of no consequence for our approach, all we need is that the starting points be accessed in their order of appearance). Once all the pairs are inserted into the set, we traverse it for finding intervals satisfying case 3.
We keep track of the maximum end point among the intervals that we come across while traversing the set, let’s call it x. If the starting point of an interval is found to be less than or equal to x, then no contribution will be made to the minutes Chef has for googling. Whereas when the starting point of an interval (let a be the starting point) is greater than x, a-x will be added to Chef’s time.
If we call the starting time of the very first invigilation to be s, then apart from the time between intervals that are found while traversing, F-x (time between the end of last invigilation to the end of exam) and s-0 (time between start of exam and start of first invigilation) also contribute to Chef’s time.
If this total time calculated is greater than or equal to K, we output Yes otherwise Chef would fall short of time to google thus making the answer No.
Algorithm using vector of pairs named s to store pairs of starting and ending points of given intervals
maxend=0;
for every pair in s:
if maxend<pair.first:
ans+=pair.first-maxend;
if pair.second>maxend:
maxend=pair.second;
ans+=F-maxend
if ans>=K:
output "YES";
else:
output "NO";
TIME COMPLEXITY:
O(N\times \log N) per test case.
As complexity of insertion in STL set is O(\log N), and insertion is done for N pairs denoting intervals of invigilation.
Proof
T(n)=\log n for insertion in set, where n is number of elements in set.
We build set from empty to n elements, thus time taken for filling the entire set is:
- T(1)+T(2)+T(3)+... +T(n) = \sum_{i=1}^n log(i)
-
\log a+\log b=\log (a\times b) , therefore \sum_{i=1}^n log(i)= log(n!)
Thus, \sum_{i=1}^n T_i = \Omega (\prod_{i=1}^n) i -
\log (n!) < \log (n^n) and log(n^n)=n\times \log n
Therefore \Omega (n!) = O(n\times log n)
Further, traversal of the set to accumulate intervals of un-invigilated time requires O(n) time attributed to the loop entirely. This makes the time complexity of our solution T(N)=O(N\times \log N)+O(N)=O(\max (N, N\times \log N))=O(N\times \log N)
SOLUTIONS:
Setter
#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define pii pair<int, int>
using namespace std;
const int maxt = 1e5;
const int maxn = 1e5;
const int maxtn = 2e5;
const int maxtime = 1e9;
int main()
{
int t; cin >> t;
int tn = 0;
int n, k, time, l, r;
while(t-- > 0){
cin >> n >> k >> time;
tn += n;
vector<pii> v;
for(int i = 0; i < n; i++){
cin >> l >> r;
v.pb(make_pair(l, r));
}
sort(v.begin(), v.end());
int prv = 0, ans = 0;
for(int i = 0; i < n; i++){
ans += max(0, v[i].first - prv);
prv = max(prv, v[i].second);
}ans += max(0, time - prv);
string output = (ans >= k ? "YeS" : "No");
cout << output << endl;
}
assert(tn <= maxtn);
}
Tester
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n,k,f;
cin>>n>>k>>f;
int sum = 0;
pair<int, int> a[n];
for(int i = 0; i < n; i++){
cin>>a[i].first>>a[i].second;
}
int temp = 0;
sort(a, a + n);
for(int i = 0; i < n; i++){
sum += max(0, a[i].first - temp);
temp = max(temp, a[i].second);
}
sum += f - temp;
if(sum >= k){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
return 0;
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
#define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
#define int long long int
#define endl "\n"
#define mod 1000000007
#define pb_ push_back
#define mp_ make_pair
//______________________________z_____________________________
void solve()
{
int n, k, f, prev=-1, ans=0;
cin>>n>>k>>f;
set<pair<int, int>>s;
for(int i=0; i<n; i++) {
int temp, temp2;
cin>>temp>>temp2;
s.insert(mp_(temp, temp2));
}
s.insert(mp_(f, f));
int maxend=0;
for(auto it: s) {
if(maxend<it.first) ans+=it.first-maxend;
if(it.second>maxend) maxend=it.second;
}
if(ans>=k) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int32_t main()
{
_z;
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
