MOVINTRL-Editorial

PROBLEM LINK:

Practice

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

s_i\le e_i < s_j\le e_j

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,

s_i\le e_i < s_{i+1}\le e_{i+1}

should hold for all i.

This would imply

s_1\le e_1 < s_2\le e_2 < \dots < s_N\le e_N

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

O(N\log N+N)\approx O(N\log N)

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

[x,x+k]\space(1\le x\le x+k\le C)

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

(s_j-1)-(maxE+1)+1\Rarr s_j-maxE-1

Thus, we update

maxi=\max(maxi, s_j-maxE-1)

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

maxE=\max(maxE,e_j)

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, where false 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 and index. Initialize 2 variables maxi and maxE, 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 return false.
  • We finally update the value of poss to false only if both IsPossible(<input values>, index) and IsPossible(<input values>, index + 1) returns false;
  • Lastly, we print Good if flag = true and Bad 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

O(N\log N+N+2*N) \approx O(N\log N)

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 :star_struck: editorial)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

Also don’t forget to up-vote this post if you liked it ! :smile:

5 Likes

Hey @infinitepro,

Your editorial is awesome, just read it right now. The only thing I suggest is to decrease the length of your editorial. In other words, I mean to make it concise. If somehow you could reduce the size of the explanation, it would be nice.

2 Likes

My editorials are made, keeping in mind the level of newbies to competitive programming, especially those answering ZCO for the first time.
I have included the intuitions in every subtask which eventually leads us to the 100 point solution. For more experienced coders, the quick explanation is ideal and gives a gist of the entire solution.
It may look like I’m repeating a few points multiple times or elaborating on things I shouldn’t stress much upon, but skipping these explanations would make it difficult for beginners to understand.
However, keeping in mind your suggestion, I shall try to make the future editorials more crisp in terms of its content. :smile:

6 Likes

Length should not be a factor at all when reading editorial. If someone wants to learn, he has to put effort in reading. What matters is, whats written making sense to them.

If someone has to read a 500 word editorial 10 times to get it v/s a 2k worded editorial once to understand it, you get the case.

Also, the editorial discusses solution to almost every subtask, so it has to be a bit lengthy. Developing solution from brute force is a neat trick and very intuitive, but sadly a bit lengthy but thats not at all any severe downside.

9 Likes