Quote:
Code chef problem solved but need to optimise due to TLE .
As usual, CodeChef challenges are challenges, this means that straightforward programs are never the solution.
If N is 200000 rectangles, there is 799999 points.
Your code is matching points as 79.9999*79.9999=639.998.400.001 checks for x and as much for y.
Your code is in O(n²).
The key is in
Data Structures and
Algorithms. Some data structures and algorithms allow to get faster, but learning them is a learning of a life, there is always something interesting to learn.
Example of simple optimization, but I fear is not enough :
Dividing the search by 4: for any x[j] matched with an x[i], swap (x[j+1], x[i]) and don't search x[j+1]. The swap makes that any previous x[j] is matched with x[j+1], so there is no need to search x[j+1], divide by 2. This imply that for any x[j], there is no search to do on any x[i] for 0 <= i <= j, divide by 2 again.
-----
Advice: Learn to indent properly your code, it show its structure and it helps reading and understanding. It also helps spotting structures mistakes.
#include <iostream>
using namespace std;
void quicksort(long int number[],long int n)
{
int i,j,a;
for (i = 0; i < n; ++i)
{
for (j = i + 1; j < n; ++j)
{
if (number[i] > number[j])
{
a = number[i];
number[i] = number[j];
number[j] = a;
}
}
}
}
int main(void) {
long int n,i,j,k,rx,ry;
cin>>n;
for(i=0;i<n;i++)
{
cin>>k;
long int x[4*k-1],y[4*k-1];
for(j=0;j<4*k-1;j++)
{
cin>>x[j]>>y[j];
}
quicksort(x,4*k-1);
quicksort(y,4*k-1);
int flagx=0,flagy=0;
for(j=0;j<4*k-1;j=j+2)
{
if(!flagx||!flagy)
{
if(!flagx)
{
if(x[j]!=x[j+1])
{
rx=x[j];
flagx=1;
}
}
if(!flagy)
{
if(y[j]!=y[j+1])
{
ry=y[j];
flagy=1;
}
}
}
else
{
break;
}
}
cout<<rx<<" "<<ry<<endl;
}
return 0;
}
Indentation style - Wikipedia[
^]
Professional programmer's editors have this feature and others ones such as parenthesis matching and syntax highlighting.
Notepad++ Home[
^]
ultraedit[
^]
-----
[Update]
I fear your quicksort routine is not a quicksort algorithm, it is more a bubble sort.
Your first code was O(n²)
Your new code is O(N²/2)
The changes I proposed are O(N²/4)
Using a balanced binary tree can lead to something like O(N*log(N))
Self-balancing binary search tree - Wikipedia[
^]
Red–black tree - Wikipedia[
^]