OJ Board

Posted: **Mon Dec 29, 2003 2:20 pm**

Without testing it, I would have to say

     for (i=0; i<npoint; i++) 
         for (j=0; j<npoint; j++) 
            clr(i,j);

Gets very expensive, as you're doing too many shift operations when n = 5000...

Posted: **Thu Jan 01, 2004 10:47 am**

Thanks. Finally got AC.

Posted: **Mon Mar 29, 2004 2:31 pm**

I dunno why i've got wa.

If the number of different x is smaller than the number of different y, I will turn the plane. Maybe it can make the program more efficient.
[pascal]
Program Counting_Rectangles;

Const
Maxn=5000;

Type
TPoint=Record
x,y:Longint;
End;
TLink=^TNode;
TNode=Record
data:Longint;
next:TLink;
End;

Var
p:Array [1..Maxn] of TPoint;
a:Array [1..Maxn] of TLink;
NumOfTestcases,Testcase,n,m,ans:Longint;

Procedure Input_Data;
Var
i:Longint;
Begin
Read(n);
For i:=1 to n Do Read(p.x,p.y);
End;

Procedure Qsort(h,t:Longint);
Var
r,i,j:Longint;
k:TPoint;
Begin
r:=Random(t-h+1)+h;
k:=p[r];
p[r]:=p[h];
i:=h; j:=t;
While i<j Do
Begin
While (i<j) and ((k.y<p[j].y) or (k.y=p[j].y) and (k.x>=p[j].x)) Do Dec(j);
p:=p[j];
While (i<j) and ((p.y<k.y) or (p.y=k.y) and (p.x>=k.x)) Do Inc(i);
p[j]:=p;
End;
p:=k;
If h<i-1 Then Qsort(h,i-1);
If i+1<t Then Qsort(i+1,t);
End;

Function Stat:Longint;
Var
i,j,ans:Longint;
Begin
ans:=0;
i:=1;
While i<=n Do
Begin
Inc(ans);
j:=i+1;
While (j<=n) and (p[j].y=p.y) Do Inc(j);
i:=j;
End;
Stat:=ans;
End;

Procedure Swap(Var a,b:Longint);
Var
temp:Longint;
Begin
temp:=a; a:=b; b:=temp;
End;

Procedure Insert(x,y:Longint);
Var
d:TLink;
Begin
New(d); d^.data:=y;
d^.next:=a[x]; a[x]:=d;
End;

Procedure Init;
Var
numy,i,j:Longint;
Begin
Qsort(1,n); numy:=Stat;
For i:=1 to n-1 Do
If (p.x=p[i+1].x) and (p[i].y=p[i+1].y) Then While True Do;
For i:=1 to n Do Swap(p[i].x,p[i].y);
Qsort(1,n); If Stat>numy Then For i:=1 to n Do Swap(p[i].x,p[i].y);
Fillchar(a,Sizeof(a),0);
m:=0;
i:=1;
While i<=n Do
Begin
Inc(m); Insert(m,p[i].x);
j:=i+1;
While (j<=n) and (p[j].y=p[i].y) Do
Begin
Insert(m,p[j].x);
Inc(j);
End;
i:=j;
End;
End;

Procedure Solve;
Var
i,j,tot:Longint;
x,y:TLink;
Begin
ans:=0;
For i:=1 to m-1 Do
For j:=i+1 to m Do
Begin
tot:=0;
x:=a[i]; y:=a[j];
While (x<>Nil) and (y<>Nil) Do
Begin
If x^.data=y^.data Then Inc(tot);
If x^.data<=y^.data Then x:=x^.next Else y:=y^.next;
End;
Inc(ans,tot*(tot-1) div 2);
End;
End;

Procedure Output_Data;
Begin
Writeln('Case ',Testcase,': ',ans);
End;

Procedure Release(p:TLink);
Begin
If p<>Nil Then
Begin
Release(p^.next);
Dispose(p);
End;
End;

Procedure Set_Free;
Var
i:Longint;
Begin
For i:=1 to m Do Release(a[i]);
End;

Begin
Assign(Input,'10574.in');
Assign(Output,'10574.out');
Reset(Input);
Rewrite(Output);

Read(NumOfTestcases);
For Testcase:=1 to NumOfTestcases Do
Begin
Input_Data;
Init;
Solve;
Output_Data;
Set_Free;
End;

