PROBLEM LINK:Author: [Abhinav Jain] DIFFICULTY:EasyMedium PREREQUISITES:None PROBLEM:You have $C=100,000$ cakes, numbered $1$ through $C$. Each cake has an integer height. Initially, the height of each cake is $0$. There are $Q$ operations. In each operation, you are given two integers $L$ and $R$ and you should increase by 1 the height of all cakes at positions $[L,L+1,…,R]$. One of these $Q$ operations should be removed and the remaining $Q−1$ operations are then performed. Given $K$, help chef by finding one operation to remove such that after performing remaining operations the number of cakes with a height of exactly $K$ is maximum possible. EXPLANATION:We will discuss a linear solution to this problem. Let's first assume that all operations are performed. How can we calculate cakes' heights after all operations are finished? Let's read all the operations first. Then, let's iterate through cakes from the first one till the last one. Suppose that we are processing currently the $i_{th}$ cake. If there is some operation which has $L=i$ that means that we must increase the heights of all cakes while we are moving forward until $R+1=i$. When $R+1=i$ that mentioned operation won't affect any more cakes. So we should keep an array $change[1\,...\,C]$. $change_i$ denotes the number of queries with $L=i$ minus the number of queries with $R=i1$. ($R=i1$ because the $R_{th}$ cake should be incremented and the increment must be canceled at $R+1$). So how to calculate the final heights? (Think a little bit).
Simple !! Now which query we should remove? Let's think about the outcome of removing one operation and canceling its effects. All cakes between the $L_{th}$ and the $R_{th}$ (inclusive) will have their heights decreased by 1. So after removing a certain operation, the number of cakes with height $K$ is equal to $A+B+C$ A = number of cakes with a height equal to exactly $K$ between the $1^{st}$ cake and the $(L1)^{th}$ cake B = number of cakes with a height equal to exactly $K+1$ between the $L^{th}$ cake and the $R^{th}$ cake C = number of cakes with a height equal to exactly $K$ between the $(R+1)^{th}$ cake and the last cake. So after calculating the heights resulting from applying the operations, we are interested in only 2 heights. $K$ and $(K+1)$. Keep 2 prefix sum arrays, $target[1\,...\,C]$ , $targetplus[1\,...,C]$ $target_i$ denotes the number of cakes with final height equal to $K$ among the first $i$ cakes. $targetplus_i$ denotes the number of cakes with final height equal to $K+1$ among the first $i$ cakes. Now, it's easy to check each operation and check the effect of removal and update our answer accordingly. Check codes for more details. Complexity $O(N + Q)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 17 Feb, 19:08

I approached this problem in slightly different way. firstly we need to calculate final heights after all queries sre processed for this purpose take an height array of length 100002 and initialize it to zero height[100002]={0} then for each and every query do height[l]++ and height[r+1] then run a loop from 1 to 100000 and do height[i]=height[i]+height[i1] this will give you final heights after all queries now one question arises that which query should be removed ?? for this purpose you can create 2 vectors and vk and vg running loop from i=1 to i=100000 we will push all indexes of elements equal to k in vk and all elements equal to k+1 in vg
intial numbers of heights with value k be X = vk.size() now we will process each and every query one by one : if we will remove a query (l,r) than all Y elements of vk lying between l and r will be reduced from k to k1 and all Z elements of vg lying between l and r will be reduced from k+1 to k thus after removing query (l,r) the new munber of heights which are equal to k is XY+Z for whichever query the value of XY+Z is maximum will be our answer
answered 18 Feb, 23:51
if you want full code please ask in comments
(18 Feb, 23:53)
@rajput1999, can u please share your code
(23 Feb, 13:50)

Can someone help me optimise my code... I believe it's the same complexity but I got a TLE answered 18 Feb, 08:40

Few minor comments (I didn't participate in the competition, just solved it for practice afterwards): 1. 2. answered 18 Feb, 11:18

@rajput1999 , your solution is just too brilliant :) Can you please give the code? I can't upvote because I don't have enough reputation points :) answered 19 Feb, 00:03
Your approach might give TLE as finding lower_bound and upper_bound takes O(logN) time :)
(19 Feb, 00:33)

can you please tell me what is it in author's solution saying 1 based index. i don't understand what is he doing when he is writing : for(i=0;i<n;i++) {="" cin="">>l[i]>>r[i];// 1 based indexing A[l[i]]++; A[r[i]+1]; } answered 22 Feb, 14:13

can you please tell me what is it in author's solution saying 1 based index. i don't understand what is he doing when he is writing : for(i=0;i<n;i++) {="" cin="">>l[i]>>r[i];// 1 based indexing A[l[i]]++; A[r[i]+1]; } answered 22 Feb, 14:13
