10369 - Arctic Network

[empo]

Why i am getting RTE again and again?.......Someone Clarify...........

Code: Select all

"accepted"

actully i was using array of 600 edges while edges can be upto 500C2==125000...

[boegel]

Can someone who has solved this problem let me know what answer they get for the following input?

Code: Select all

1
4 23
2414 6028
1010 1508
4244 743
9021 2690
1265 5478
2918 5462
3574 8662
7098 5207
4110 2662
2624 748
651 5884
3873 6556
8707 397
7093 3177
5930 1904
2427 3786
5994 7001
1636 5094
7332 5012
6034 1258
2405 7364
8292 983
5241 7012

I'll keep the answer I'm getting to myself for now, but the reason I'm asking this is because I have two solutions by two different people which yield a different answer than my solution, and I don't understand why my answer would be incorrect...

[helloneo]

Can someone who has solved this problem let me know what answer they get for the following input?

Code: Select all

1
4 23
2414 6028
1010 1508
4244 743
9021 2690
1265 5478
2918 5462
3574 8662
7098 5207
4110 2662
2624 748
651 5884
3873 6556
8707 397
7093 3177
5930 1904
2427 3786
5994 7001
1636 5094
7332 5012
6034 1258
2405 7364
8292 983
5241 7012

My AC code returns..

Code: Select all

1862.61

Hope this help

[boegel]

My AC code returns..

Code: Select all

1862.61

Hope this help

Thanks a lot for your reply. I was getting 1923.67, and failed to see why that was wrong for quite a while.

In the end, I did figure out that you only need two satellites for the first edge, and that you only need one additional satellite for each other edge you want to get rid of...

K.

[puigy1]

I don't still understand the solution for the problem. Implementing a kruskal algorithm with P-S nodes would mean that satellite chanel's can communicate with any other channel with no cost, but the statement of the problem says that they can only communicate with no cost with other satellite channels. That's why I don't understand why could a kruskal algorithm with P-S can work for this problem.

Thank you

[sanjid]

please help.. i don't understand, why it is wa

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
long lin[100000],rank[1000000];
struct point
{
	double x;
	double y;
}p[10000];

struct T
{
	long u,v;
	double w;
}t[1000000];
int sf(const void *aa,const void *bb)
{
	T *p=(T *)aa;
	T *q=(T *)bb;
	if(p->w >q->w)
		return 1;
	return -1;
}
void make(long x)
{
	lin[x]=x;
	rank[x]=0;
}
long find(long z)
{
	if(z!=lin[z])
		lin[z]=find(lin[z]);
	return lin[z];
}
void link(long x,long y)
{
	if(rank[x]>rank[y])
		lin[y]=x;
	else
	{
		lin[x]=y;
		if(rank[x]==rank[y])
			rank[x]++;
	}
}
int main()
{
	long i,j,k,l,m,test,n,x,y;
	double f,sum;
	scanf("%ld",&test);
	while(test--)
	{
		scanf("%ld%ld",&m,&n);
		for(i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		l=0;
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
			{
				f=((p[i].x-p[j].x)*(p[i].x-p[j].x))+((p[i].y-p[j].y)*(p[i].y-p[j].y));
				f=sqrt(f);
				t[l].u=i;
				t[l].v=j;
				t[l].w=f;
				l++;
			}
		}
		qsort(t,l,sizeof(t[0]),sf);
		for(i=0;i<l;i++)
			make(i);
		sum=0;
		k=n;
	
		for(i=0;i<l;i++)
		{
			x=find(t[i].u);
			y=find(t[i].v);
			if(x!=y)
			{
				link(x,y);
				if(sum<t[i].w&&k>m)
				sum=t[i].w;
				k--;
			
			}
		}
		printf("%.2lf\n",sum+1e-9);
	}
	return 0;
}



				

[Sabiha_Fancy]

I am getting wrong answer for a long time. if any one help me to find out the problem.

Code: Select all

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

double distance(int x1,int y1,int x2,int y2);

struct node{
int x;
int y;
}V[510];

double w[510][510];
double dis[510],k[510];
int h[510],p[510];

int compare (const void * a, const void * b)
{
return ( *(double*)a - *(double*)b );
}

int main()
{
int N,S,P,i,j,u,d;
scanf("%d",&N);
while(N--)
{
scanf("%d %d",&S,&P);
for(i=1; i<=P; ++i)
{
scanf("%d %d",&V.x,&V.y);
}
for(i=1; i<=P; ++i)
{
for(j=1; j<=P; ++j)
w[j] = distance(V.x,V.y,V[j].x,V[j].y);
}
for(i=1; i<=P; ++i)
{
k = w[1];
h = 0;
p = 1;
}
h[1] = 1;
d = 0;
for(i=1; i<P; ++i)
{
u = -1;
for(j=1; j<=P; ++j)
{
if(!h[j])
{
if(u == -1 || k[j]<k)
u = j;
}
}
dis[d] = w[p];
d++;
h = 1;
for(j=1; j<=P; ++j)
{
if(!h[j])
{
if(k[j]>w[j])
{
k[j] = w[j];
p[j] = u;
}
}
}
}
qsort(dis,d,sizeof(double),compare);
printf("%.2lf\n",dis[d-S]);
}
return 0;
}

double distance(int x1,int y1,int x2,int y2)
{
int dis2;
double dis1;
dis2 = ((x2-x1)*(x2-x1)) + ((y2-y1)*(y2-y1));
dis1 = dis2*1.0;
return sqrt(dis1);
}

[brianfry713]

Explain your algorithm or try solving it using Kruskal’s algorithm until you have P-S sets.

[Sabiha_Fancy]

I used prim's algorithm.

[brianfry713]

try solving it using Kruskal’s algorithm until you have P-S sets.

[Mukit Chowdhury]

for input given above :

Code: Select all

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

output must be 1...

[phantom11]

I have tried this problem , but I dont know why is it wrong.
I have sorted the edges. Initially I have p forests and everytime I take an edge, i decrease the number of forest by 1. I do so till I have s forest left, after which I output the last seen edge's weight.

[brianfry713]

Post your full code. Don't store the node id's as a double and then cast them back to ints. Store them as ints instead.

[phantom11]

Thank you for the reply. I have changed the casting of ids from double by wrapping it in a class. Still I get the same wrong answer. Here is the full code.

Code: Select all

Removed after AC!! Thanks brianfry

[brianfry713]

Input:

Code: Select all

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

Output should be 1.00 not 1