OJ Board

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

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

Thanx Tomal for ur time. But how do i do it?

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.

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[501];
int sat;
int max;
int zb[501];
int next[501];
int size[501];
int last[501];
double e[124750];
int w[124750];
int k[124750][2];
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][0]=x;
k[i++][1]=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]][0],k[w[i]][1],e[w[i]]);*/
for (i=0;i<ie && j<max-sat;i++)
{
x=k[w[i]][0];
y=k[w[i]][1];
if (zb[x]==zb[y])
continue;
j++;
join(x,y);
}
printf("%.2lf\n",e[w[i-1]]);
}
return 0;
}[/c][/code]

it seems that u and my prob are same...
but wanting a suggestion..
isn't there any...?

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?

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?

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[600];
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]

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

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

this is not a binary search problem.

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.

really? wow... actually i didnt get that approach..

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.