ANUAHR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Minako Kojima
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM

PRE-REQUISITES:

Binary Search, Basic math, Data Structures

PROBLEM:

You have N rectangles of sides Li, Bi. You can move them and place them anywhere, but you cannot rotate them. You can also remove M of those rectangles. Finally we take the intersection of left rectangles. What is the maximum possible intersection area.
N ≤ 105.

QUICK EXPLANATION:

  1. Use binary search on area.
  2. Sort pair of (L_i,B_i). In each step from i=0 to M, consider to remove first i rectangles. After removing first i rectangles, we can delete M - i more smallest breadths from available rectangles and we’ll get the maximum area.

EXPLANATION:

One of the most basic things is that we’ll keep left bottom vertices of all rectangles are origin. For example in a way like this(different colors represent different rectangles):

img

This will always give us the maximum intersection area possible. It is a very intuitive result, however we can think like if we increase y-coordinate of any rectangle(keeping everyone else at origin) it’ll never cause us profit.

First of all let’s find intersection area if we can’t remove any rectangle:
It’s min(Li) * min(Bi). (Length and breadth of intersection can’t exceed the min length and min breadth).

Now that we can remove M rectangles, we will be able to achieve better results since we can increase minimum of lengths and breadths.

APPROACH1:

An interesting thing to note here will be that if our answer area is A(ie. most optimal solution), any area less than A will also be possible. So, we can do binary search here. For binary search, we’ll have to check if an area A is possible to achieve by deleting atmost M rectangles.

To check if an area A is possible, we traverse over all rectangles and do the following process:

Assuming Li is the minimum length after deletions. So, all rectangles that wouldn’t have been deleted would have length greater than Li. Also, since we are achieving area A, all remaining rectangles will have breadth atleast A/(Bi). Let’s say K is number of rectangles j where Lj ≤ Li and Bj ≤ A/(Bi). If K ≤ M(ie. we have deleted atmost M rectangles), it’s possible to achieve this area.

So, we have a list of pairs (x_i, y_i) and for a given i, we query: find number of pairs j such that x_j ≤ x_i and y_j ≤ (A/y_i). We’ll need to do this for all i. The order in which we do such queries is not important here.
So, we sort the list of pairs first. How does this help?
Choosing the index i in new sorted list means that all pairs with index greater than i are straightaway excluded from scrutiny(because their x is surely greater than x_i). And now we need to count number of possible j ≤ i, such that y_j ≤ (A/y_i). For this we can use a BIT. While going in increasing order of i, we keep marking the positions of y_j in the BIT and then we can count number of y_j less than A/y_i. But for that we’ll need to use coordinate compression(because x_i, y_i are less than 109). Coordinate compression basically means mapping larger values to smallers values(because there are only 2*N distinct values of x_i and y_i).
Complexity here would be O(log(A) * N * log MAX). where MAX = 2*N and A = 1018 in worst case.

AN EASIER APPROACH:

An easier approach would be to fix the answer as L * B, we then need to remove all rectangles whose Li < L or Bi < B. Note that these L and B belong to one of the rectangles length and breadth(not necessarily the same rectangle).
Instead of fixing both L and B, we fix L and then let’s try to find the maximum B possible. So, we remove all rectangles with Li < L. Let’s say we have removed m rectangles now. We can remove M - m more rectangles now. As we want to maximize B, we should remove rectangles with least Bi of the remaining rectangles.

How do we implement this with good complexity? Doing it naively would result in high complexity.
Look at this psuedo code for the algorithm:

//reduces the count of key x in mymap
//remove the key if count is reduced to 0
map_dec(mymap, x):
    mymap[x]--;
    if mymap[x]==0:
        myamp.erase(x)

map < int , int > mymap;

//we keep a list of pair A
//we mark all breadths in a map
for i=0 to N-1:
    A*.first, A*.second = input
    mymap[A*.second]++

sort(A)

//we unmark the first M breadths after sorting
for i=0 to M-1:
    map_dec(mymap, A*.second)
    
ans=0
for i=m-1 to -1:
    //i denotes that we have deleted first (i+1) elements of sorted A
    //A[i+1].first is the smallest length now
    //of all the marked breadths we take the minimum breadth
    curans = A[i+1].first * mymap.begin()->first;
    ans = max(ans, curans)
    
    //we are done
    if(i==-1)break;
    
    //we mark the breadth of i'th rectangle
    //because in next iteration we'll consider it to be present
    S.insert(A*.second);
    
    //now, in next iteration we'll have an option to delete 1 more extra breadth
    //so we delete the minimum breadth available to us till now
	map_dec(mymap, mymap.begin()->first);
    
print ans

Complexity: O(N log N + M log N).

SOLUTIONS:

Setter’s solution
Tester’s solution

1 Like

if suppose the ith breadth included comes to the begining of multiset(as per setter code) & later on it is deleted (as u have 1 choice extra ) then in next iteration its length is being considered which has been alredy deleted previously .

clarify if i misunderstood something!!!

I did it as follows:

  1. Sort the length and width arrays separately (with index).
  2. Take first m rectangles from second list and mark them as removed2.
  3. Take w as the position of minimum width which is not removed. Then w=m.
  4. Initial ans=Length[0]*Width[m]
  5. Iterate on first list. Try to remove the ith element from this list, mark it in remmoved1.
  6. If this rectangle is already marked in removed2, then ans=max(ans,Length[i+1]*Width[w])
  7. Otherwise we remove the first member from the current position in list2 going towards left which is not marked as removed1 and set its removed2 to zero. This is now w.
  8. If there is no such rectangle this means that we cannot remove the ith rectangle from first list, so end the loop.
  9. Otherwise ans=max(ans,Length[i+1]*Width[w])

Code : Contest ,Practice

2 Likes

@darkshadows do you mind explaining the easier approach in more intuitively? I’m just not able to get my head around the logic. Also, are you sorting based on the first value in the pair?

Thanks.

Regards,
Ankit