You are not logged in. Please login at www.codechef.com to post your questions!

×

MAXREMOV - Editorial

2
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

This question is marked "community wiki".

asked 17 Feb, 19:08

deadwing97's gravatar image

3★deadwing97
1181234
accept rate: 0%

edited 18 Feb, 02:35

admin's gravatar image

0★admin ♦♦
19.8k350498541


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;
        }
    }
link

answered 18 Feb, 23:51

rajput1999's gravatar image

5★rajput1999
3716
accept rate: 0%

edited 18 Feb, 23:55

if you want full code please ask in comments

(18 Feb, 23:53) rajput19995★

@rajput1999, can u please share your code

(23 Feb, 13:50) vandana_982★

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

link

answered 18 Feb, 08:40

harendrasingh's gravatar image

3★harendrasingh
642
accept rate: 12%

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].

link

answered 18 Feb, 11:18

shoom's gravatar image

6★shoom
3534
accept rate: 30%

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

My Code

link

answered 18 Feb, 11:29

satyankar_2005's gravatar image

2★satyankar_2005
91
accept rate: 0%

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.

link

answered 18 Feb, 11:58

parker7's gravatar image

3★parker7
1
accept rate: 0%

@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))$.

link

answered 18 Feb, 12:57

theoneyouwant's gravatar image

5★theoneyouwant
434
accept rate: 0%

@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 :-)

link

answered 19 Feb, 00:03

secrex's gravatar image

3★secrex
1
accept rate: 0%

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

(19 Feb, 00:33) secrex3★

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

link

answered 22 Feb, 14:13

rock2000's gravatar image

2★rock2000
1
accept rate: 0%

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

link

answered 22 Feb, 14:13

rock2000's gravatar image

2★rock2000
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×968
×43
×7

question asked: 17 Feb, 19:08

question was seen: 2,606 times

last updated: 23 Feb, 13:53