## 10369 - Arctic Network

Moderator: Board moderators

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

### Re: 10369 - Arctic Network

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

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

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

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

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

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];
}
{
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)
{
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

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

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

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

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: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 10369 - Arctic Network

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.

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 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.

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.

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!