10397 - Connect the Campus

[little joey]

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

[Observer]

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

[Sedefcho]

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.

[Sedefcho]

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.

[Sedefcho]

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.

[CDiMa]

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.

The test data is correct.
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

OUTPUT

Code: Select all

3.00

I don't think that many programs will fail on this simple input, but mine shurely did

Ciao!!!

Caudio

[Sedefcho]

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.

[CDiMa]

Unfortunately my program does not fail on that
test you've given. It prints 3.00 as it should.

Well, I know this was a problem with the particular algorithm I used. I mentioned it just in case...

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 consider every possible connection between the nodes? That's O(n^2)!
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

[Sedefcho]

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.

Code: Select all

Do you consider every possible connection between the nodes? That's O(n^2)!  

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!

[Rocky]

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

[Rocky]

Ah... Got it ACC now

Thank's
Rocky

[sakhassan]

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

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;
}

[nymo]

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];
}

[sakhassan]

Thanks. But malloc doesn't bother me ..... I change my double variable to int and got AC ... I don't know why double makes trouble

[asmaamagdi]

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.