PROBLEM LINK:
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy
PREREQUISITES:
Greedy , Interval Scheduling , Sorting
PROBLEM:
Given C cakes numbered from 1 to C. There are N children, where the i^{th} (1 \le i \le N) child wants to eat all the cakes from S_{i} to E_{i}, endpoints inclusive.
You can persuade at most K children, the i^{th} child can be persuaded to change his preference to some other set of cakes [X,Y], provided that the number of cakes are same i.e. (E_{i}-S{i}+1 = Y-X+1).
Determine whether it is possible to make sure that there is no such cake which appears in more than 1 child set after persuading at most K children.
QUICK EXPLANATION:
-
Sort the intervals in ascending order on the basis of their starting points (S_{i}). If the starting points are same then sort them in ascending order on the basis of their ending points (E_{i}).
-
If there are intersecting intervals, there exists an i such that [S_{i},E_{i}] and [S_{i+1},E_{i+1}] intersect.
-
If [S_{i},E_{i}] and [S_{i+1},E_{i+1}] intersect:
- If K=0, we are unable to relocate any interval and hence print Bad.
- If K=1, then we need to relocate interval [S_{i},E_{i}] or [S_{i+1},E_{i+1}], such that after relocation there exists no two intervals which intersect. If such relocation is possible print Good otherwise print Bad.
-
If there are no two intervals which intersect print Good.
EXPLANATION:
Sort the intervals in ascending order on the basis of their starting points (S_{i}). If the starting points are same then sort them in ascending order on the basis of their ending points (E_{i}). The idea of sorting the intervals is useful as if there are intersecting intervals, then there exists an i, such that [S_{i},E_{i}] and [S_{i+1},E_{i+1}] intersect.
Proof
Let us assume that there exists a array of sorted intervals, such that there are intersecting intervals but no two consecutive intervals [S_{i},E_{i}] and [S_{i+1},E_{i+1}] intersect.
If [S_{i},E_{i}] and [S_{i+1},E_{i+1}] doesn’t intersect it means, that the ending point of interval i is less than starting point of interval i+1.
If we extend it further, it implies that:
It shows us that there exists no two pairs (i,j) such that [S_{i},E_{i}] and [S_{j},E_{j}] intersect, which contradicts our assumption. Hence if there are intersecting intervals, then there exists an i, such that [S_{i},E_{i}] and [S_{i+1},E_{i+1}] intersect.
Subtask 1:
Here K=0, which means that we are unable to relocate any interval. So, our task is basically reduced to check that if there exists any two intervals, which intersect each other.
For this, we iterate over the sorted array to determine if there exists an i such that [S_{i},E_{i}] and [S_{i+1},E_{i+1}] intersects. If there exists such i output Bad, otherwise Good.
Time Complexity
O(NlogN)
Subtask 2:
How is this condition E_{i} \le C/2 useful ?
This condition implies that the maximum length of all the intervals is always less than or equal to the empty space. Hence it is always possible to relocate any of the N intervals to the empty space such that it doesn’t intersect with any other intervals.
Proof
len will be maximum, when S_{i} is minimum and E_{i} is maximum. Minimum possible value that S_{i} can take is 1 whereas, the maximum possible value that E_{i} can take is \lfloor \frac{C}{2} \rfloor. Hence the maximum value of len is \lfloor \frac{C}{2} \rfloor.
gap will be minimum, when A is maximum and B is minimum. Maximum possible value that A can take is \lfloor \frac{C}{2} \rfloor+1 whereas, the minimum possible value that B can take is C. Hence the minimum value of gap is \lfloor \frac{C+1}{2} \rfloor.
Hence we can see that len \le gap is always true.
Now we are only left with finding which interval should be relocated such that after relocation. there exists no two intervals which intersect with each other.
For this we will relocate every interval [S_{i},E_{i}] one by one independently, and check if there exists no intersecting intervals afterwards. If there exists an i, such that relocation of [S_{i},E_{i}] ensures that there are no intersecting intervals afterwards print Good, otherwise print Bad.
Time Complexity
Sorting : O(NlogN)
Checking: O(N^{2})
Subtask 3:
The condition of E_{i} \le C/2 is removed.
Since the condition is removed, we need to ensure that if there is enough empty space such that the interval can be relocated. We will try to relocate every interval [S_{i},E_{i}] one by one independently and check that if it is possible to do so.
- Find the length (len) of the interval [S_{i},E_{i}].
- Remove interval [S_{i},E_{i}] from the array.
- Find the maximum empty space (gap) after removal of the interval.
We are now left with finding the maximum empty space (gap).
Maximum Empty Space
If there are N intervals, then there can be N+1 vacant intervals (or gaps), where gap_{1} = S_{1}-1 and gap_{N+1}=C-E_{N}. All the remaining gaps can be found by using the below formula.
gap_{i}=S_{i} - \displaystyle\max_{0<j<i} E_{j} -1We need to take the maximum of all the previous intervals as it is not guaranteed that, E_{j} \le E_{j+1} is always true. Also the intervals are endpoints inclusive, so we also need to subtract 1.
After finding all the gaps, we need take the maximum gap among them i.e.
gap=\displaystyle\max_{1 \le i \le N+1} gap_{i}
If there exist an i such that after removal of interval [S_{i},E_{i}], there exists no two intervals which intersect each other as well as len \le gap print Good, otherwise Bad.
Time Complexity
Sorting : O(NlogN)
Checking: O(N^{2})
Subtask 4:
Since the value of N is large, we need to optimize a bit more. To do so we need to find any valid i such that [S_{i},E_{i}] and [S_{i+1},E_{i+1}] intersects each other and check if we can relocate either of the two intervals such that there exists no intersecting intervals afterwards.
Why checking of only two intervals is sufficient ?
If the intervals [S_{i},E_{i}] and [S_{i+1},E_{i+1}] intersect each other, then relocating any other interval would not affect the intersection of [S_{i},E_{i}] and [S_{i+1},E_{i+1}] - leading to the existence of intersecting intervals even after relocation.
Why checking both the intervals is necessary ?
Checking interval i is necessary because it may be possible that the interval i and i+2 intersects but i+1 and i+2 doesn’t intersects. Then relocation of i is only possible way. You can also visualize this case here
Checking intervals i+1 is necessary because it may be possible that the only intersecting intervals are [i,i+1] and [i+1,i+2].Then relocation of i+1 is only possible way. You can also visualize this case here
If it is possible to relocate either [S_{i},E_{i}] or [S_{i+1},E_{i+1}] , print Good, otherwise Bad.
Time Complexity
Sorting : O(NlogN)
Checking: O(N)
SOLUTIONS:
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
bool overlap(vector <pair<int,int>> v1,int n,int j,int c){
int len,end=0,gap=0;
len=v1[j].snd-v1[j].fst+1;
for(int i=0;i<n;i++){
if(i==j) continue;
if(end>=v1[i].fst) return false;
gap=max(gap,v1[i].fst-end-1);
end=max(end,v1[i].snd);
}
gap=max(gap,c-end);
return gap>=len;
}
void solve(){
int c,n,k; cin>>c>>n>>k;
vector <pair<int,int>> a(n);
for(int i=0;i<n;i++){
cin>>a[i].fst>>a[i].snd;
}
sort(a.begin(),a.end());
bool ok=true;
int ind=-1;
for(int i=1;i<n;i++){
if(a[i-1].snd>=a[i].fst){
ind=i;
ok=false;
break;
}
}
if(k==0){
if(ok) cout<<"Good"<<"\n";
else cout<<"Bad"<<"\n";
}
else{
if(ok) cout<<"Good"<<"\n";
else{
if(overlap(a,n,ind,c) || overlap(a,n,ind-1,c)){
cout<<"Good"<<"\n";
}
else cout<<"Bad"<<"\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t--){
solve();
}
return 0;
}
BONUS:
What if the value C was small, can we optimize the code further i.e. in O(N) time complexity.
Spoiler
Difference Array
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 