# CTIME - EDITORIAL

Author: Daanish Mahajan
Tester: Manan Grover
Editorialist: Nandini Kapoor

Simple

# PREREQUISITES:

Sorting, Set, Pair

# 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();
}
}

11 Likes

Can anyone help me where my solution is going wrong?
https://www.codechef.com/viewsolution/47089669

@rutuja2229 What if several supervisors start watching Chef at the same minute?

x−1−(b−1) minutes

In opinion it should be (b+1) instead of (b-1).

Can you please find out the error in mine.
I passed 3 of the subtasks.
https://www.codechef.com/viewsolution/47091769

1 Like

Can somebody please check my code. It is passing the 1st and 4th subtasks.
Or please provide some edge cases to check my solution.
https://www.codechef.com/viewsolution/47081504

Consider the case when two interval overlap completely.
eg - (1 , 6) , (2 , 5) , (7 , 9)

2 Likes

will u plz give me test cases?

@rutuja2229

1
2 2 3
0 2
0 1


3 Likes

https://www.codechef.com/viewsolution/47055767
can you look into this one?

Hey there! my code cleared 3 subtask and failed in one can someone please help me finding my error here is my submission CodeChef: Practical coding for everyone

@sky_nik Can you please look into my code too. My code is passing 1st and 4th subtasks. And this sample case too.
https://www.codechef.com/viewsolution/47081504

Alteast tell some test cases to check my solution.

Here is my submission. MY code passes two sub task and all the test cases mentioned in this thread why my code fails two sub task ?

Thank you sooo much.That is what happens most of the time I missed testcases
or took tym to reach optimized one during contest.

No the time interval would have been x-b, written ad x-1-(b-1) to comply with the representation of the interval that was written earlier, which itself might have gotten confusing because both extremities inclusive was specified, it thus being different than the one used in the question. Thank you for bringing that to notice I have edited it to comply with the rest of the times intervals are used.

2 Likes

For test case:
2 2 100
99 100
2 3
The spare in your code must return 98, however it returns 2.

1 Like

s[i] and e[i] must be less than f it is already given in question.

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define lli long long int
#define vi vector<lli>
#define vii vector<pair<lli,lli> >
#define pb push_back
#include<string>
#define mp map<string,lli>
#define mpp map<char,lli>
#define ss set<lli>
#define MOD 1000000007
//#define N 100001
#define test lli t;cin>>t;while(t--)
using namespace std;
int main()
{
test
{
lli n,k,f,x,y;
cin>>n>>k>>f;
vi arr,brr,c;
arr.pb(0),brr.pb(0);
if(n==1)
{
cin>>x>>y;
c.pb(x-0);
c.pb(f-y);
if(c[0]>=k || c[1]>=k)
cout<<"YES\n";
else
cout<<"NO\n";
}
else
{
vii a;
for(lli i=0;i<n;i++)
{
cin>>x>>y;
a.pb(make_pair(x,y));
}
sort(a.begin(),a.end());
for(auto x:a)
arr.pb(x.first),brr.pb(x.second);
for(lli i=0;i<brr.size();i++)
c.pb((arr[i+1]-brr[i]));
if(f>brr[brr.size()-1])
c.pb(f-brr[brr.size()-1]);
bool flag=false;
for(lli i=0;i<c.size();i++)
{
if(c[i]>=k)
{
flag=true;
break;
}
}
if(flag)
cout<<"YES\n";
else
cout<<"NO\n";
}
}
}



Thank you so much man!!

Does the editorial solution take overlapping intervals into consideration ?

1 Like