10574 - Counting Rectangles

[bobi1978]

Hi.

Can someone give me any hint how to solve this problem without receiving TIME LIMIT EXCEEDED?

I tried to sort the points (C++ QUICK SORT), first by X and then by Y coordinate, and after that run 4 for loops with breaking conditions.
Is this slow?

[junjieliang]

That's definitely too slow. You're running a O(n^4) algorithm down here. That'll be 5000^4 = 625e12. Include another factor of 10 for the test cases and you have this super big number!

An idea that I have (which might not work) is to sort first, then use 2 for loops to run through every two points. These two points will be the opposite corners of the square (if they exist). Then search through a hash table to see if the other 2 points exist as well.

I'll try coding that when I'm free... busy with studies lately...
Good luck!

[jpfarias]

I think this is not the only thing to do, as you may have rectangles instead of squares....

So, my idea is:

Code: Select all

01. sort on X
02. for i = 1 to num_points - 3 do
03.    i1 = i + 1
04.    while X[i1] == X[i]  // Here we have one side of the rectangle
05.        i2 = i1 + 1
06.        while X[i2] == X[i] do
07.            i2 = i2 + 1
08.        while i2 < num_points - 1 do
09.            if Y[i2] == Y[i] // the third point was found
10.                if find point with x = X[i2] and y = Y[i1]
11.                    increase total

Of course this can be reduced. Once you got i and i1, search for i2 only on points with y == Y and x > X. Note that we must have Y != Y[i1]. The search for the final point can be done on points with x == X[i2].

This will require a sort on Y also, to help the search for i2.

I don't know if this is the best way to solve this one, but I think it should solve it. I'll try to implement it when I have some free time.

JP.

[BiK]

2junjieliang:

During the online contest we implemented this idea. However when we search for the other two points we used binary search. Our algorithm is (n^2*log(n)). It got TLE. Any idea how to improve the running time (except using a hash table) ?

[marian]

We have implemented O(N^2) algorithm during the contest (even if the complexity analysis is a bit tricky ). Idea is as follows: Sort the points by their x-coordinate. If the points have equal x-coordinate, sort them by y. So we have some sequences of points with x-coordinates x_1<x_2<...<x_k. For every i=1..k we compute, where in the array the points with given x-coodrinate x_i begin and end. Now we go through every pair of x-coordinates x_i, x_j, x_i<x_j and compute, how many rectangles there are with left edge on x_i and right edge on x_j. Since we have fixed x-coordinate, the only thing we can choose is y-coordinates of top and bottom edge. We have to have 2 points with the same y-coordinate and x-coordinates x_i and x_j and another 2 points with same y-coordinate. Since have sorted y-coordinates of points with x-coordinate x_i and x_j, we go through these 2 arrays (one for x_i and second for x_j) and find points with same y-corrdinate (something similiar to merge in merge-sort). (We are formally doing an intersection of a sets of y-coordinates of that points) We can compute this in time O(k+l) where k and l are lenghts of that array. So we know possible y-coordinates (let p be the number of that y-coordinates) for top and bottom edges, how many rectangles there are? Trivial combinatorics says, that here are exactly (p*(p-1))/2 rectangles.

To the complexity analysis: Initial sorting is O(N^2) (could be O(N log N), but who cares ). Every point is compared at most once with every other point. (when comparing y-coordinates) That gives us O(N^2).

[BiK]

Thanks a lot. That's the best explanation of an algorithm I've ever read in this forum. I think that there should be more posts like yours.

[rbuchan]

We never solved it during the online contest, but we used <map>. It was indexed on X, and the value at X was Y. So, we would go through each of the X's, and then try to follow a rectangle. If we couldn't do that, then there wasn't a rectangle. Didn't get it to work though.

[Cosmin.ro]

During the contest I've tougth of implementing marian's solution but I wasn't sure the solution wasn't too slow. I implemented first the n^2 log n solution wich got tle and then I tried marking the points on a matrix and do the n^2 solution. Because there are only 5000 points there are only 5000 different x coordinates and 5000 different y coordinates so we can normalize the coordinates so all the points have integer coordinates in [0,5000]X[0,5000]. So for the simple n^2 solution you need a 25Mb matrix and I thougth that uva allowed less so I switched my implementation to a bit matrix and I still got TLE ,for geting the bit in the matrix wich represented x,y I used some bit operations and I tried optimising this using precumputations and this got me accepted in 2.97 (the time limit in the contest was 3 s). After the contest I've heard that C++ and Pascal source code using 25 Mb got tle, maybe this is because working with more memory is slower.

[tep]

