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 about 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!