DAREA - Editorial

[bhanu_parashar]

Hi , can anyone please suggest where I am going wrong in this solution:

#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include <bits/stdc++.h>

using namespace std;

void printBox(long long box[])
{
    cout<<"[ ";
    for(long long i=0;i<4;i++)
        cout<<box[i]<<" ";
    cout<<"]\n";
}

bool inquad(long long quad[],pair<long long,long long> point)
{
    long long x = point.first;
    long long y = point.second;
    //printBox(quad);
    //cout<<x<<","<<y<<"\n"; 
    if(x>=quad[0] and y>=quad[2] and x<=quad[1] and y<=quad[3])
        {
            return true;
        }
    return false;
}

long long area(long long box[])
{
    return (box[1]-box[0])*(box[3]-box[2]);
}
long long join(long long box1[],long long box2[])
{
    long long f1=box1[0];
    long long f2=box2[0];
    if(f1 ==-1 and f2 == -1)
        return 0;
    if(f1 == -1)
        return area(box2);
    if(f2 == -1)
        return area(box1);

    long long b[4];
    b[0] = min(box1[0],box2[0]);
    b[1] = max(box1[1],box2[1]);
    b[2] = min(box1[2],box2[2]);
    b[3] = max(box1[3],box2[3]);
    return area(b);
}

void updateBox(long long (&box)[4],pair<long long,long long> point)
{
    long long x = point.first;
    long long y = point.second;

    if(box[0] == -1 or box[0]>x)
        box[0] = x;
    if(box[1] == -1 or box[1]<x)
        box[1] = x;
    if(box[2] == -1 or box[2]>y)
        box[2] = y;
    if(box[3] == -1 or box[3]<y)
        box[3] = y;
}


pair<long long,long long> points[100002];

int main()
{
    // ios_base::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
    long long T;
    cin>>T;
    while (T--)
    {
        long long N;
        cin>>N;
        //vector<pair<long long,long long>> points;
        long long left = -1, right = -1, top = -1, bottom = -1;
        for(long long i=0;i<N;i++)
        {
            long long x,y;
            cin>>x>>y;
            points[i] = make_pair(x,y);
            if(left == -1 || left>x)
            {
                left = x;
            }
            if(right == -1 || right<x)
            {
                right = x;
            }
            if(top == -1 || top>y)
            {
                top = y;
            }
            if(bottom == -1 || bottom<y)
            {
                bottom = y;
            }
        }
        long long midx = (left+right)/2;
        long long midy = (top+bottom)/2;

        long long Q[4][4];
        
        // cout<<left<<" "<<right<<" "<<top<<" "<<bottom<<"\n";
        Q[0][0] = left;
        Q[0][1] = midx;
        Q[0][2] = top;
        Q[0][3] = midy;
        
        Q[1][0] = midx;
        Q[1][1] = right;
        Q[1][2] = top;
        Q[1][3] = midy;
        
        Q[2][0] = left;
        Q[2][1] = midx;
        Q[2][2] = midy;
        Q[2][3] = bottom;

        Q[3][0] = midx;
        Q[3][1] = right;
        Q[3][2] = midy;
        Q[3][3] = bottom;

        long long box[4][4];
        for(long long i=0;i<4;i++)
            for(long long j=0;j<4;j++)
                box[i][j]=-1;
        for(long long i=0;i<N;i++)
        {
            for(long long j=0;j<4;j++)
            {
                if(inquad(Q[j],points[i]))
                {
                    updateBox(box[j],points[i]);
                    break;
                }
            }
        }

        long long a1 = join(box[0],box[1])+join(box[2],box[3]);
        long long a2 = join(box[0],box[2])+join(box[1],box[3]);

        cout<<min(a1,a2)<<"\n";
    }
}

[dm89f11]

how is multi set used here?

[emotiological]

@taran_1407

This line splits the original point set P into two sets P1 ​ and P2 ​ such that P1 ​ contains points with x-coordinate strictly smaller than a, and P2 ​ contains points with x-coordinate greater than or equal to a. We need to find value of f(P1) + f(P2) for these sets.

@taran_1407
You have written here that sides will not touch of two rectangle according to this if I am not wrong. But I do not think it is true.

Also, test cases were weak, my code passed AC but fails at:
1
19
1 1
2 1
3 1
1 2
1 3
1 4
1 5
3 2
3 3
3 4
3 5
3 6
3 7
3 8
4 8
5 8
5 7
5 6
5 5

[rushi2001]

@emotiological
what is the expected o/p for this tc ?

[emotiological]

14

[rushi2001]

