10369  Arctic Network
Moderator: Board moderators

 New poster
 Posts: 10
 Joined: Tue Oct 01, 2002 11:37 pm
10369  Arctic Network
I first compute the distance and add a corresponding edge between each pair of outposts. That is, I construct an undirected graph where edge weights are those distances.
Then I apply Kruskal algorithm until PS edges are added and print the weight of the last edge added.
With this approach I get WA.
As the statement is not very specific about the output, I tried rounding and truncating the result and either way I get WA. I tried also using double or single floating point preccission...
There must be something I'm missing, but what is it?
Then I apply Kruskal algorithm until PS edges are added and print the weight of the last edge added.
With this approach I get WA.
As the statement is not very specific about the output, I tried rounding and truncating the result and either way I get WA. I tried also using double or single floating point preccission...
There must be something I'm missing, but what is it?

 New poster
 Posts: 27
 Joined: Thu Feb 14, 2002 2:00 am
Re: 10369  Arctic Network
The MCST does not solve this problem. It appears as if you did so.
Santiago Zanella wrote:I first compute the distance and add a corresponding edge between each pair of outposts. That is, I construct an undirected graph where edge weights are those distances.
Then I apply Kruskal algorithm until PS edges are added and print the weight of the last edge added.
With this approach I get WA.
As the statement is not very specific about the output, I tried rounding and truncating the result and either way I get WA. I tried also using double or single floating point preccission...
There must be something I'm missing, but what is it?
Why is MCST not going to solve this problem?
I'm also getting WA i did MCST on the generated graph by calculating the straight line distance between all the points and then sorted the edges in the MCST descending and started positioning satellites on the edges whenever i found a edge could not be covered I outputted the edge cost if all the edges were covered then i said 0.00
I'm also getting WA i did MCST on the generated graph by calculating the straight line distance between all the points and then sorted the edges in the MCST descending and started positioning satellites on the edges whenever i found a edge could not be covered I outputted the edge cost if all the edges were covered then i said 0.00

 New poster
 Posts: 10
 Joined: Tue Oct 01, 2002 11:37 pm
