I want someone to explain the algorithm clearly for zco question no 2 and explain me how does algorithm give answer to this input.
U re allowed to make 1 change
12 cakes,5 children
0 based indexing
The ranges are [1,2],[3,4],[0,4],[10,11].
Please also give a note about time complexity.
Sry I couldn’t completely understand the algorithm given in other thread zco discussion.
Link to question
The cake one
2 Likes
Ya, it would be helpful if someone can explain the algorithm. Thanks in advance
Please provide proper problem description and/or relevant links, otherwise I don’t see how anyone can help you except for those who know exactly what you’re talking about.
@meooow https://www.commonlounge.com/discussion/7ca7510fa3ad4ac6b07ea0fe2127db73/main this link has the question
I don’t know my answer was time-efficient or not, but here is my solution:
First of all, find an interval which is overlapping. I think that can be done by sorting the intervals and one for-loop. So the time complexity till here is O(nlogn).
In the first case of an overlap, just take the two overlapping intervals and check whether there is a situation possible wherein you cannot shift any one of the intervals without overlapping. You can do that by storing all the ‘sizes’ of the free spaces on the cake in some vector or array and comparing the size of the interval-being-checked with it. If the intervals can be placed without overlapping, continue to the next part, else, print “BAD”. If shifted, make a boolean variable shifted = true;
Next part: Check again for the rest overlapping intervals. Same for the other intervals. If shifted = true, cake-good = false;
If you find any mistakes, feel free to point out. I think this was a typical brute force.
Your sample input was [1,2],[3,4],[0,4],[10,11]. Let’s go step by step.
-
Sort’em up. [0, 4], [1, 2], [3, 4], [10, 11].
-
Free Spaces: (i) (1-4)-1<0 --> NOT CONSIDERED.
(ii) (3-2)-1=0 --> NOT CONSIDERED.
(iii) (10-4)-1 --> 5 --> push into sizes vector. -
Overlapping Intervals: [0,4] & [1, 2], [0, 4] & [3, 4] .
-
Overlapping sizes: (4-0)+1 = 5; (2-1)+1 = 2;
-
Size 5 is present in vector sizes. Can be shifted. Cake-good = true; shifted = true;
-
Next Overlapping Items: [0,4] & [3,4].
-
shifted = true; cake-good = false;
-
Next Overlapping Items: None.
-
Print output: Cake-good --> BAD.
Peace. 
@prajneya only one shift possible
Ur algorithm will fail in this input
Input
Shift allowed,
No of students 4
12 cakes
Ranges [0,3],[1,2],[6,8],[7,8]
@lokesh2002 Sorry I forgot the details of the question. Only one shift could be done. Updated again.
@prajneya your algorithm will not work for a case like this: 4 cakes and 2 students, ranges are [0 1], [1 2]. The range [1 2] can be shifted to [2 3] but your algorithm will not find enough space for it.
@lokesh2002 This approach should work:
- Sort the ranges by start point and then by end point.
- Check every adjacent pair for overlap.
- If number of overlapping pairs is more than 0 and allowed shifts is 0 then it is bad.
- If number of overlapping pairs is more than 2 and allowed shifts is 1 then it is bad.
- If there is one overlapping pair and one shift allowed do this: For each range of the pair, remove it from the list and check if there is enough space between the remaining ranges to insert it. If it can be done for one or both ranges then it is good, else bad.
- If there are two overlapping pairs and one shift allowed do this: For a shift to be possible the two pairs must have one element in common, so they are actually 3 adjacent elements. Now a shift may be possible in 2 ways:
- The first and third of the 3 do not intersect. Then check whether the middle range can be removed and made to fit in any other place.
- The largest of the 3 covers the other two, which are disjoint. Then check whether this large range can be fit anywhere else.
The complexity is dominated by sorting, which takes \mathcal{O}(n \log n).
@meooow it doesn’t work because for this case ,1swap allowed no of cakes 11 and 4 children ,ranges are [1,2],[2,3],[1,3],[8,9]
It does work for this case. The answer is bad. But you’re right, it doesn’t work always, I missed out one case actually. I have updated the answer. Let me know if I have missed any other situation.
sry @meooow still wrong ,take the case
1 swap allowed
14 cakes
4 children
ranges [1,2],[3,4],[5,6],[1,5];
u have three overlap still it is good
Hmm you’re right. The problem is not as simple as I thought. What were the constraints? If \mathcal{O}(n^2) is allowed then it is a matter of removing every range one by one and checking.