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

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

Post by helloneo » Thu Aug 30, 2007 5:03 am

You might want to look up "union find" for disjoint set..
I found this from google..

http://www.cse.ust.hk/~dekai/271/notes/L09/L09.pdf

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Mon Mar 24, 2008 8:58 pm

its a problem of mst.
u can use prims algo.
before that u have to set 0 to the given edge.
''I want to be most laziest person in the world''

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

Post by asmaamagdi » Tue Mar 25, 2008 3:01 am

Thank u guys for ur help. I was giving up this problem but I got it ACed finally :D
---
Asmaa Magdi

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: ACC at last !

Post by andmej » Wed Mar 26, 2008 4:44 am

Sedefcho wrote:

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.
I've used O(n^2) for the connections too and got accepted. But I'm not happy with my running time.

How can I improve the part of building the graph (That is, to not consider all possible connections between nodes)? Thanks.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

marib
New poster
Posts: 2
Joined: Mon Apr 07, 2008 12:10 am

Re:

Post by marib » Tue Apr 15, 2008 7:26 pm

asmaamagdi wrote:Thank u guys for ur help. I was giving up this problem but I got it ACed finally :D
How?? What you have changed in the code?

marib
New poster
Posts: 2
Joined: Mon Apr 07, 2008 12:10 am

Re:

Post by marib » Tue Apr 15, 2008 8:03 pm

sakhassan wrote: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 :-?
Which double variable you change to int??

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

Re: 10397 Connect the Campus, WA????

Post by asmaamagdi » Tue Apr 15, 2008 8:09 pm

How?? What you have changed in the code?
used the union find algorithm.
---
Asmaa Magdi

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

RTE

Post by Ron » Thu Sep 11, 2008 1:45 pm

Help..!!
Why RTE ??

code:->

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
bool f[1000];
vector<int> v,w;
vector< vector<int> > cn;

void fn(int k){
	int i,j,n;
	for(i=0;i<cn[k].size();i++){
		n=cn[k][i];
		if(f[n]){
			f[n]=0;
			j=0;
			while(w[j]!=n)	j++;
			w.erase(w.begin()+j);
			v.push_back(n);
			fn(n);
		}
	}
}

int main(){
	int n,m,c[1000][2],i,j,p,p1,p2;
	int mn,d;
	double ans;
	while(cin>>n){
		for(i=1;i<=n;i++){
			cin>>c[i][0]>>c[i][1];
			f[i]=1;
		}
		cin>>m;
		cn.clear();
		cn.resize(n+1);
		while(m--){
			cin>>i>>j;
			cn[i].push_back(j);
			cn[j].push_back(i);
		}
		v.clear();w.clear();
		v.push_back(1);
		for(i=2;i<=n;i++)
			w.push_back(i);
		f[1]=0;
		fn(1);
		ans=0.0;
		while(w.size()>0){
			mn=(c[v[0]][0]-c[w[0]][0])*(c[v[0]][0]-c[w[0]][0])+(c[v[0]][1]-c[w[0]][1])*(c[v[0]][1]-c[w[0]][1]);
			p1=v[0];p2=w[0];
			p=0;
			for(i=0;i<v.size();i++){
				for(j=0;j<w.size();j++){
					d=(c[v[i]][0]-c[w[j]][0])*(c[v[i]][0]-c[w[j]][0])+(c[v[i]][1]-c[w[j]][1])*(c[v[i]][1]-c[w[j]][1]);
					if(d<mn){
						mn=d;
						p1=v[i];p2=w[j];
						p=j;
					}
				}
			}
			ans+=sqrt(1.0*mn);
			f[w[p]]=0;
			fn(p2);
			v.push_back(w[p]);
			w.erase(w.begin()+p);
		}
		cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl;
	}
	return 0;
}


mrlinx
New poster
Posts: 3
Joined: Wed May 06, 2009 5:03 am

10397 - Connect the Campus

Post by mrlinx » Wed May 06, 2009 5:08 am

I get a Runtime Error from UVA and Segmentation Error in another system, probably with the same data tests...
My code checks for array bounds, but I can't seem to understand the failure.
Anyone can see the problem?

Code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_V 1000

typedef struct { int v1; int v2; float cost; } edge;
typedef struct point { int x; int y; } point;

edge edges[MAX_V];
point buildings[MAX_V];
int set[MAX_V];
int rank[MAX_V];

int compare (const void * a, const void * b) {
	float cost_a = ((edge*) a)->cost, cost_b = ((edge*) b)->cost;
	if(cost_a > cost_b) return 1;
	else if(cost_a == cost_b) return  0;
	else return -1;
}

void link(int a, int b) {
	if(rank[a]>rank[b])
		set[b]=a;
	else {
		set[a]=b;
		if(rank[a]==rank[b])
			rank[b]++;
	}
}
int find(int a) {
	if(set[a]!=a) 
		set[a]=find(set[a]);
	return set[a];
}