Because there are only 5000 points there are only 5000 different x coordinates and 5000 different y coordinates so we can normalize the coordinates so all the points have integer coordinates in [0,5000]X[0,5000].

Could you tell me how to normalize the coordinates so all the points have integer coordinates?

regards,
tep

[Larry]

Ya, I did the same thing during the contest, and couldn't get it AC, after the contest, I got it AC in about 4 seconds.. so..

To renormalize x-y, just sort by x, label distinct x-coordinates incrementally, then sort by y, and label distinct y-coordinates incrementally..

[tep]

I'm still confused... Then how do I search in O(1) if there is point (x,y)?
Are you using n^2 algorithm ?

[gawry]

Just make big table bool t[5000][5000] and set t[x][y] iff there is point with (normalized) coordinates (x,y).

[tep]

Umm.. sorry I still don't understand..

for example we have 3 point (x,y)
1e9 , 2e9
1e8 , 2e8
1e7 , 2e7

so, x[1] = 1e9, x[2] = 1e8, x[3] = 1e7
y[1] = 2e9, y[2] = 2e8, y[3] = 2e7

now if i want to search whether (1e8,2e6) exists?
then i search in x array 1e8? found in index 2
search in y array 2e6? not found, so the point doesn't exist.
if we can found both, then we check the big table?

Is it the way?

thanks..

[Larry]

No, basically, for me anyhow, you store x, y, rx, ry, where rx, ry are the renormalized x, y. After sorting your 3 points, you get:

1e9 , 2e9, 2, 2
1e8 , 2e8, 1, 1
1e7 , 2e7, 0, 0

(I actually don't store the rx, ry explicitly)

As mentioned above, you have a big 5000x5000 array, and you don't need the original numbers anymore.. a rectangle exist when there exists four corners, so for a O(n^2) algorithm, you basically have:

for each point a
for each point b
if a_x, b_y exists and if a_y, b_x exists
increment counter

And you can check if a renormalized point exists in O(1), by checking array.

My program doesn't run under 3 seconds though, so I'l be curious as to how to solve it in so much faster..

[tep]

Please help.. I don't know why I still got TLE..
I've used the method (normalizing) above..

thanx

[cpp]// Problem : Counting Rectangles
// UVA id : 10574
// Lang. : C++
// Author : Stephanus Indra
// Date : 29 December 2003

#include <iostream>
#include <cstdlib>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define MAX_N 5000

using namespace std;

class Point {
public:
int x,y;
int rx,ry;
};

Point point[MAX_N];
int p[MAX_N][157]; // 157 = 1 + N/BITSPERWORD
int npoint;

void set(int x,int y) { p[y][x >> SHIFT] |= (1 << (x & MASK)); }
void clr(int x,int y) { p[y][x >> SHIFT] &= ~(1 << (x & MASK)); }
int test(int x,int y) { return p[y][x >> SHIFT] & (1 << (x & MASK)); }

int pxcmp(const void *i,const void *j)
{
Point *a = (Point *)i;
Point *b = (Point *)j;

if (a->x == b->x)
return a->y - b->y;
else
return a->x - b->x;
}

int pycmp(const void *i,const void *j)
{
Point *a = (Point *)i;
Point *b = (Point *)j;

if (a->y == b->y)
return a->x - b->x;
else
return a->y - b->y;
}

int main()
{
int ncase,n;
int i,j,nrect;

cin >> ncase;
for (n=1; n<=ncase; n++)
{
// get input
cin >> npoint;
for (i=0; i<npoint; i++)
for (j=0; j<npoint; j++)
clr(i,j);
for (i=0; i<npoint; i++)
cin >> point.x >> point.y;

// sort,normalize - x
qsort(point,npoint,sizeof(Point),pxcmp);
point[0].rx = 0;
for (i=1; i<npoint; i++)
if (point.x != point[i-1].x)
point.rx = point[i-1].rx + 1;
else
point.rx = point[i-1].rx;

// sort,normalize - y
qsort(point,npoint,sizeof(Point),pycmp);
point[0].ry = 0;
for (i=1; i<npoint; i++)
if (point.y != point[i-1].y)
point.ry = point[i-1].ry + 1;
else
point.ry = point[i-1].ry;

// sign x-y
for (i=0; i<npoint; i++)
set(point.rx,point.ry);

// solve
nrect = 0;
for (i=0; i<npoint; i++)
for (j=i+1; j<npoint; j++)
if (point[i].ry < point[j].ry && point[i].rx < point[j].rx && test(point[i].rx,point[j].ry) && test(point[j].rx,point[i].ry))
nrect++;

// output
cout << "Case " << n << ": " << nrect << endl;
}

return 0;
}[/cpp]