ZCO - MOVINTRL (Unofficial) Editorial

THIS EDITORIAL IS AN UNOFFICIAL ONE AND THE REASONING BEHIND THE LOGIC MAY DIFFER FROM THE OFFICIAL ONE.

PROBLEM LINK:

Contest

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given C cakes, the limits(lower and upper) of N children and an integer K
find whether each cake is eaten by at most a single child. If k is 1, you can request one child to chose a different set of cakes of the SAME size.

QUICK EXPLANATION:

Find out the first index where an intersection of the limits (cake is eaten more than 1 child) is happening. Remove both the indexes in two turns, and see whether the following is happening:

  1. No fight between the rest of the children
  2. There is an interval which could be given to the child we did not consider, and still no fights take place.

EXPLANATION:

We have two cases,

  1. K = 0.
  2. K = 1.

When K = 0,
Here you CAN’T persuade a child to take different set of cakes. So there are only two options, either a fight takes place, or it doesn’t. This is very straight-forward.

Solution Snippet
pair<int, int> a[MAXN]; //this is the array which stores the limits of the children
bool f = false;
for(int i = 1; i < n; i++) { // 1 indexed
    if(a[i].second >= a[i].first) {
        f = true;
        break;
    }             
}

When K = 1,
Here you CAN persuade at most one child to take different set of cakes. Now if you think of doing it with simple if-else construct, there are a variety of EDGE cases which will fail on your code. You might spend days doing this problem, while you don’t get in ZCO. So the if-else construct is not our answer.

What can we gain more from the question? Think it yourself.

Answer

We can understand that whenever there is an intersection of limits, we need to move one of the children. Either it is the first one or the second one.

So we have till now discovered the logic, but NOT the implementation.
This problem is implementation based, many know the logic but fail to implement it for 100.

Think of the implementation. Try it, then revert back.

Implementation

Okay, so here is the way to go about it. We have the index of the children who are fighting. I will be calling the children first child and second child. Let us think that the first child wasn’t there and k = 0. Now we have to check whether another set of children are fighting or not. If yes, then it is Bad.

Now, the question arises where can we place the child we assumed wasn’t there. Obviously, we will chose the maximum distance between two intervals. If this is greater than the size of the limits of the first child, then you can put the child over there, else not.

Hint

There are spaces before the first child and after the last child. (Here, I am referring to the children in the array taken as input).

Now do the same thing with the second child.

Solution Snippet
max_gap = (idx == 1) ? (a[2].first - 1) : (a[1].first - 1);//maximum gap between two intervals
max_right = 0;//the rightmost cake which is eaten by a child
for (int i = 1; i <= n; i++)
{
    if (i == idx)//as we are not taking the idx into the consideration. Idx is the child whose limits intersect with any other child.
        continue;
    max_right = max(max_right, a[i].second);
    j = (i + 1 == idx) ? (i + 2) : (i + 1);..not considering idx
    if (j > n) continue;
    if (a[i].second >= a[j].first)
    {
        return false;
    }
    max_gap = max(max_gap, a[j].first - a[i].second);
}
max_gap = max(max_gap, c - max_right);

TIME COMPLEXITY:

O(N) per test case

SOLUTION:

My solution.

Any comments on how to improve this editorial are openly welcomed!

3 Likes

Good approach and clear explanation, thanks.

I went a slightly different way, identifying all fights first. Note that you can have more than one “fight”, and it may be resolvable provided there a child common to all fights.

For example
9 3 1
6 7
5 9
8 9

But if there’s no common child to multiple fights, or any cake is claimed by more than two children, there’s no resolution possible.

With just one fight you still need the option of shifting either child of course.

2 Likes

Yes, if you see my first submission 100 point submission, I have done the same thing. Identifying the fights and then applying the operations. Then the way I have shown in the editorial, struck my mind. I did it for 100 points, and as this was easier to make people understand, I thought of this method.

1 Like