10397 - Connect the Campus
Moderator: Board moderators
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Well, suit yourself then. I only called it 'weird' and 'hard to understand' because I think it is. I have a hard time reading your code, but maybe I'm too unexperienced with Pascal (I only have 700+ ACs in that language).
The main reason for asking for the full code is to compile and test it myself, which saves me from a lot of pen and paper debugging. I'm not doubting the correctness of your functions (although 90% of all bugs are in code that the programmer 'knows' is correct), I only want to use them to test your program.
As for the i/o: it's almost the same as mine. The only difference is that I handle extra blank lines at the end of the input. I don't know if they're present in this particular problem. I always handle them by default. Your program would crash if they are there.
End of discussion.
-little joey
The main reason for asking for the full code is to compile and test it myself, which saves me from a lot of pen and paper debugging. I'm not doubting the correctness of your functions (although 90% of all bugs are in code that the programmer 'knows' is correct), I only want to use them to test your program.
As for the i/o: it's almost the same as mine. The only difference is that I handle extra blank lines at the end of the input. I don't know if they're present in this particular problem. I always handle them by default. Your program would crash if they are there.
End of discussion.
-little joey
Sorry for being rude because I've been upset due to this problem for more then 3 months!!!!!
I finally get ACC!!!! Yes!!! There ARE blank lines in the input!!!!!!! Be careful!!!!!!!!!
Thx little joey for your suggestion. Thx v much!!!
I finally get ACC!!!! Yes!!! There ARE blank lines in the input!!!!!!! Be careful!!!!!!!!!
Thx little joey for your suggestion. Thx v much!!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Lots of WAs
Hi,
I have made a lot of submissions for this problem but still WA.
My program covers all test cases which I have met in this
thread and in other threads dedicated to problem 10397.
I have also taken into consideration the remarks about
the existence of blank line in the Judge's Input.
For sorting the edges I use heap sort. My program is in Java.
Any ideas about what could my problem be are welcome!
Thanks in advance.
I have made a lot of submissions for this problem but still WA.
My program covers all test cases which I have met in this
thread and in other threads dedicated to problem 10397.
I have also taken into consideration the remarks about
the existence of blank line in the Judge's Input.
For sorting the edges I use heap sort. My program is in Java.
Any ideas about what could my problem be are welcome!
Thanks in advance.
My program covers these test cases but also gets WA.
I've read in other threads dedicated to problem 10397
that the Judge's Input for this problem contains empty lines
and most probably also ends with empty lines.
Do you take this into account ?
I am wondering why a standard Minimum Spanning Tree
problem like this one could be so hard. Seems weird to me.
I've read in other threads dedicated to problem 10397
that the Judge's Input for this problem contains empty lines
and most probably also ends with empty lines.
Do you take this into account ?
I am wondering why a standard Minimum Spanning Tree
problem like this one could be so hard. Seems weird to me.
Could someone give any ideas of why that problem surprisingly
happens to be so hard although it is a standard MST problem ?
Other threads about this problem 10397 are:
http://online-judge.uva.es/board/viewtopic.php?t=1686
and
http://online-judge.uva.es/board/viewtopic.php?t=2957
Is the test data posted in the second one correct ?
Could someone with an ACC program verify that test data.
happens to be so hard although it is a standard MST problem ?
Other threads about this problem 10397 are:
http://online-judge.uva.es/board/viewtopic.php?t=1686
and
http://online-judge.uva.es/board/viewtopic.php?t=2957
Is the test data posted in the second one correct ?
Could someone with an ACC program verify that test data.
The test data is correct.Sedefcho wrote:Could someone give any ideas of why that problem surprisingly
happens to be so hard although it is a standard MST problem ?
Other threads about this problem 10397 are:
http://online-judge.uva.es/board/viewtopic.php?t=1686
and
http://online-judge.uva.es/board/viewtopic.php?t=2957
Is the test data posted in the second one correct ?
Could someone with an ACC program verify that test data.
Before getting accepted I had troubles with sets of colinear points. I made a random input generator and tested my program with lots of inputs without finding any flaws. At last I found this trivial input that broke my algorithm:
INPUT
Code: Select all
4
0 4
0 1
0 3
0 0
1
4 2
Code: Select all
3.00
Ciao!!!
Caudio
Last edited by CDiMa on Wed Jun 22, 2005 9:45 am, edited 1 time in total.
Hi, CDiMa,
First, thank you.
Unfortunately my program does not fail on that
test you've given. It prints 3.00 as it should.
Why should sets containing colinear points be of any
problem. It is simply an MST problem in which we assign
the distances ( the weights of the edges ) in the
following way:
1) if Node1 is connected to Node2 with cable Dist(node1, node2)=0
2) if Node1 is NOT connected to Node2 with cable Dist(node1, node2)
is the plane distance between the points in the plane represented
by Node1 and Node2
That's it. Then we just execute the Kruskal's algorithm or the
Prim's algorithm and everything should be fine.
Do you have any other ideas ?
I think the Judge's input contains blank lines or something like that.
I've read things like that in the threads about problem 10397.
I take this into account too. Still WA.
Any ideas are welcome.
First, thank you.
Unfortunately my program does not fail on that
test you've given. It prints 3.00 as it should.
Why should sets containing colinear points be of any
problem. It is simply an MST problem in which we assign
the distances ( the weights of the edges ) in the
following way:
1) if Node1 is connected to Node2 with cable Dist(node1, node2)=0
2) if Node1 is NOT connected to Node2 with cable Dist(node1, node2)
is the plane distance between the points in the plane represented
by Node1 and Node2
That's it. Then we just execute the Kruskal's algorithm or the
Prim's algorithm and everything should be fine.
Do you have any other ideas ?
I think the Judge's input contains blank lines or something like that.
I've read things like that in the threads about problem 10397.
I take this into account too. Still WA.
Any ideas are welcome.
Well, I know this was a problem with the particular algorithm I used. I mentioned it just in case...Sedefcho wrote:Unfortunately my program does not fail on that
test you've given. It prints 3.00 as it should.
Do you consider every possible connection between the nodes? That's O(n^2)!Sedefcho wrote:Why should sets containing colinear points be of any
problem. It is simply an MST problem in which we assign
the distances ( the weights of the edges ) in the
following way:
1) if Node1 is connected to Node2 with cable Dist(node1, node2)=0
2) if Node1 is NOT connected to Node2 with cable Dist(node1, node2)
is the plane distance between the points in the plane represented
by Node1 and Node2
That's it. Then we just execute the Kruskal's algorithm or the
Prim's algorithm and everything should be fine.
I select a subset of the connections, apply a constrained MST on the subset and fail on sets of colinear points
Anyway, you could try this input/output and see how your program behaves... It's only a big sample that maybe will show some precision error.
Ciao!!!
Claudio
ACC at last !
Thanks Claudio, the 3 test cases which you have given me
have revealed more than a precision bug in my code.
It wasn't a big logical bug actually but still I wouldn't see
it without some decent test cases.
Yes, I consider all the connections, it's O(N^2), right. I just
use the standard Kruskal's algorithm, that's why I was so
sure I have to get ACC.
Now I got ACC. Both Running Time and
Memory Usage of my program are terrible
But I think now I am the only one proud owner
of a Java-solution of this problem
I take one of the last 15 places in the standings for this problem:
http://acm.uva.es/cgi-bin/OnlineJudge?P ... 5:425:1.00
Claudio, once again thanks a lot for the help!
have revealed more than a precision bug in my code.
It wasn't a big logical bug actually but still I wouldn't see
it without some decent test cases.
Code: Select all
Do you consider every possible connection between the nodes? That's O(n^2)!
use the standard Kruskal's algorithm, that's why I was so
sure I have to get ACC.
Now I got ACC. Both Running Time and
Memory Usage of my program are terrible
But I think now I am the only one proud owner
of a Java-solution of this problem
I take one of the last 15 places in the standings for this problem:
http://acm.uva.es/cgi-bin/OnlineJudge?P ... 5:425:1.00
Claudio, once again thanks a lot for the help!
10397 -- HELP...
Hi
I try from a weak for this problem(10397) and i found no bug in my code.i try all the possible input of mine && read all the threds in board for this problem.but i got right result.but judge say WA...
can any body give me some test data.i become crazy for this problem...PLZZZ .. Help Me
THANK"S IN ADVANCE
Rocky
I try from a weak for this problem(10397) and i found no bug in my code.i try all the possible input of mine && read all the threds in board for this problem.but i got right result.but judge say WA...
can any body give me some test data.i become crazy for this problem...PLZZZ .. Help Me
THANK"S IN ADVANCE
Rocky
oh... simple mistek
Ah... Got it ACC now
Thank's
Rocky
Thank's
Rocky
I am getting RTE... if i increase the MAX size to 1001 .. i get MLE ... I dont know what to do ?? pls help me
Here is ma code
Here is ma code
Code: Select all
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXNODE 1001
#define NIL -1
#define MAXDEG MAXNODE*MAXNODE
#define N 1001
double graph[N][N];
struct edge{
int from;
int to;
double weight;
};
struct vertex{
int rank;
int parent;
};
struct edge * edges[MAXDEG];
struct edge * mst_edges[MAXNODE];
struct vertex *vertices[MAXNODE];
int partition(int p,int r)
{
int i,j;
double w;
struct edge *e_tmp;
w = edges[r]->weight;
i = p-1;
for(j=p;j<r;j++)
{
if(edges[j]->weight<=w)
{
i = i+1;
e_tmp = edges[i];
edges[i] = edges[j];
edges[j] = e_tmp;
}
}
e_tmp = edges[i+1];
edges[i+1]=edges[r];
edges[r]=e_tmp;
return i+1;
}
void sort_edges(int p, int r)
{
int q;
if(p<r)
{
q = partition(p,r);
sort_edges(p,q-1);
sort_edges(q+1,r);
}
}
int extract_edge(int n)
{
int i,j,m;
struct edge *e;
m = 0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(graph[i][j]==NIL)
continue;
e = (struct edge *)malloc(sizeof(struct edge));
e->from = i;
e->to = j;
e->weight = graph[i][j];
edges[m]=e;
m++;
}
return m;
}
void make_set(int x)
{
struct vertex *v;
v = (struct vertex *)malloc(sizeof(struct vertex));
v->parent = x;
v->rank = 0;
vertices[x]=v;
}
void set_link(int x, int y)
{
int xrank,yrank;
xrank = vertices[x]->rank;
yrank = vertices[y]->rank;
if(xrank>yrank)
{
vertices[y]->parent = x;
}
else
{
vertices[x]->parent = y;
if(xrank==yrank)
vertices[y]->rank = yrank+1;
}
}
int find_set(int x)
{
if(x!=vertices[x]->parent)
{
vertices[x]->parent = find_set(vertices[x]->parent);
}
return vertices[x]->parent;
}
void set_union(int x, int y)
{
set_link(find_set(x),find_set(y));
}
void kruskal(int n, int m)
{
int i;
int u,v;
int tail;
for(i=0;i<n;i++)
{
make_set(i);
}
tail = 0;
sort_edges(0,m-1);
for(i=0;i<m;i++)
{
u = edges[i]->from;
v = edges[i]->to;
if(find_set(u)!=find_set(v))
{
mst_edges[tail] = edges[i];
++tail;
set_union(u,v);
}
}
}
int main()
{
int n,m;
int i,j;
int a,b;
int w;
double sum;
int x[N],y[N];
double res;
int c;
//printf("Number of vertices?: ");
while(scanf("%d",&n)==1)
{
/*
if(n==0)
break;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
graph[i][j]= NIL;
}
while(1)
{
scanf("%d%d%d",&a,&b,&w);
if(a==0 && b==0 && w==0)
break;
graph[a][b]=w;
//graph[b][a]=w;
}
*/
for(i=0;i<n;i++)
{
scanf("%d%d",&x[i],&y[i]);
for(j=0;j<n;j++)
graph[i][j]=-1;
}
scanf("%d",&c);
for(i=0;i<c;i++)
{
scanf("%d%d",&a,&b);
graph[a-1][b-1]=0;
graph[b-1][a-1]=0;
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(graph[i][j]==-1 && i!=j)
{
double p,q;
p = (double)(x[i]-x[j])*(double)(x[i]-x[j]);
q = (double)(y[i]-y[j])*(double)(y[i]-y[j]);
res=sqrt( p + q );
graph[i][j]=res;
graph[j][i]=graph[i][j];
}
}
}
m = extract_edge(n);
kruskal(n,m);
sum = 0.0;
for(i=0;i<n-1;i++)
{
sum += mst_edges[i]->weight;
}
printf("%.2lf\n",sum);
//printf("Number of vertices?: ");
}
return 0;
}
Time that gone is gone forever ...
to sakhassan:
Hi sakhassan, use of malloc() should be done judiciously... it may cause you RTEorMLE... I haven't gone through your code... rather, posting mine in stead... [no dynamic memory needed].
Code: Select all
long p[SIZE + 1];
long rank[SIZE + 1];
void MakeSet(long x)
{
p[x] = x;
rank[x] = 0;
}
void Union(long x, long y)
{
Link(FindSet(x),FindSet(y));
}
void Link(long x, long y)
{
if(rank[x] > rank[y])
{
p[y] = x;
}
else
{
p[x] = y;
if(rank[x] == rank[y])
{
rank[y] = rank[y] + 1;
}
}
}
long FindSet(long x)
{
if(x != p[x])
{
p[x] = FindSet(p[x]);
}
return p[x];
}
regards,
nymo
nymo
-
- New poster
- Posts: 27
- Joined: Tue Dec 20, 2005 9:14 am
- Location: Egypt
Hey guys. I'm getting this problem TLE. I'm sure of the algorithm and had used the same code before in another problem (and got it AC). The only difference here is the maximum input for the problem which is causinf the TLE.
I used MST Kruskal but I'm still a beginner in graph algorithms. When I check to see if 2 vertices are in the same set or not I use BFS on one ending point and check whether the other ending point is dscovoered or not. I think there is other efficient method to do so, but I can't think of any with complexity < O(n). If someone can help me with this I may get rid of the TLE problem.
Another thing. How to make use of the "existed edges" in optimizing the code??!! I just put them in the graph as they are and assigned the edge weight to be 0.
I used MST Kruskal but I'm still a beginner in graph algorithms. When I check to see if 2 vertices are in the same set or not I use BFS on one ending point and check whether the other ending point is dscovoered or not. I think there is other efficient method to do so, but I can't think of any with complexity < O(n). If someone can help me with this I may get rid of the TLE problem.
Another thing. How to make use of the "existed edges" in optimizing the code??!! I just put them in the graph as they are and assigned the edge weight to be 0.