Close(Output);
Close(Input);
End.
[/pascal]

Posted: **Sat Apr 03, 2004 5:46 pm**

nice trick... worked out for me.... although it was AC in +-7.715 secs...

I have seen similar problems on other tests (as the south american contest 2003).... therefore i am posting this question

I am using a:
typedef struct point {
long x,y;
};

And C++ vector/sort in order to have the algorithm complete.... I cache objects in order to create at most 5000 points summing up all tests.

Would it be faster to use simple ints?

Do people who achieve it under 1 sec use this algo?

Thanks

Guilherme

Posted: **Mon Jan 17, 2005 3:16 pm**

I think I am using n^2 algo, but getting TLE.

This is the n^2 part of my code..

Code: Select all

for(i=0;i<n;i++)
  for(j=i+1;j<n;j++) {
     if( V[i].x >= V[j].x || V[i].y >=V[j].y) continue;
     if( A[V[i].x][V[j].y] && A[V[i].y][V[j].x] )  
        ans++;
}

here A[j] indicates whether point (i, j) is valid after normalization.

The rest of my code is either nlogn or n.

Is it too costly.

Posted: **Tue May 16, 2006 10:07 am**

I am also getting TLE, but my code runs in about 1.36 seconds for ten test cases where n = 5000 on my laptop.
There are at most ten test cases, and at most 5000 points ( I've checked this ), so it should be ACC on the judge.
I don't believe my laptop is 10 times faster than the judge server

Here is my code, if someone can see the reason why I keep on getting TLE:

Code: Select all

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int MAXN = 5000;

struct pt {
  int x, y;
  pt( int nx = 0, int ny = 0 ) : x( nx ), y( ny ) {}
  friend bool operator<( const pt& A, const pt& B ) {
    if ( A.x != B.x ) return ( A.x < B.x );
    return ( A.y < B.y );
  }
};

char ima[MAXN][MAXN];
char cookie = 0;

int main()
{
  int t; scanf( "%d", &t );
  for( int t_case = 0; t_case < t; ++t_case ) {
    int n; scanf( "%d", &n );
    vector< pt > P( n );
    map< int, int > X, Y; 
    for( int i = 0; i < n; ++i ) {
      scanf( "%d%d", &P[i].x, &P[i].y );
      X[P[i].x] = 3;
      Y[P[i].y] = 4;
    }
    
    {
      int i = 0;
      for( map< int, int >::iterator it = X.begin(); it != X.end(); ++it, ++i )
	it->second = i;
    }

    {
      int i = 0;
      for( map< int, int >::iterator it = Y.begin(); it != Y.end(); ++it, ++i )
	it->second = i;
    }

    ++cookie;
    for( int i = 0; i < n; ++i ) {
      P[i].x = X[P[i].x];
      P[i].y = Y[P[i].y];
      ima[P[i].x][P[i].y] = cookie;
    }

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

    int cnt = 0;
    for( short i = 0; i < n; ++i )
      for( short j = i + 1; j < n; ++j ) 
	cnt += ( P[i].x < P[j].x && P[i].y < P[j].y && ima[P[i].x][P[j].y] == cookie && ima[P[j].x][P[i].y] == cookie );
      
    printf( "Case %d: %d\n", t_case + 1, cnt );
  }
  return 0;
}

Posted: **Tue May 16, 2006 10:26 am**

If you want to know how fast your machine is compared to the judge's host, you can use this function on your computer:

Code: Select all

void wait(int n){
   int i,j,k;
   int dummy=0;
   
   for(i=0;i<n;i++){
      for(j=0;j<10000;j++){
         for(k=0;k<1435;k++){
            dummy++;
            }
         }
      }
   }

Calling wait(n) will waste approx. 0.1*n seconds on the judge, so if wait(100) takes 1 second on your machine, that means it is 10 times faster than the judge.

Posted: **Tue May 16, 2006 7:13 pm**

Does the judge use -O2 option when compiling c++ code?
My code runs signifantly slower when compiled without -O2

Posted: **Tue May 16, 2006 7:29 pm**

No, it doesn't. Should have mentioned that, I guess...

OJ Board

10574 - Counting Rectangles

I use Marian's method, but got WA. I don't know why

tle..