MAXREMOV - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: [Abhinav Jain]
Tester: Michael Nematollahi
Editorialist: Hussain Kara Fallah

DIFFICULTY:

Easy-Medium

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=i-1.

(R=i-1 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).

for(int i = 1 ; i ≤ C ; i++)
   height[i] = height[i-1] + change[i];

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 (L-1)^{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:

AUTHOR’s solution

TESTER’s solution

2 Likes
2

Can someone help me optimise my code… I believe it’s the same complexity but I got a TLE

https://www.codechef.com/viewsolution/23136141

3

Few minor comments (I didn’t participate in the competition, just solved it for practice afterwards):

1.height doesn’t even need to be an array since, it is used only to update target and targetplus.

2.target and targetplus can be combined into one array that keep the difference in the number of cakes with the final height K+1 and K in the first i cakes (e.g. count[i], which is equal to targetplus[i] - target[i]). In addition we need to calculate a total final number of cakes of height K (let’s call it K_count). Then the removal of range [L,R] makes the number of cakes of size K equal to: K_count + count[R] - count[L-1].

4

Can someone optimise my (noob’s) code with the same logic I am using?

My Code

5

I used segment tree approach to solve the problem.
I am unable to understand why does my code results in WA, Please Help!
Solution Link.

6

@parker7, You can see my solution here for a (I believe) correct segment tree approach. However, this gets TLE as the complexity is O(T*10^5log(10^5)).

7

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[i-1]

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

for(i=1;i<=100000;i++)
{  
   if(height[i]==k)vk.push_back(i);
   if(height[i]==k+1)vg.push_back(i);
}

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 k-1 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 X-Y+Z
for whichever query the value of X-Y+Z is maximum will be our answer

for(i=1;i<=n;i++)
{
        low=lower_bound (vk.begin(), vk.end(), l[i]);
        up= upper_bound (vk.begin(), vk.end(), r[i]);
        Y=up-low;
   
        low=lower_bound (vg.begin(), vg.end(), l[i]);
        up= upper_bound (vg.begin(), vg.end(), r[i]);
        Z=up-low;
        if(max<X-Y+Z)
        {
            max=X-y+Z;
        }
    }
1 Like
8

if you want full code please ask in comments

9

@rajput1999 , your solution is just too brilliant :slight_smile: Can you please give the code? I can’t upvote because I don’t have enough reputation points :slight_smile:

10

Your approach might give TLE as finding lower_bound and upper_bound takes O(logN) time :slight_smile:

11

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]–;
}

12

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]–;
}

13

@rajput1999, can u please share your code