I tried with my code and its giving me ans 14
but it is giving me wrong ans for all the subtasks , i dont know why ?

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

Here is link to my query

Whats Wrong in my code?

I am solving a question Minimal Dual Area from the latest june challenge . https://www.codechef.com/JUNE21B/problems/DAREA I tried the approach as similar mentioned in editorial . In the util array of size n*4 i am storing at utili,0 the minimum x from top to i utili,1 the maximum x from top to i utili,2 the minimum y from top to i utili,3 the maximum y from top to i While in next i am storing from bottom to i the same things mentioned above . And in last loop i am finding …

Can you plz tell me whats wrong with my code , It will be really helpful .

[david_s]

After sorting the points by X then Y, I used a binary tree for the minimum Y and another for the maximum Y. Then for any range of points from 1 to K we can find the minimum or maximum Y from the corresponding tree in O(log N) time. To evaluate possible horizontal divisions I swap the X and Y coordinates of all the points and use the same code as for vertical divisions. The overall rime complexity remains O(NlogN). You can see my solution at CodeChef: Practical coding for everyone

[anon43494225]

I am unable to understand the solution even after watching the editorial video 3 times. I’ve understood how the prefix and suffix arrays are being calculated and all the other stuff. But not understanding why did they do it. Any suggestions?! Pls help.

[anupam_codecs]

I don’t think the test cases had a scenario where the sides of rectangles touch each other. Following is a test case for that scenario where Author’s solution fails! (while the Editor’s solution is correct). The correct ans is 55 while Author’s solution gives 56.

1
20
3 5
9 0
5 2
3 1
9 6
0 6
5 6
7 7
2 9
4 7
6 3
2 3
7 6
8 6
6 4
1 7
2 5
9 4
5 5
2 2

