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

# PROBLEM LINK:

# 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:

- No fight between the rest of the children
- 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,

- K = 0.
- 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:

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