## 10369 - Arctic Network

Moderator: Board moderators

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions
Hello
1
3 6
0 1
0 2
0 4
0 5
0 7
0 8
This input should give 2.0 as we have 3 satellites so if we number the vertices
[0,1] = 1
[0,2] = 2
[0,4] = 3
[0,5] = 4
[0,7] = 5
[0,8] = 6
Kruskal will make a tree
[1->2](1.0),[3->4](1.0),[5->6](1.0),[2->3](2.0),[4->5](2.0)
If we use three satellites only one of two edges with cost 2.0 can be covered so the answer is three.

Will any one tell me if i'm wrong or not. if yes then how?

Thanx

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
I think you are wrong.
Kruskal will make a tree
[1->2](1.0),[3->4](1.0),[5->6](1.0),[2->3](2.0),[4->5](2.0)
is correct. However, notice that when you have three components with 1->2, 3->4 and 5->6 you can place the three satellites on 1, 3 and 5. Thus, the whole graph will be connected, and the highest cost that you had to pay for an edge was [5->6](1.0).

Therefore, the answer is 1.00 not 3.00

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions
Thanx Tomal for ur time. But how do i do it?

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:

### using kruskal's algorithm

If you implement Kruskal's algorithm, it's pretty easy. I haven't implemented Prim's one anywhere, so I'm not sure if it'd work here. Since, some previous posts said that it won't I blindly go with them.

Now with Kruskal's you know when you start your MSCT building you have K=N components left (all the N vertices are disjoint). Every time you add an edge, one component is reduced (K--). You have to do this while you have S components left (K>S). And you've to keep the cost of the last used edge, as the edges are sorted by non decreasing cost. The final output will be the last used edge.

I've implemented the pseudocode given in Introduction to Algorithm book. Only two additional lines were needed to my original implementation of Kruskal's.

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
If you have a minute free time, can you tell me what's wrong with this code? It's exactly the same as you guys were talking about and for me it works perfectly, but I get WA. Can you help me?
thanks

[code]#include <stdio.h>
#include <math.h>
struct stacja { int x,y; } p;
int sat;
int max;
int zb;
int next;
int size;
int last;
double e;
int w;
int k;
int swap(int *a, int *b)
{
int i;
i=*a;
*a=*b;
*b=i;
}
int make_set(int x)
{
zb[x]=x;
next[x]=0;
size[x]=1;
last[x]=x;
}
int join(int a, int b)
{
int i,x,y;
x=a;
y=b;
/* if (size[zb[y]]>size[zb[x]])
swap(&x,&y);*/
next[last[zb[x]]]=zb[y];
last[zb[x]]=last[zb[y]];
i=zb[y];
size[zb[x]]+=size[zb[y]];
while (i)
{
zb[i]=zb[x];
i=next[i];
}
}
int cmp(const void *a, const void *b)
{
if (e[*(int *)a]<e[*(int *)b])
return -1; else
if (e[*(int *)a]>e[*(int *)b])
return 1; else
return 0;
}
int main()
{
int it,i,x,y,ie,j;
int maxe;
scanf("%d",&it);
while (it)
{
it--;
scanf("%d%d",&sat,&max);
ie=max*(max-1)/2;
for (i=1;i<=max;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
make_set(i);
}
i=0;
for (x=1;x<=max;x++)
for (y=x+1;y<=max;y++)
{
e[i]=hypot((double)(p[x].x-p[y].x),(double)(p[x].y-p[y].y));
k[i]=x;
k[i++]=y;
}
for (i=0;i<ie;i++)
w[i]=i;
j=0;
qsort(w,ie,sizeof(int),cmp);
/* for (i=0;i<ie;i++)
printf("wierz %d %d od %.2lf\n",k[w[i]],k[w[i]],e[w[i]]);*/
for (i=0;i<ie && j<max-sat;i++)
{
x=k[w[i]];
y=k[w[i]];
if (zb[x]==zb[y])
continue;
j++;
join(x,y);
}
printf("%.2lf\n",e[w[i-1]]);
}
return 0;
}[/c][/code]

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
it seems that u and my prob are same...
but wanting a suggestion..
isn't there any...?
"Everything should be made simple, but not always simpler"

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
I changed the hypot(a,b) function
into sqrt(a*a+b*b) and got accepted. Should I be angry at the guys writing stdlib or is it my fault that I rely on their code? gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
You should be angry with the Gnu C compiler. If you use the -ansi flag (as uva does) it gives you no header file for hypot(), because hypot() is not in the ANSI C definition. But you don't get a link-time error because the non-ansi implementation exists in the library. Since there is no header, it is implicitly declared as "int hypot()" when it should be "double hypot()" and you get wrong results.