int main (int argc, const char * argv[]) {
	//freopen("input.txt", "rb", stdin);
	//freopen("output.txt", "wb", stdout);

	int num_buildings = -1, num_pipes = -1;
	while (scanf("%d%*c", &num_buildings) == 1) {
		int num_edges = 0;
		for (int i=0; i<num_buildings; i++) {
			scanf("%d %d%*c", &buildings[i].x, &buildings[i].y);
			set[i]=i;
			rank[i]=0;
		}
		
		for (int i=0; i<num_buildings; i++) {
			for (int k=i+1; k<num_buildings; k++) {
				edges[num_edges].v1 = i;
				edges[num_edges].v2 = k;
				edges[num_edges].cost = sqrt(pow((float) (buildings[i].x-buildings[k].x), 2) + pow((float) (buildings[i].y-buildings[k].y), 2));
				num_edges++;
			}
		}

		scanf("%d%*c", &num_pipes);
		for (int i = 0, start, end; i<num_pipes; i++) {
			scanf("%d %d%*c", &start, &end);
			if (start >= 1 && end >= 1)
				link(find(start-1), find(end-1));
		}

		qsort(edges, num_edges, sizeof(edge), compare);

		float minCost = 0;
		for (int i=0; i<num_edges; i++) {
			int v1 = find(edges[i].v1), v2 = find(edges[i].v2);
			if (v1 != v2) {
				link(v1, v2);
				minCost += edges[i].cost;
			}
		}		
		printf("%.2f\n", minCost);
	}
    return 0;
}

Thanks for all the help. This is my last resort, I've spent quite a few hours looking at it, and testing several inputs.
Last edited by mrlinx on Sat May 09, 2009 1:26 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10397 - Connect the Campus

Post by mf » Wed May 06, 2009 12:58 pm

Well, you seem to have allocated a very small array for edges:

Code: Select all

#define MAX_V 1000
...
edge edges[MAX_V];
There's almost 300000 edges in the worst case, not 1000.

mrlinx
New poster
Posts: 3
Joined: Wed May 06, 2009 5:03 am

Re: 10397 - Connect the Campus

Post by mrlinx » Wed May 06, 2009 2:07 pm

Hi,

Thanks for catching that. I solved my RE.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 10397 - Connect the Campus

Post by saiful_sust » Fri Sep 04, 2009 6:49 pm

Hi some one PLZ help me

i solve 10147 same as this problem
but i got WA in 10397
:oops: :oops: :oops:

Code: Select all

CUT after ACC................. :lol:  :lol: 
Last edited by saiful_sust on Sun Sep 06, 2009 10:53 am, edited 1 time in total.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 10397 - Connect the Campus

Post by saiful_sust » Sat Sep 05, 2009 3:24 pm

Some PLZ help me................ :oops: :oops: :oops:

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 10397 - Connect the Campus

Post by saiful_sust » Sun Sep 06, 2009 11:00 am

I solve this problem same code as i post here

the problem was double
i change the double type to int then it got acc....... :lol: :lol:

But what is wrong with double.?????????

regan
New poster
Posts: 4
Joined: Wed Apr 28, 2010 6:24 pm

10397 RTE & RTE !!!

Post by regan » Wed Jan 26, 2011 7:55 pm

Got RTE several times with my code....can any one help me by detecting the reason ....Here is my code...

Code: Select all

#include<iostream>
#include<math.h>
using namespace std;
long n,m,i,j,f,t,p[10000];
double extra;
struct edge
{
 long from;
 long to;
 double dist;
}edg[1000000];

struct node
{
 long x;
 long y;
}nod[10000];
long parent(long u)
{
 if(p[u]==-1) return u;
 else
 {
  p[u]=parent(p[u]);
  return p[u];
 }
}

int fn(const void *a,const void *b)
{
 edge *x=(edge *)a;
 edge *y=(edge *)b;
 if(x->dist-y->dist>0.00) return 1;
 if(x->dist-y->dist>0.00) return -1;
 return 0;
}

void FIND_MST()
{
 qsort(edg,n*n,sizeof(edg[0]),fn);
 
 for(i=0;i<n*n;i++)
 {
  if(parent(edg[i].from)!=parent(edg[i].to))
  {
   extra
  +=edg[i].dist;
   p[parent(edg[i].from)]=parent(edg[i].to);
  }
 }
}

int main()
{
double aa,aaa;
 while(scanf("%ld",&n)!=EOF)
 {
  for(i=0;i<n;i++)
  {
   p[i]=-1;
   cin>>f>>t;
   nod[i].x=f+10000;
   nod[i].y=t+10000;
  }
  cin>>m;
  for(i=0;i<m;i++)
  {
   cin>>f>>t;
   edg[(f-1)*n+t-1].from=f-1;
   edg[(f-1)*n+t-1].to=t-1;
   p[parent(edg[(f-1)*n+t-1].from)]=parent(edg[(f-1)*n+t-1].to);
  }
  for(i=0;i<n;i++)
  {
   for(j=0;j<n;j++)
   {
    edg[(i*n)+j].from=i;
    edg[(i*n)+j].to=j;
    if(i==j)
    {
     edg[(i*n)+j].dist=0.00;
    }
    else
    {
        
        edg[(i*n)+j].dist=sqrt((nod[i].x-nod[j].x)*(nod[i].x-nod[j].x)+(nod[i].y-nod[j].y)*(nod[i].y-nod[j].y));
    }
   }
  }
  extra=0.00;
  FIND_MST();
  printf("%.2lf\n",extra);
 }
 return 0;
}

Post Reply

Return to “Volume 103 (10300-10399)”