The two rectangles represented by lower-left corner and upper-right corner are {(0, 6), (2, 9} and {(2, 0), (9, 7)}

[paramchattani]

I got 3 AC out of 4 but just can’t find why it fails on 4th case . Also I used ordered map . I only used only minimum y and maximum y [thats why map used ] for a particular x while sorting in x , and then i increased area for left rectangle and decreased for right rectangle while moving from left to right . If anyone can review code , I would be helpful

‘’’

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
ll int grid[n][2];
// vector<pair<int,int>> xy;
for(int i=0;i<n;i++)
{
cin>>grid[i][0]>>grid[i][1];
// xy.push_back({grid[i][0],grid[i][1]});
}

     //sort(xy.begin(),xy.end());
     
     map<ll int,ll int> largemap;
     map<ll int,ll int> smallmap;
     for(int i=0;i<n;i++)
     {
         largemap[grid[i][0]]=max(largemap[grid[i][0]],grid[i][1]);
     }
     
     for(int i=0;i<n;i++)
     {
         if(smallmap.find(grid[i][0])!=smallmap.end())
         {
             smallmap[grid[i][0]]=min(smallmap[grid[i][0]],grid[i][1]);
         }
         else
         smallmap[grid[i][0]]=grid[i][1];
     }
     
     
     
map<ll int,ll int>::reverse_iterator big=largemap.rbegin();
map<ll int,ll int>::reverse_iterator small=smallmap.rbegin();
ll int miny[smallmap.size()];
ll int maxy[largemap.size()];
maxy[largemap.size()-1]=big->second;
miny[smallmap.size()-1]=small->second;
big++;
small++;
 int index=largemap.size()-2;
//map<int,int>::iterator starting=largemap.begin();
//starting--;
//map<
for(;big!=largemap.rend();big++)
{
    maxy[index]=max(big->second,maxy[index+1]);
    miny[index]=min(small->second,miny[index+1]);
    small++;
    index--;
}
    //for(int i=0;i<largemap.size();i++)
//    cout<<maxy[i]<<" "<<miny[i];
  //  cout<<endl;

map<ll int,ll int>::iterator start=largemap.begin();
map<ll int,ll int>::iterator startmin=smallmap.begin();

map<ll int,ll int>::iterator constantmax=largemap.begin();
map<ll int,ll int>::iterator constantmin=smallmap.begin();

map<ll int,ll int>::iterator initial=smallmap.begin();

map<ll int,ll int>::reverse_iterator end=largemap.rbegin();
ll int leftmaxy=start->second;
ll int leftminy=startmin->second;
//cout<<leftmaxy<<leftminy;
//cout<<end->first<<start->first;
ll int totalarea=(maxy[0]-miny[0])*((end->first)-(start->first)); 
//ll int totalarea=LONG_MAX;
start++;
startmin++;
int ind=1;
for(;start!=largemap.end();start++)
{
    leftminy=min(leftminy,constantmin->second);
    leftmaxy=max(leftmaxy,constantmax->second);
    //cout<<leftminy<<leftmaxy;
    //cout<<(leftmaxy-leftminy)*((constantmax->first)-(initial->first));
  //  cout<<endl;
 totalarea=min(totalarea,(maxy[ind]-miny[ind])*((end->first)-(start->first)) + (leftmaxy-leftminy)*((constantmax->first)-(initial->first)));
    
    startmin++;
    constantmin++;
    constantmax++;
    ind++;
}
//cout<<totalarea<<endl;
ll int firstresult=totalarea;

//------------------------------------------------------------
//for y now , similar approach , its just copy paste of above code with grid changed from x,y to y,x
//------------------------------------------------------------

for(int i=0;i<n;i++)
{
ll int temp=grid[i][0];
grid[i][0]=grid[i][1];
grid[i][1]=temp;
}
largemap.clear();
smallmap.clear();
for(int i=0;i<n;i++)
{
largemap[grid[i][0]]=max(largemap[grid[i][0]],grid[i][1]);
}

     for(int i=0;i<n;i++)
     {
         if(smallmap.find(grid[i][0])!=smallmap.end())
         {
             smallmap[grid[i][0]]=min(smallmap[grid[i][0]],grid[i][1]);
         }
         else
         smallmap[grid[i][0]]=grid[i][1];
     }
     
     
     
 big=largemap.rbegin();
 small=smallmap.rbegin();
for(int i=0;i<largemap.size();i++)
{
    miny[i]=0;
    maxy[i]=0;
}
maxy[largemap.size()-1]=big->second;
miny[smallmap.size()-1]=small->second;
big++;
small++;
index=largemap.size()-2;
for(;big!=largemap.rend();big++)
{
    maxy[index]=max(big->second,maxy[index+1]);
    miny[index]=min(small->second,miny[index+1]);
    small++;
    index--;
}
    //for(int i=0;i<largemap.size();i++)
//    cout<<maxy[i]<<" "<<miny[i];
  //  cout<<endl;

     start=largemap.begin();
 startmin=smallmap.begin();

 constantmax=largemap.begin();
 constantmin=smallmap.begin();

 initial=smallmap.begin();

 end=largemap.rbegin();
leftmaxy=start->second;
leftminy=startmin->second;
//cout<<leftmaxy<<leftminy;
//cout<<end->first<<start->first;
 totalarea=(maxy[0]-miny[0])*((end->first)-(start->first)); 
//totalarea=LONG_MAX;
start++;
startmin++;
ind=1;
for(;start!=largemap.end();start++)
{
    leftminy=min(leftminy,constantmin->second);
    leftmaxy=max(leftmaxy,constantmax->second);
    //cout<<leftminy<<leftmaxy;
    //cout<<(leftmaxy-leftminy)*((constantmax->first)-(initial->first));
  //  cout<<endl;
 totalarea=min(totalarea,(maxy[ind]-miny[ind])*((end->first)-(start->first)) + (leftmaxy-leftminy)*((constantmax->first)-(initial->first)));
    startmin++;
    constantmin++;
    constantmax++;
    ind++;
}
ll int secondresult=totalarea;
cout<<min(firstresult,secondresult)<<endl;

}
}

‘’’

[anon33804904]

I thought I had a valid approach that would work but it didn’t. Now I’m struggling to find out why.

1. Sort all points by their X coordinates
2. Iterate over the list and find two points next to each other in the sorted list that have the greatest distance across the X axis. Let these points me A and B.
3. Find the area of the rectangle containing all points from the beginning of the list to A, and then from B to end of the list. Add these two up.

Repeat the same for a list sorted across Y axis.

Return the minimum of the result obtained by the above two procedures.

When does this approach not work and why??

[paramchattani]

That is partially correct , As I spent good amt . of hours with this problem . Following your words, There can be a case where when you merge A point in left rectangle, there can be a huge difference in y-coordinates.Lets call ydiff=ymax-ymin seen till x=A.[so the area would be

(Ax-0)*ydiff

(difference in y coordinates seen till now which could be huge) ] assuming first point starts at x=0.

Now when You take B point in right rectangle , there could be low variation in ycoordinates . Hence area for right rectangle (xmax-Bx )*ydiff.

Here ydiff is difference between maxy and min y from x=b to x=xmax

Now although A and B could be x coordinates with large difference but if we take A in
right rectangle and due to low variance in y , we might consider it to merge in right rectangle so that area could be low as area also contains another component which is
ydiff
I hope explanation is clear

[rahulnegi20]

