Page 3 of 4

Re: 10369 - Arctic Network

Posted: Sat Dec 06, 2008 10:05 pm
by 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...

Re: 10369 - Arctic Network

Posted: Wed Feb 09, 2011 11:01 am
by 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...

Re: 10369 - Arctic Network

Posted: Thu Feb 10, 2011 4:47 pm
by helloneo
boegel wrote: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 :)

Re: 10369 - Arctic Network

Posted: Thu Feb 10, 2011 7:06 pm
by boegel
helloneo wrote:
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.

Re: 10369 - Arctic Network

Posted: Tue Jun 21, 2011 12:23 pm
by 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

10369 - Arctic Network

Posted: Fri Dec 30, 2011 4:42 pm
by 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;
}



				


Re: 10369 - Arctic Network

Posted: Sun Jan 27, 2013 1:31 pm
by Sabiha_Fancy
I am getting wrong answer for a long time. if any one help me to find out the problem.
#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);
}

Re: 10369 - Arctic Network

Posted: Tue Jan 29, 2013 12:55 am
by brianfry713
Explain your algorithm or try solving it using Kruskal’s algorithm until you have P-S sets.

Re: 10369 - Arctic Network

Posted: Tue Jan 29, 2013 11:18 am
by Sabiha_Fancy
I used prim's algorithm.

Re: 10369 - Arctic Network

Posted: Tue Jan 29, 2013 9:16 pm
by brianfry713
try solving it using Kruskal’s algorithm until you have P-S sets.

Re: 10369 - Arctic Network

Posted: Thu Feb 07, 2013 12:26 pm
by 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...

Getting Wrong answer on 10369 Arctic Networks.

Posted: Thu Sep 12, 2013 11:47 pm
by 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.

Re: Getting Wrong answer on 10369 Arctic Networks.

Posted: Fri Sep 13, 2013 9:25 pm
by 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.

Re: Getting Wrong answer on 10369 Arctic Networks.

Posted: Sat Sep 14, 2013 4:31 pm
by 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

Re: Getting Wrong answer on 10369 Arctic Networks.

Posted: Tue Sep 17, 2013 12:58 am
by 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