10369 - Arctic Network

[Santiago Zanella]

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 P-S 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?

[uzioriluzan]

The MCST does not solve this problem. It appears as if you did so.

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 P-S 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?

[likhan]

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

[Santiago Zanella]

As likhan asks, why searching the MST of the graph doesn't solve this problem?
Maybe we misunderstood the problem... Could you give me some reason because it won't work?

[gvcormac]

Kruskal's algorithm should work.

There is nothing tricky about the output format. Round to 2 decimal places.

[likhan]

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, N-1, 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 == N-1 )
puts("0.00");
else
printf("%.2f\n", t[i].cost);

}
}
[/cpp]

[gvcormac]

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.

[gvcormac]

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 union-find. (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.

[likhan]

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

[gvcormac]

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.

[gvcormac]

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)

[likhan]

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]

[uzioriluzan]

Exactly. Prim's MCST does not work. For those wanting to see a BS solution, look at Waterloo.
Regards...

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.

[Santiago Zanella]

I rewrote my implementation of the Union-Find data structure used by Kruskal Algorithm and I finally got Accepted. I was using a quite quick implementation with path-compression 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.

[kmhasan]

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:

Any two outposts with a satellite channel can communicate via the satellite, regardless of their location

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.

Hope it helps.