Anyone used same approach on python3 or any different approach, i am struggling to follow the same on python someone help!

[dm89f11]

hey i tried exact same approach:
result only one test case passed CodeChef: Practical coding for everyone
i figured what was wrong after :

consider the case:

seperating rectangles vertically
ans1 = left rectangle + right rectangle
= (4-2)x(3-1) + (4-2)x(5-5)
= 4
seperating rectangles horizontally
ans2 = upper rectangle+ bottom rectangle
=(4-3)x(5-3)+(5-1)x(2-2)
= 2

you can see ans2 < ans1
hope you understood the test case here

[ificiana]

Hi, so I tried the brute force approach and wrote a code in python to test my idea… while it gives me correct output to every testcase I’m providing, when submitted I get WA

Can someone help me figure out what’s wrong?

This is my code:

def bb(c):

    min_x = 1e10
    min_y = 1e10
    max_x = -1
    max_y = -1

    for i in c:
        if i[0] < min_x: min_x = i[0]
        if i[0] > max_x: max_x = i[0]
        if i[1] < min_y: min_y = i[1]
        if i[1] > max_y: max_y = i[1]

    return [(min_x,min_y),(max_x,max_y)]

def bba(c, d):

    e = bb(c)
    f = bb(d)

    if(min(e[1][0], f[1][0]) <= max(e[0][0], f[0][0]) or min(e[1][1], f[1][1]) <= max(e[0][1], f[0][1])):
        ea = (e[1][0]-e[0][0])*(e[1][1]-e[0][1])
        fa = (f[1][0]-f[0][0])*(f[1][1]-f[0][1])
        return ea + fa
    return 1e10

t = int(input())
for i in range(t):
    n = int(input())
    p = [[0, 0]]*n
    q = 1e10
    for i in range(n):
          p[i] = [int(i) for i in input().split()]
    if n == 1: print(0)
    else:
        x = sorted(p, key= lambda a: a[0])
        y = sorted(p, key= lambda a: a[1])
        for i in range(n):
            q = min(bba(x[:i], x[i:]), q)
            q = min(bba(y[:i], y[i:]), q)
    print(int(q))

Thanks in advance!

[arpit92_8]

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

can anyone please tell me where I am going wrong?

[adhi01]

Solution satisfying this testcase.

Just check the same conditions and finding the minimum answers as the solution suggests.
But now you have to sort the coordinate array in 2 ways:

First array (coordinates stored as (x, y) in each pair):
First is the normal sort with (x1 < x2, or if x1 == x2 then y1 < y2)
Second sort is with (x1 > x2, or if x1 == x2 then y1 > y2)

Second array (coordinates stored as (y, x) in each pair):
First is the normal sort with (y1 < y2, or if y1 == y2 then x1 < x2)
Second sort is with (y1 > y2, or if y1 == y2 then x1 > x2)

You can also use one array and sort them in 4 ways using lambda sort and do the same process but taking 2 different array for (x, y) and (y, x) arrangement was easier to understand and implement.

By checking all the conditions on both the arrays we will cover all the possible rectangles that could be created and our solution will always be non - overlapping since overlapping case will have greater area than the non - overlapping counterpart.

[physicalworld]

I have been trying to solve this problem and my Code works correctly on all the test cases I can find even on some random test cases but it doesn’t always gives WA error when i try to submit. can Anyone help me with it.

Here is my code

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int n;

int sol(vector<pair <int, int>> cord) {

ll MIN, MAX = 0;

vector<pair<int, int>>cordR(n), prefix(n), suffix(n);

ll area = 0, sol = 1e9;

// X - Vertical line

for (int i = 0; i < n; i++)

{

    if (i == 0)

    {

        MIN = cord[i].second;

        MAX = cord[i].second;

    }

    else

    {

        MIN = min(cord[i].second, prefix[i - 1].first);

        MAX = max(cord[i].second, prefix[i - 1].second);

    }

    prefix[i] = {MIN, MAX};

}

for (int i = n - 1; i >= 0; i--)

{

    if (i == (n - 1))

    {

        MIN = cord[i].second;

        MAX = cord[i].second;

    }

    else

    {

        MIN = min(cord[i].second, suffix[i + 1].first);

        MAX = max(cord[i].second, suffix[i + 1].second);

    }

    suffix[i] = {MIN, MAX};

}

// Area for Vertical line

for (int i = 0; i < n; i++)

{

    if (n <= 2)

    {

        area = 0;

    }

    else if (i == 0 || i == (n - 1))

    {

        area = abs((cord[1].first - cord[n - 1].first) * (prefix[n - 1].second - prefix[n - 1].first));

    }

    else

    {

        area = abs((cord[i].first - cord[0].first) * (prefix[i].second - prefix[i].first) +

                   (cord[n - 1].first - cord[i + 1].first) * (suffix[i + 1].second - suffix[i + 1].first));

    }

    sol = min(sol, area);

}

return sol;

}