I did this. Could any one plz see and tell what i'm doing wrong. The explanation is posted on my previous post. See top.
Thanx
[cpp]
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXV 510
#define MAXVAL 200000000L
long S, N;
struct City
{
float x, y;
}b[MAXV];
struct tree
{
long u, v;
double cost;
} t[MAXV];
float cost[MAXV][MAXV], gmin;
long nea[MAXV], I, J;
int sfunc( const void *in1, const void *in2 )
{
tree a = *(tree *)in1;
tree b = *(tree *)in2;
if ( a.cost < b.cost )
return +1;
if ( a.cost > b.cost )
return 1;
return 0;
}
void Prims(void)
{
float mincost = 0, min;
long i, j, in, k;
mincost = gmin;
t[1].u = I;
t[1].v = J;
t[1].cost = cost[J];
nea = nea[J] = 0;
for(i = 1; i <= N; i++)
if(nea != 0)
{
if(cost > cost[J])
nea = J;
else nea = I;
}
for ( j = 2; j <= N  1; j++ )
{
min = MAXVAL;
in = 0;
for(i = 1; i <= N; i++)
{
if(nea != 0 && min > cost[nea[i]])
{
min = cost[i][nea[i]];
in = i;
}
}
if( in==0  fabs(MAXVAL  min) < 0.001) break;
t[j].u = in;
t[j].v = nea[in];
t[j].cost = cost[in][nea[in]];
mincost += cost[in][nea[in]];
nea[in] = 0;
for(k = 1; k <= N; k++)
if( nea[k] != 0 && cost[k][nea[k]] > cost[k][in])
nea[k] = in;
}
}
void main(void)
{
long i, j, kase, x, y, c;
double temp;
scanf("%ld", &kase);
while( kase )
{
scanf("%ld %ld",&S,&N);
for(i = 1; i <= N; i++)
{
scanf("%ld%ld", &x, &y);
b[i].x = (double)x;
b[i].y = (double)y;
nea[i] = i;
}
gmin = MAXVAL;
for(i = 1; i <= N; i++)
{
cost[i][i] = MAXVAL;
for(j = i+1; j <= N; j++)
{
temp = (b[i].x  b[j].x) * (b[i].x  b[j].x) + (b[i].y  b[j].y)*(b[i].y  b[j].y);
temp = sqrt(temp);
cost[i][j] = cost[j][i] = temp;
if(nea[i]!=0 && nea[j]!= 0 && gmin > cost[i][j])
{
gmin = cost[i][j];
I = i;
J = j;
}
}
}
Prims();
char selected[MAXV];
memset( selected, 0, sizeof(selected) );
qsort( t+1, N1, sizeof(t[0]), sfunc );
i = 1;
while ( S )
{
if ( !selected[t[i].u] && S > 0 )
{
selected[t[i].u] = 1;
S;
}
else
break;
if ( !selected[t[i].v] && S > 0 )
{
selected[t[i].v] = 1;
S;
}
else
break;
i++;
}
if ( i == N1 )
puts("0.00");
else
printf("%.2f\n", t[i].cost);
}
}
[/cpp]
Thanx
[cpp]
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXV 510
#define MAXVAL 200000000L
long S, N;
struct City
{
float x, y;
}b[MAXV];
struct tree
{
long u, v;
double cost;
} t[MAXV];
float cost[MAXV][MAXV], gmin;
long nea[MAXV], I, J;
int sfunc( const void *in1, const void *in2 )
{
tree a = *(tree *)in1;
tree b = *(tree *)in2;
if ( a.cost < b.cost )
return +1;
if ( a.cost > b.cost )
return 1;
return 0;
}
void Prims(void)
{
float mincost = 0, min;
long i, j, in, k;
mincost = gmin;
t[1].u = I;
t[1].v = J;
t[1].cost = cost[J];
nea = nea[J] = 0;
for(i = 1; i <= N; i++)
if(nea != 0)
{
if(cost > cost[J])
nea = J;
else nea = I;
}
for ( j = 2; j <= N  1; j++ )
{
min = MAXVAL;
in = 0;
for(i = 1; i <= N; i++)
{
if(nea != 0 && min > cost[nea[i]])
{
min = cost[i][nea[i]];
in = i;
}
}
if( in==0  fabs(MAXVAL  min) < 0.001) break;
t[j].u = in;
t[j].v = nea[in];
t[j].cost = cost[in][nea[in]];
mincost += cost[in][nea[in]];
nea[in] = 0;
for(k = 1; k <= N; k++)
if( nea[k] != 0 && cost[k][nea[k]] > cost[k][in])
nea[k] = in;
}
}
void main(void)
{
long i, j, kase, x, y, c;
double temp;
scanf("%ld", &kase);
while( kase )
{
scanf("%ld %ld",&S,&N);
for(i = 1; i <= N; i++)
{
scanf("%ld%ld", &x, &y);
b[i].x = (double)x;
b[i].y = (double)y;
nea[i] = i;
}
gmin = MAXVAL;
for(i = 1; i <= N; i++)
{
cost[i][i] = MAXVAL;
for(j = i+1; j <= N; j++)
{
temp = (b[i].x  b[j].x) * (b[i].x  b[j].x) + (b[i].y  b[j].y)*(b[i].y  b[j].y);
temp = sqrt(temp);
cost[i][j] = cost[j][i] = temp;
if(nea[i]!=0 && nea[j]!= 0 && gmin > cost[i][j])
{
gmin = cost[i][j];
I = i;
J = j;
}
}
}
Prims();
char selected[MAXV];
memset( selected, 0, sizeof(selected) );
qsort( t+1, N1, sizeof(t[0]), sfunc );
i = 1;
while ( S )
{
if ( !selected[t[i].u] && S > 0 )
{
selected[t[i].u] = 1;
S;
}
else
break;
if ( !selected[t[i].v] && S > 0 )
{
selected[t[i].v] = 1;
S;
}
else
break;
i++;
}
if ( i == N1 )
puts("0.00");
else
printf("%.2f\n", t[i].cost);
}
}
[/cpp]
It looks to me like you are using Prim's algorithm not Kruskal's.
Prim's starts at a designed connected component and repeatedly adds the shortest edge connecting this component to some other component. Kruskal's examines the edges in order and adds the shortest edge that connects any two distinct components.
Also, your check for 0.00 is unecessary and wrong. Perhaps you have interpreted the definition of "satellite channel" differently from the intent of the question.
Prim's starts at a designed connected component and repeatedly adds the shortest edge connecting this component to some other component. Kruskal's examines the edges in order and adds the shortest edge that connects any two distinct components.
Also, your check for 0.00 is unecessary and wrong. Perhaps you have interpreted the definition of "satellite channel" differently from the intent of the question.
On a second look, I can't convince myself that the code labelled "Prim" implements either Prim's or Kruskal's algorithm. To implement Prim
you have to select only edges where one vertex has been visited and
one hasn't. To implement Kruskal you need unionfind. (And Prim
won't work for this problem, which is not to find a spanning tree but to find a forest of S spanning trees.
By the way, there's a totally different way of solving the problem.
you have to select only edges where one vertex has been visited and
one hasn't. To implement Kruskal you need unionfind. (And Prim
won't work for this problem, which is not to find a spanning tree but to find a forest of S spanning trees.
By the way, there's a totally different way of solving the problem.
Hello,
Thanx gvcormac for your patience to see the code. In the above code I found some mistakes and corrected it. The bottom portion I think should be like this.
[cpp]
i = 1;
while ( S && i < N )
{
if ( !selected[t.u] && S > 0 )
{
selected[t.u] = 1;
S;
}
else
break;
if ( !selected[t.v] && S > 0 )
{
selected[t.v] = 1;
S;
}
else
break;
i++;
}
if ( i == N )
puts("0.00");
else
printf("%.2lf\n", t.cost);
[/cpp]
Thanx again. And gvcormac I still don't understand why Prims will have some problems. Could u describe it in detail? And plz also describe the other way to solve it.
Thanx
Thanx gvcormac for your patience to see the code. In the above code I found some mistakes and corrected it. The bottom portion I think should be like this.
[cpp]
i = 1;
while ( S && i < N )
{
if ( !selected[t.u] && S > 0 )
{
selected[t.u] = 1;
S;
}
else
break;
if ( !selected[t.v] && S > 0 )
{
selected[t.v] = 1;
S;
}
else
break;
i++;
}
if ( i == N )
puts("0.00");
else
printf("%.2lf\n", t.cost);
[/cpp]
Thanx again. And gvcormac I still don't understand why Prims will have some problems. Could u describe it in detail? And plz also describe the other way to solve it.
Thanx
Here's a counterexample to Prim.
1
3 6
0 1
0 2
0 4
0 5
0 7
0 8
The output should be 1, but Prim will give 2.
Let's say you start with 0,1. You will connect it to 0,2. Then the closest point is 0,4 which is distance 2. Wrong. And just as wrong no matter which point you start at.
On the other hand if you use Kruskal you will connect 0,1 and 0,2 then 0,4 and 0.5 then
0,7 and 0.8. Max distance 1. Right.
The other approach involves a binary search. Consider the function C(D) to be
the number of connected components iif the transmitter distance is D. Solve for the
minimum D such that C(D) = S.
1
3 6
0 1
0 2
0 4
0 5
0 7
0 8
The output should be 1, but Prim will give 2.
Let's say you start with 0,1. You will connect it to 0,2. Then the closest point is 0,4 which is distance 2. Wrong. And just as wrong no matter which point you start at.
On the other hand if you use Kruskal you will connect 0,1 and 0,2 then 0,4 and 0.5 then
0,7 and 0.8. Max distance 1. Right.
The other approach involves a binary search. Consider the function C(D) to be
the number of connected components iif the transmitter distance is D. Solve for the
minimum D such that C(D) = S.
Your code still looks wrong to me. Are you trying to implement Prim or Kruskal?
Prim looks like this:
connected_set = {some arbitrary vertex in the graph}
while connected_set != V do
find v elt. connected_set and w notelt. connected_set such that
dist(v,w) is minimized
add w to connected_set
done
Kruskal like this:
components = { {v}  v elt. V }
while components > 1 do
find v elt Q and w elt R such that
Q != R and Q elt. components and R elt. components
and dist(v,w) is minimized
components = components  Q  R + union(Q,R)
Prim looks like this:
connected_set = {some arbitrary vertex in the graph}
while connected_set != V do
find v elt. connected_set and w notelt. connected_set such that
dist(v,w) is minimized
add w to connected_set
done
Kruskal like this:
components = { {v}  v elt. V }
while components > 1 do
find v elt Q and w elt R such that
Q != R and Q elt. components and R elt. components
and dist(v,w) is minimized
components = components  Q  R + union(Q,R)
Hello,
I think I have gone mad that I can't solve this problem.
I even tried with kruskal.
The code goes like this.
[cpp]
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXE 510
#define MAXV 125000
#define sqr(a) ((a)*(a))
struct Point
{
long x, y;
} p[MAXV];
struct Edge
{
long u, v;
double cost;
} edge[MAXE], tree[MAXV];
long n, s, nele;
long pred[MAXV];
int sfuncasc( const void *in1, const void *in2 )
{
Edge a = *(Edge *)in1;
Edge b = *(Edge *)in2;
if ( a.cost < b.cost )
return 1;
if ( a.cost > b.cost )
return +1;
return 0;
}
int sfuncdesc( const void *in1, const void *in2 )
{
Edge a = *(Edge *)in1;
Edge b = *(Edge *)in2;
if ( a.cost < b.cost )
return +1;
if ( a.cost > b.cost )
return 1;
return 0;
}
double dist( double x1, double y1, double x2, double y2 )
{
return ( sqrt(sqr((x1  x2)) + sqr((y1  y2))) );
}
long root( long idx )
{
while ( idx != pred[idx] )
idx = pred[idx];
return idx;
}
void combine( long u, long v )
{
pred[root(u)] = v;
}
void main()
{
Edge nedge;
long i, j, k, kase;
scanf("%ld", &kase);
while ( kase )
{
scanf("%ld %ld", &s, &n);
for ( i = 0; i < n; i++ )
{
scanf("%ld %ld", &p.x, &p.y);
pred = i;
}
if ( s == n )
{
puts("0.00");
continue;
}
nele = 0;
for ( i = 0; i < n; i++ )
for ( j = (i + 1); j < n; j++ )
{
nedge.u = i;
nedge.v = j;
nedge.cost = dist( p.x, p.y, p[j].x, p[j].y );
edge[nele++] = nedge;
}
qsort( edge, nele, sizeof(edge[0]), sfuncasc );
j = 0;
for ( i = 1; i < n; i++ )
{
for ( ; j < nele; j++ )
{
nedge = edge[j];
if ( root(nedge.u) != root(nedge.v) )
{
combine( nedge.u, nedge.v );
j++;
break;
}
}
tree = nedge;
}
memset( pred, 0, sizeof(pred) );
qsort( tree, n  1, sizeof(tree[0]), sfuncdesc );
i = 0;
while ( i < (n  1) && s > 0 )
{
if ( pred[tree.u] == 0 )
{
if ( s > 0 )
{
pred[tree.u] = 1;
s;
}
else
break;
}
if ( pred[tree.v] == 0 )
{
if ( s > 0 )
{
pred[tree.v] = 1;
s;
}
else
break;
}
i++;
}
if ( i == (n  1) )
puts("0.00");
else
{
while ( pred[tree[i].u] && pred[tree[i].v] ) i++;
if ( i == (n  1) )
puts("0.00");
else
printf("%.2lf\n", tree[i].cost);
}
}
}
[/cpp]
I think I have gone mad that I can't solve this problem.
I even tried with kruskal.
The code goes like this.
[cpp]
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXE 510
#define MAXV 125000
#define sqr(a) ((a)*(a))
struct Point
{
long x, y;
} p[MAXV];
struct Edge
{
long u, v;
double cost;
} edge[MAXE], tree[MAXV];
long n, s, nele;
long pred[MAXV];
int sfuncasc( const void *in1, const void *in2 )
{
Edge a = *(Edge *)in1;
Edge b = *(Edge *)in2;
if ( a.cost < b.cost )
return 1;
if ( a.cost > b.cost )
return +1;
return 0;
}
int sfuncdesc( const void *in1, const void *in2 )
{
Edge a = *(Edge *)in1;
Edge b = *(Edge *)in2;
if ( a.cost < b.cost )
return +1;
if ( a.cost > b.cost )
return 1;
return 0;
}
double dist( double x1, double y1, double x2, double y2 )
{
return ( sqrt(sqr((x1  x2)) + sqr((y1  y2))) );
}
long root( long idx )
{
while ( idx != pred[idx] )
idx = pred[idx];
return idx;
}
void combine( long u, long v )
{
pred[root(u)] = v;
}
void main()
{
Edge nedge;
long i, j, k, kase;
scanf("%ld", &kase);
while ( kase )
{
scanf("%ld %ld", &s, &n);
for ( i = 0; i < n; i++ )
{
scanf("%ld %ld", &p.x, &p.y);
pred = i;
}
if ( s == n )
{
puts("0.00");
continue;
}
nele = 0;
for ( i = 0; i < n; i++ )
for ( j = (i + 1); j < n; j++ )
{
nedge.u = i;
nedge.v = j;
nedge.cost = dist( p.x, p.y, p[j].x, p[j].y );
edge[nele++] = nedge;
}
qsort( edge, nele, sizeof(edge[0]), sfuncasc );
j = 0;
for ( i = 1; i < n; i++ )
{
for ( ; j < nele; j++ )
{
nedge = edge[j];
if ( root(nedge.u) != root(nedge.v) )
{
combine( nedge.u, nedge.v );
j++;
break;
}
}
tree = nedge;
}
memset( pred, 0, sizeof(pred) );
qsort( tree, n  1, sizeof(tree[0]), sfuncdesc );
i = 0;
while ( i < (n  1) && s > 0 )
{
if ( pred[tree.u] == 0 )
{
if ( s > 0 )
{
pred[tree.u] = 1;
s;
}
else
break;
}
if ( pred[tree.v] == 0 )
{
if ( s > 0 )
{
pred[tree.v] = 1;
s;
}
else
break;
}
i++;
}
if ( i == (n  1) )
puts("0.00");
else
{
while ( pred[tree[i].u] && pred[tree[i].v] ) i++;
if ( i == (n  1) )
puts("0.00");
else
printf("%.2lf\n", tree[i].cost);
}
}
}
[/cpp]

 New poster
 Posts: 27
 Joined: Thu Feb 14, 2002 2:00 am
