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

Santiago Zanella
New poster
Posts: 10
Joined: Tue Oct 01, 2002 11:37 pm

10369 - Arctic Network

Post by Santiago Zanella » Thu Oct 24, 2002 5:46 am

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
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

Re: 10369 - Arctic Network

Post by uzioriluzan » Tue Nov 05, 2002 4:43 pm

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 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
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post by likhan » Tue Nov 05, 2002 8:34 pm

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
New poster
Posts: 10
Joined: Tue Oct 01, 2002 11:37 pm

Post by Santiago Zanella » Wed Nov 06, 2002 12:08 am

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Wed Nov 06, 2002 11:59 am

Kruskal's algorithm should work.

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

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post by likhan » Wed Nov 06, 2002 2:57 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, 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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Wed Nov 06, 2002 4:08 pm

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Wed Nov 06, 2002 4:24 pm

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
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post by likhan » Wed Nov 06, 2002 6:30 pm

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Wed Nov 06, 2002 8:15 pm

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Wed Nov 06, 2002 8:26 pm

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
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post by likhan » Wed Nov 06, 2002 10:03 pm

Hello,
I think I have gone mad that I can't solve this problem. :oops:
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
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

Post by uzioriluzan » Thu Nov 07, 2002 12:33 am

Exactly. Prim's MCST does not work. For those wanting to see a BS solution, look at Waterloo.
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.

Santiago Zanella
New poster
Posts: 10
Joined: Tue Oct 01, 2002 11:37 pm

Kruskal

Post by Santiago Zanella » Thu Nov 07, 2002 3:28 am

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.

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

The problem statement seemed confusing

Post by kmhasan » Thu Nov 07, 2002 4:54 am

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.

Post Reply

Return to “Volume 103 (10300-10399)”