int main() {

int t;

cin >> t;

while (t--) {

    cin >> n;

    int sol1, sol2, x, y;

    

    vector <pair <int, int>> cord(n), cordR(n);

    

    for(int i = 0; i < n; i++) {

        cin >> x >> y;

        cord[i].first  = x;

        cord[i].second = y;

        cordR[i].first = y;

        cordR[i].second = x;

    }

    sort (cord.begin(), cord.end());

    sort (cordR.begin(), cordR.end());

    sol1 = sol(cord);

    sol2 = sol(cordR);

    

    cout << min(sol1, sol2) << "\n";

}

}

[physicalworld]

I have a similar type of approach but gives me correct output to every testcase I’m providing, when submitted I get WA. I don’t know what the problem is but if you find an please let me know

[archit385]

Can anyone tell me why this code is showing TLE. How can I optimize this

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static Long minSum(Point[] points) {
        if (points.length <= 2) return 0L;

        Arrays.sort(points, new sortByX());
        long sum1 = Long.MAX_VALUE;
        int[] prefymin = new int[points.length];
        int[] suffymin = new int[points.length];
        int[] prefymax = new int[points.length];
        int[] suffymax = new int[points.length];
        prefymin[0] = points[0].y;
        prefymax[0] = points[0].y;
        for (int i = 1; i < points.length; i++) {
            prefymin[i] = Math.min(prefymin[i - 1], points[i].y);
            prefymax[i] = Math.max(prefymax[i - 1], points[i].y);
        }
        suffymin[points.length - 1] = points[points.length - 1].y;
        suffymax[points.length - 1] = points[points.length - 1].y;
        for (int i = points.length - 2; i >= 0; i--) {
            suffymin[i] = Math.min(suffymin[i + 1], points[i].y);
            suffymax[i] = Math.max(suffymax[i + 1], points[i].y);
        }
        int spx = points[0].x;
        int epx = points[points.length - 1].x;
        for (int i = 0; i < points.length - 1; i++) {
            long num1 = (points[i].x - spx) * (long) (prefymax[i] - prefymin[i]);
            long num2 = (epx - points[i + 1].x) * (long) (suffymax[i + 1] - suffymin[i + 1]);
            sum1 = Math.min(sum1, num1 + num2);
        }
        Arrays.sort(points, new sortByY());
        long sum2 = Long.MAX_VALUE;
        int[] prefxmin = new int[points.length];
        int[] suffxmin = new int[points.length];
        int[] prefxmax = new int[points.length];
        int[] suffxmax = new int[points.length];
        prefxmin[0] = points[0].x;
        prefxmax[0] = points[0].x;
        for (int i = 1; i < points.length; i++) {
            prefxmin[i] = Math.min(prefxmin[i - 1], points[i].x);
            prefxmax[i] = Math.max(prefxmax[i - 1], points[i].x);
        }
        suffxmin[points.length - 1] = points[points.length - 1].x;
        suffxmax[points.length - 1] = points[points.length - 1].x;
        for (int i = points.length - 2; i >= 0; i--) {
            suffxmin[i] = Math.min(suffxmin[i + 1], points[i].x);
            suffxmax[i] = Math.max(suffxmax[i + 1], points[i].x);
        }
        int spy = points[0].y;
        int epy = points[points.length - 1].y;
        for (int i = 0; i < points.length - 1; i++) {
            long num1 = (points[i].y - spy) * (long) (prefxmax[i] - prefxmin[i]);
            long num2 = (epy - points[i + 1].y) * (long) (suffxmax[i + 1] - suffxmin[i + 1]);
            sum2 = Math.min(sum2, num1 + num2);
        }
        return Math.min(sum1, sum2);
    }
    static class sortByX implements Comparator<Point> {
        public int compare(Point p1, Point p2) {
            return (p1.x - p2.x);
        }
    }
    static class sortByY implements Comparator<Point> {
        public int compare(Point p1, Point p2) {
            return (p1.y - p2.y);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            Point[] points = new Point[n];
            for (int j = 0; j < n; j++) {
                String[] in = br.readLine().split("\\s");
                points[j] = new Point(Integer.parseInt(in[0]), Integer.parseInt(in[1]));
            }
            pw.println(minSum(points));
        }
        pw.flush();
    }
}