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

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

Post by likhan » Thu Nov 07, 2002 10:03 am

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

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

Post by kmhasan » Thu Nov 07, 2002 10:46 am

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

Post by likhan » Thu Nov 07, 2002 9:08 pm

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

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

using kruskal's algorithm

Post by kmhasan » Fri Nov 08, 2002 2:43 am

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

Post by makbet » Wed Mar 26, 2003 9:28 pm

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]

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Mar 28, 2003 12:47 pm

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

Post by makbet » Fri Mar 28, 2003 1:01 pm

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? :wink:

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Sun Mar 30, 2003 5:26 pm

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? :wink:

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Mon Jun 14, 2004 10:08 pm

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]

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

10369 - Arctic Network

Post by helloneo » Tue Dec 27, 2005 6:37 pm

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

Post by DongJoo Kim » Wed Dec 28, 2005 12:59 pm

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 :D

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Thu Jul 27, 2006 6:20 pm

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

Post by minskcity » Thu Jul 27, 2006 6:42 pm

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.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Thu Jul 27, 2006 7:17 pm

really? wow... actually i didnt get that approach..
fahim
#include <smile.h>

User avatar
Oronno
New poster
Posts: 21
Joined: Sun Jul 09, 2006 1:42 pm
Location: Dhaka
Contact:

Post by Oronno » Tue Mar 25, 2008 9:13 pm

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...

Post Reply

Return to “Volume 103 (10300-10399)”