10369 - Arctic Network

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

Re: 10369 - Arctic Network

Post by empo » Sat Dec 06, 2008 10:05 pm

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...
"Accepted" is my passion but RTE is my weakness.....

boegel
New poster
Posts: 2
Joined: Wed Feb 09, 2011 10:56 am

Re: 10369 - Arctic Network

Post by boegel » Wed Feb 09, 2011 11:01 am

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 10369 - Arctic Network

Post by helloneo » Thu Feb 10, 2011 4:47 pm

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 :)

boegel
New poster
Posts: 2
Joined: Wed Feb 09, 2011 10:56 am

Re: 10369 - Arctic Network

Post by boegel » Thu Feb 10, 2011 7:06 pm

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.

puigy1
New poster
Posts: 2
Joined: Tue Jun 21, 2011 12:20 pm

Re: 10369 - Arctic Network

Post by puigy1 » Tue Jun 21, 2011 12:23 pm

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
New poster
Posts: 1
Joined: Fri Dec 30, 2011 4:32 pm

10369 - Arctic Network

Post by sanjid » Fri Dec 30, 2011 4:42 pm

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
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 10369 - Arctic Network

Post by Sabiha_Fancy » Sun Jan 27, 2013 1:31 pm

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);
}
Fancy

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10369 - Arctic Network

Post by brianfry713 » Tue Jan 29, 2013 12:55 am

Explain your algorithm or try solving it using Kruskal’s algorithm until you have P-S sets.
Check input and AC output for thousands of problems on uDebug!

Sabiha_Fancy
New poster
Posts: 24
Joined: Mon Jul 16, 2012 3:43 pm

Re: 10369 - Arctic Network

Post by Sabiha_Fancy » Tue Jan 29, 2013 11:18 am

I used prim's algorithm.
Fancy

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10369 - Arctic Network

Post by brianfry713 » Tue Jan 29, 2013 9:16 pm

try solving it using Kruskal’s algorithm until you have P-S sets.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10369 - Arctic Network

Post by Mukit Chowdhury » Thu Feb 07, 2013 12:26 pm

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
New poster
Posts: 7
Joined: Thu Sep 12, 2013 12:36 am

Getting Wrong answer on 10369 Arctic Networks.

Post by phantom11 » Thu Sep 12, 2013 11:47 pm

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.
Last edited by phantom11 on Wed Sep 18, 2013 12:24 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Getting Wrong answer on 10369 Arctic Networks.

Post by brianfry713 » Fri Sep 13, 2013 9:25 pm

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.
Check input and AC output for thousands of problems on uDebug!

phantom11
New poster
Posts: 7
Joined: Thu Sep 12, 2013 12:36 am

Re: Getting Wrong answer on 10369 Arctic Networks.

Post by phantom11 » Sat Sep 14, 2013 4:31 pm

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
Last edited by phantom11 on Wed Sep 18, 2013 12:24 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Getting Wrong answer on 10369 Arctic Networks.

Post by brianfry713 » Tue Sep 17, 2013 12:58 am

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
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 103 (10300-10399)”