PROBLEM LINK:
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:
- Use binary search on area.
- 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):
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[i].first, A[i].second = input
mymap[A[i].second]++
sort(A)
//we unmark the first M breadths after sorting
for i=0 to M-1:
map_dec(mymap, A[i].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[i].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).