PROBLEM LINK:
Editorialist: Adithya Dsilva
DIFFICULTY:
EASY
PREREQUISITES:
Greedy, Pairs (its equivalent in your language)
PROBLEM:
An interval is a pair of positive integers [s,e]\space(s\le e) and represents all values from s to e (endpoints inclusive)
There are C cakes, numbered from 1 to C. There are N children. The i^{th}\space(1\le i\le N) child wants to eat all cakes in interval [s_i,e_i].
You are also given an integer K\in\{0,1\}. You can persuade at most K children to change their preference to some other set of cakes. You can persuade child i to change his range of cakes from [s_i,e_i] to [x,y], only if the number of cakes in interval [x,y] and [s_i,e_i] are equal.
Determine if it is possible to make sure that no cake appears in 2 children’s preferred set of cakes.
QUICK EXPLANATION:
Sort the N intervals in ascending order on the basis of their start indices (s_i) and breaking ties (if any) by sorting them in ascending order of the end indices (e_i). Thus, if intersecting intervals exist in the array, there exists valid i such that [s_i,e_i] and [s_{i+1},e_{i+1}] are intersecting.
If [s_i,e_i] and [s_{i+1},e_{i+1}] are intersecting intervals and K=0, we output Bad
as we can’t ensure that no 2 intervals are intersecting.
If [s_i,e_i] and [s_{i+1},e_{i+1}] are intersecting intervals and K=1, we are compelled to relocate either of the 2 intervals since relocating any other interval would not affect the intersection of these 2 intervals.
So, now we find whether it is possible to relocate interval [s_i,e_i] (or [s_{i+1},e_{i+1}]) such that it doesn’t intersect with any of the other intervals.
One of the ways to determine if relocation is possible is by finding the size of the largest interval, none of whose elements are claimed by the N children. Interval [s_i,e_i] can be relocated (without causing intersections) only if its size is not greater than than this value.
We also determine if after relocating this interval, no other intervals intersect.
Thus, if it is possible to relocate either of [s_i,e_i] or [s_{i+1},e_{i+1}] such that there exists no intersecting intervals after relocation, we output Good
or Bad
otherwise.
EXPLANATION:
Refer the PROBLEM section for definition of the terms being used.
As the entire problem revolves around intersection of intervals, we start by making an important claim on the intersection of 2 intervals. This shall be the base for all subsequent claims.
Claim : [s_i,e_i] and [s_j,e_j]\space(s_i\le s_j) are intersecting intervals if the two intervals have some elements in common. More formally, if [s_i,e_i] and [s_j,e_j] are intersecting intervals, then s_j\le e_i
Proof
Assume the contrary.
Let [s_i,e_i] and [s_j,e_j] (s_i\le s_j) be intersecting intervals, but here s_j>e_i.
Since s_i\le e_i and s_j\le e_j, combining the 3 inequalities gives us
which implies that the intervals are not intersecting.
Thus contradiction.
Let us try solving subtask 1, where K=0.
As no relocations can be done, we check if there exists 2 intervals (among the N intervals) which are intersecting. If intersecting intervals exist, then we output Bad
, otherwise we output Good
. Checking for intersecting intervals can be done by iterating over all pair of intervals and determining if they intersect, using the above claim.
This solution is O(N^2) as we iterate over all pairs of intervals. This is sufficient to solve the first subtask. However, we can reduce the complexity to O(N\log N) by following the below optimization.
Sort the N intervals in ascending order on the basis of their start indices (s_i) and breaking ties (if any) by sorting them in ascending order of the end indices (e_i). Sorting the intervals ensures that s_i\le s_{i+1} for all valid i.
Why have we sorted the intervals? The intervals have been sorted so that the following criterion holds.
Claim : If intersecting intervals exist in the array, there exists valid i such that [s_i,e_i] and [s_{i+1},e_{i+1}] are intersecting.
Proof
Let us assume the contrary.
Suppose there exists a sorted array of N intervals such that intersecting intervals exist, but no 2 consecutive intervals [s_i,e_i] and [s_{i+1},e_{i+1}] are intersecting.
Since the array is sorted s_i\le s_{i+1} for all valid i.
Then, if [s_i,e_i] and [s_{i+1},e_{i+1}] don’t intersect,
should hold for all i.
This would imply
which shows that s_i\le e_i < s_j \le e_j for all pairs i,j\space(i<j).
Thus, no 2 intervals intersect, causing a contradiction to our initial claim.
So, for K=0, 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}] are intersecting. As sorting takes time O(N\log N) and only 1 iteration is done over the N intervals, the time complexity of the above method is
Let us try to solve subtask 2, where K can be 1 and e_i\le \lfloor\frac{C}{2}\rfloor.
What does the criteria e_i\le \lfloor\frac{C}{2}\rfloor imply?
As e_i\le \lfloor\frac{C}{2}\rfloor for all i, all cakes from \lfloor\frac{C}{2}\rfloor + 1 till C are unclaimed. As the maximum possible size of the N intervals is \lfloor\frac{C}{2}\rfloor, it is always possible to relocate any the N intervals, such that it doesn’t intersect with the other intervals (we can relocate it to the unclaimed interval between \lfloor\frac{C}{2}\rfloor + 1 and C)
All that we now have to find is the interval which should be relocated such that there exists no intersecting intervals afterwards.
For this, we find any valid i such that [s_i,e_i] and [s_{i+1},e_{i+1}] are intersecting intervals and check if we can relocate either of the 2 intervals such that there exists no intersecting intervals afterwards.
If, even after relocating [s_i,e_i] or [s_{i+1},e_{i+1}], intersecting intervals exist then it is not possible to have disjoint intervals.
This claim is true because we can relocate at max 1 interval, and 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.
To do this, we either remove [s_i,e_i] or [s_{i+1},e_{i+1}] (as we are relocating it and the relocation makes sure it doesn’t intersect with the other intervals) from our array and then determine if there still are intersecting intervals (using Claim 1).
Now, we can focus on the original constraints.
The only difference between this subtask and subtask 2 is that it is always possible to relocate an interval (when K=1) in subtask 2, but is not always the case in this subtask.
We follow similarly from the method discussed for subtask 2 - finding a valid i such that [s_i,e_i] and [s_{i+1},e_{i+1}] are intersecting.
We are now trying to determine if it is possible to relocate [s_i,e_i] such that there are no intersecting intervals afterwards.
Note : All instances [s_i,e_i] further in the editorial refer to this interval that we are trying to relocate.
We determine the upper bound on the size of the interval that we can relocate. In other words, we are finding the longest interval
such that none of the cakes in this range are claimed by the children. Then k+1 becomes the upper bound on the size of an interval which we can relocate without causing intersections.
This would imply that all intervals with size \le k+1 can be relocated without intersecting with other intervals, and it’s not possible to relocate intervals with size >k+1.
Thus, if (e_i-s_i+1) \le k+1, then it is possible to relocate this interval, else it is not possible.
How do we determine the upper bound k+1? The implementation (in brief) for finding it is as follows.
With similar references as above, let [s_i,e_i] and [s_{i+1},e_{i+1}] be intersecting intervals.
We are trying to determine to determine if it is possible to relocate interval [s_i,e_i] such that there are no intersecting intervals afterwards. The method can then be similarly reused for relocation of interval [s_{i+1},e_{i+1}].
Iterate over the sorted array of intervals in a sequential order (from [s_1,e_1] till [s_N,e_N]), and for each valid j, determine the size of largest unclaimed interval of cakes [x,x+k] where, x+k < s_j. In other words, we find the largest unclaimed interval of cakes before interval [s_j,e_j]
To do this, we define two variables.
-
maxi : This represents the size of the largest unclaimed interval of cakes that we have found out so far. If we are currently processing interval [s_j,e_j], then maxi is the size of the largest unclaimed interval of cakes before interval [s_j,e_j].
The final value stored by this variable will be the upper bound on the size of an interval that we can relocate (without causing intersections with other intervals). - maxE : The largest e value we have encountered till the current iteration. Or in other words, maxE is the last claimed cake that we have encountered thus far (remember that we are iterating over the N intervals).
Both are initially 0.
As we did in the previous subtask, we remove interval [s_i,e_i] from the array. Assume we are currently processing interval [s_j,e_j].
As per our definition of maxE, it holds the index of the last claimed cake before cake s_j. This implies that no cake in the interval [maxE+1,s_j-1] has been claimed. The size of this interval is
Thus, we update
which implies that maxi now holds the value of the largest unclaimed interval of cakes before interval j.
But wait! What if s_j\le maxE ? This would imply that, even after an assumed relocation of [s_j,e_j], intersecting intervals still exist. Thus, it is evident that it is not possible to relocate interval [s_j,e_j] such that there are no intersecting intervals and so we break from the iteration.
Otherwise, we update
implying that maxE holds the index of the last claimed cake till the current iteration.
Thus in every iteration, the values of maxE and maxi hold to their definitions.
After iterating over all the intervals (assuming s_j\le maxE was never satisfied), we check if the size of interval [s_i,e_i] is \le maxi.
If yes, it is possible to relocate this interval or else, it is impossible!
Thus, if it is possible to relocate either of [s_j,e_j] or [s_{j+1},e_{j+1}] such that there are no intersecting intervals after relocation, we print Good
else we print Bad
.
IMPLEMENTATION:
- Make a vector/array of pairs (or its equivalent in your language, like ArrayList in
Java
) A to hold the interval ranges. - Sort A in ascending order of the first term (s_i) and handle ties by sorting in ascending order of the second term (e_i).
- We make a boolean
poss
, initially true, wherefalse
represents that it is not possible to have disjoint intervals. - Run an iteration over the the elements in sorted A, and find the first index i such that A_i and A_{i+1} are intersecting intervals. If K=0, we are done, else we continue as below. We break the loop after this iteration completes.
- Now, we try relocating either of the 2 intervals. We talk about relocating A_i and the same method can be extended to relocate A_{i+1}. Let
index = i
, which is the interval we are relocating. - We make a function
IsPossible()
and pass the input values andindex
. Initialize 2 variablesmaxi
andmaxE
, both with value 0. - We now iterate over the values in A, while skipping the case when the current interval is the one we are relocating. Let the current interval we are processing be A_x\space(A_x \ne A_{index})
- We check if maxi\ge A_x.first, which implies the existence of multiple intersecting intervals; We return
false
if this is the case. - We then update maxi and maxE accordingly as mentioned in the editorial.
- After the iteration over the array, we update maxi to \max(maxi,C-maxE).
- Finally we check if maxi \ge A_{index}.second-A_{index}.first+1 and return
true
; Else, we returnfalse
. - We finally update the value of
poss
tofalse
only if bothIsPossible(<input values>, index)
andIsPossible(<input values>, index + 1)
returnsfalse
; - Lastly, we print
Good
ifflag = true
andBad
otherwise!
SOLUTION SNIPPET:
bool IsPossible(int C, int N, int K, int index){
if(K == 0) //K = 0 and there exists intersecting intervals
return false;
int maxi = 0; //Maximum gap available to relocate interval
int maxE = 0; //Largest End range encountered so far.
int RangeSize = A[index].second - A[index].first + 1;
//Size of range A[index]
for(int i = 0; i < N; i++){
//Handling case where i = index
if(i == index) i++;
if(maxE >= A[i].first) //Intersecting intervals still exist
return false;
maxi = max(maxi, A[i].first - maxE - 1); //Update maxi
maxE = max(maxE, A[i].second); //Update maxE
}
maxi = max(maxi, C - maxE); //The corner case (no pun intended)
if(maxi < RangeSize)
return false;
return true;
}
vector<pair<int, int>> A(N); //To hold the ranges of the N intervals
for(auto &i : A) //Read about range-based loops in C++14 if new to you
cin >> i.first >> i.second; //Take input of range
sort(A.begin(), A.end()); //Sort the ranges
bool poss = true; // Possible to have disjoint ranges
for(int i = 0; i < N - 1; i++){
if(A[i].second < A[i + 1].first) //Ranges don't intersect
continue;
//If A[i] and A[i + 1] intersect...
poss = IsPossible(C, N, K, i) | IsPossible(C, N, K, i + 1);
//Check if ordering exists
break;
}
if(poss) cout << "Good" << endl;
else cout << "Bad" << endl;
TIME COMPLEXITY:
Sorting the array takes O(N\log N).
We run a single iteration over the array to find the first intersecting interval. This has complexity O(N).
There are at max, only 2 calls to function IsPossible()
which has time complexity O(N) (single iteration through the array).
Thus the overall complexity is
SOLUTIONS:
Editorialist’s solution can be found here.
SIMILAR PROBLEMS:
The search continues! Will add as and when I find them.
Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!
Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome editorial)
- 1
- 2
- 3
- 4
- 5
0 voters
Also don’t forget to up-vote this post if you liked it !