Exactly. Prim's MCST does not work. For those wanting to see a BS solution, look at Waterloo.
Regards...
Regards...
gvcormac wrote:Here's a counterexample to Prim.
1
3 6
0 1
0 2
0 4
0 5
0 7
0 8
The output should be 1, but Prim will give 2.
Let's say you start with 0,1. You will connect it to 0,2. Then the closest point is 0,4 which is distance 2. Wrong. And just as wrong no matter which point you start at.
On the other hand if you use Kruskal you will connect 0,1 and 0,2 then 0,4 and 0.5 then
0,7 and 0.8. Max distance 1. Right.
The other approach involves a binary search. Consider the function C(D) to be
the number of connected components iif the transmitter distance is D. Solve for the
minimum D such that C(D) = S.

 New poster
 Posts: 10
 Joined: Tue Oct 01, 2002 11:37 pm
Kruskal
I rewrote my implementation of the UnionFind data structure used by Kruskal Algorithm and I finally got Accepted. I was using a quite quick implementation with pathcompression an union by rank, but although I remember testing it throughly it was somewhat faulty.
As you say, there is absolutely no trick in this problem, it's a plain application of Kruskal Algorithm. Maybe it could be solved using binary search and improve speed, but the time limit is not a problem here.
As you say, there is absolutely no trick in this problem, it's a plain application of Kruskal Algorithm. Maybe it could be solved using binary search and improve speed, but the time limit is not a problem here.
The problem statement seemed confusing
Hi,
I've had a hard time solving this problem. I couldn't actually relate the sample input to the sample output. Finally got AC using Kruskal, though. The part I got confused with was:
Hope it helps.
I've had a hard time solving this problem. I couldn't actually relate the sample input to the sample output. Finally got AC using Kruskal, though. The part I got confused with was:
I thought satellite channel==an edge. But as it finally turns out, satellite channels belongs to outposts, so they are analogous to vertices. Thus it simply reduces to finding the "Minimum Cost Spanning Forest" in the graph that has S components left. The representatives of these S components can then have the S satellite channels.Any two outposts with a satellite channel can communicate via the satellite, regardless of their location
Hope it helps.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/