10397 - Connect the Campus

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Aug 06, 2003 6:07 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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Aug 07, 2003 6:05 am

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!!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Lots of WAs

Post by Sedefcho » Mon Jun 20, 2005 3:02 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon Jun 20, 2005 3:05 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon Jun 20, 2005 3:09 pm

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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Tue Jun 21, 2005 9:48 am

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

Ciao!!!

Caudio
Last edited by CDiMa on Wed Jun 22, 2005 9:45 am, edited 1 time in total.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Jun 21, 2005 1:18 pm

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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Wed Jun 22, 2005 9:43 am

Sedefcho wrote: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...
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.
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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

ACC at last !

Post by Sedefcho » Wed Jun 22, 2005 12:08 pm

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!

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

10397 -- HELP...

Post by Rocky » Thu Nov 17, 2005 12:36 pm

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

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

oh... simple mistek

Post by Rocky » Thu Nov 24, 2005 12:50 pm

Ah... Got it ACC now

Thank's
Rocky

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Sun Jan 07, 2007 12:39 pm

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

Time that gone is gone forever ...

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

to sakhassan:

Post by nymo » Mon Jan 08, 2007 8:14 am

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

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Mon Jan 08, 2007 1:46 pm

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 :o :o :-?
Time that gone is gone forever ...

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt

Post by asmaamagdi » Thu Aug 30, 2007 3:39 am

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.

Post Reply

Return to “Volume 103 (10300-10399)”