A side-effect of this weirdness is that if you put in a correct declaration for hypot, you can use it.
makbet wrote:I changed the hypot(a,b) function
into sqrt(a*a+b*b) and got accepted. Should I be angry at the guys writing stdlib or is it my fault that I rely on their code? minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
I'm using binary search on D^2. Then take sqrt. What can be wrong with my code??[cpp]#include <iostream>
#include <vector>
#include <utility>
#include <deque>
#include <math.h>
#include <string>
using namespace std;

char help;
vector < pair < long, long > > data;
long s, n, t, d, u;

inline long dist(const pair < long, long > &p1, const pair < long, long > &p2){
return (p1.first - p2.first)*(p1.first - p2.first) +
(p1.second - p2.second)*(p1.second - p2.second);
}

bool good(long d){
memset(help, 0, sizeof(help));
long cnt = 0;

for(unsigned long i = 0; i < data.size(); i++)
if(!help){
help = 1;
cnt++;
deque < long > q;
q.push_back(i);
while(q.size()){
for(unsigned long j = 0; j < data.size(); j++)
if(!help[j])
if(dist(data[q.front()], data[j]) <= d){
q.push_back(j);
help[j] = 1;
}

q.pop_back();
}
}
return cnt <= s;
}

int main(){

cin >> t;
while(t-- && cin >> s >> n){
if(!s) s = 1;
data.resize(n);
for(long i = 0; i < n; i++) cin >> data.first >> data.second;

u = 1000000000;
d = 0;

while(u - d > 1)
if(good((u + d)/2)) u = (u + d)/2;
else d = (u + d)/2;
if(good(d)) u = d;

cout.setf(ios::fixed);
cout.precision(2);

cout << sqrt(1.0*u) << endl;
}

return 0;
}
[/cpp]

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### 10369 - Arctic Network

i don't understand why the answer for sample input is 212.13
sombody please explain the sample I/Os .. ;;
thanks..

Code: Select all

``````1
2 4
0 100
0 300
0 600
150 750
``````

Code: Select all

``````212.13
``````
Last edited by helloneo on Tue May 22, 2007 8:04 am, edited 2 times in total.

DongJoo Kim
New poster
Posts: 20
Joined: Tue Sep 20, 2005 9:20 am
Location: Daejeon, Korea
There are 6 edges.

If we number edges 0,1,2,3..
0-1 : 200
2-3 : 212.132
1-2 : 300
1-3 : 474.342
0-2 : 500
0-3 : 667.083

Among this 6 edges. You choose first 2 edges. The maximum value of edge is the answer.

The tricky thing in this problem is about 'satellite channel'. The channel means not 'edges' but 'vertices'.

I think this is enough to solve the problem smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
this is not a binary search problem.
fahim
#include <smile.h>

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
smilitude wrote:this is not a binary search problem.
Maybe not, but got it solved with binary search after adding one line to the code that I posted.

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
really? wow... actually i didnt get that approach..
fahim
#include <smile.h>

Oronno
New poster
Posts: 21
Joined: Sun Jul 09, 2006 1:42 pm
Location: Dhaka
Contact:
I can't understand many of this board tell that prim's algo might give WA for this problem. How is it possible, where Kruskal works but prim's not! It is impossible that, for a graph, Prim's give different result than Kruskal. Both are ok.
I just solve this problem using exactly Prim's Algorithm.
I like programming but i am so lazy to do it...