10034 - Freckles

[troy]

OK Found what the problem was.
Input buffer size was to small once changed to 256 char it was accepted.

Have to rewrite my the readln method so it doesnt require a buffer size.

Thanks Troy

[GavinLan]

My 10034 Freckles keeps WA. I use Kruskal algorithm to solve the mini span tree, But I really can't findout the bugs. Any One can help me ? Thanks very much. My code follow:

#include<iostream.h>
#include<math.h>
#include<iomanip.h>

struct sPoint
{
double x, y;
};
struct edgenode
{
int head, end;
};

const int MAXN = 101, MAXE = 5000;
double edge[MAXE];

sPoint freckle[MAXN];
edgenode EdgeOrder[MAXE];

double distance(sPoint p1, sPoint p2);
void sortEdge(int EdgeNum);
double MiniSpanTree_Kruskal( int vertexNum, int edgeNum );

int main()
{
int cn, n, i, j, EdgeNum=0;
double ans=0;

//ifstream cin("G:\\Program\\ACM\\SZU\\a.in");
//ofstream cout("G:\\Program\\ACM\\SZU\\a.out");

cin>>cn;
while( cn-- )
{
cin>>n;
i=0;
while( i<n ) cin>>freckle.x>>freckle.y, i++;

if( n==1 ){
if( cn == 0 ) cout<<"0.00"<<endl;
else cout<<"0.00"<<endl<<endl;
continue;
}

// get lenth of edges
EdgeNum = 0; // edge numbers
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
{
edge[EdgeNum] = distance(freckle, freckle[j]);
EdgeOrder[EdgeNum].head = j, EdgeOrder[EdgeNum].end = i;
EdgeNum++;
}

// call Kruskal span tree, return mini path
ans = MiniSpanTree_Kruskal( n, EdgeNum );

// print the result
cout.setf(ios::fixed);
if( cn==0 ) cout<<setprecision(2)<<ans<<endl;
else cout<<setprecision(2)<<ans<<endl<<endl;
}
return 0;
}

double distance(sPoint p1, sPoint p2)
{
return sqrt( pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2) );
}

// sorting for edge
void sortEdge( int len )
{
int i, j, tmphead, tmpend;
bool order = false;
double tmp;

// Bubble sort
for(i=1; i<len && !order; ++i)
{
order = true;
for(j=0; j<len-i; ++j)
{
if( edge[j] > edge[j+1] )
{
tmp = edge[j+1], tmphead = EdgeOrder[j+1].head, tmpend = EdgeOrder[j+1].end;
edge[j+1] = edge[j], EdgeOrder[j+1].head = EdgeOrder[j].head, EdgeOrder[j+1].end = EdgeOrder[j].end;
edge[j] = tmp, EdgeOrder[j].head = tmphead, EdgeOrder[j].end = tmpend;
}
order = false;
}
}
}

double MiniSpanTree_Kruskal( int vertexNum, int edgeNum )
{
bool Select[MAXN];
int i, SelectCount;
double minsum;

// sort for edges
sortEdge( edgeNum );
/*
//test the data
cout<<"EdgeNum"<<setw(10)<<"EdgeLen"<<setw(10)<<"end"<<setw(10)<<"head"<<endl;
for(i=0; i<edgeNum; ++i)
cout<<setw(3)<<i<<setw(13)<<edge<<setw(10)<<EdgeOrder.end<<setw(10)<<EdgeOrder.head<<endl;
cout<<endl;
*/
// initialize tree NULL
for(i=0; i<vertexNum; ++i) Select = false;

SelectCount = 0;
minsum = 0;
for(i=0; SelectCount<vertexNum-1 && i<edgeNum; ++i)
{
if( !(Select[EdgeOrder.head] && Select[EdgeOrder.end]) )
{
Select[EdgeOrder.head] = Select[EdgeOrder[i].end] = true;
SelectCount++;
minsum += edge[i];
}
}

return minsum;
}

[jaracz]

I'm not sure if I understood this pro correct

I think it is simple, but gives me also WA

here's my code

Code: Select all

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

int main()
{
    int n,m;
    double a,b,x,y,rope;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
        rope = 0;
        scanf("%d",&m);
        scanf("%lf%lf",&a,&b);
        for(int i = 1; i < m; i++)
        {
            scanf("%lf%lf",&x,&y);
            rope += sqrt(pow(x-a,2)+pow(y-b,2));
            a = x;b = y;
        }    
        printf("%.2lf\n\n",rope);
    }    
    return 0;
}    

Regards

[Mohammad Mahmudur Rahman]

To jaracz ->
There is an edge between any two points, not the adjacent points. I guess you are treating the input graph itself as the spanning tree which is not correct. Hope it helps.

[Biks]

I am getting WA on this problem
i used Kruskal algorithm
my solution pass testcase i have found in the board
Can any one help me finiding my error
I am sending here my code

Code: Select all

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

#define ERROR 0.00000001


#define MAXV 110
#define MAXDEGREE 110
#define MAXINT 2e15

long parent[MAXV+1];

typedef struct{
	double x;
	double y;
}POint;
POint point[102];



typedef struct{
	long v;
	double weight;
}edge;

typedef struct{
	edge edges[MAXV+1][MAXDEGREE];
	long degree[MAXV+1];
	long nvertices;
	long nedges;
}graph;


typedef struct{
	long x,y;
	double w;
}qedge;

typedef struct{
	qedge element[MAXV+1];
	long head;
	long tail;
}queue;


void initialize_graph(graph *g);
void insert_edge(graph *g,long x,long y,double w,bool directed);
double kruskal(graph *g);
qedge deque(queue *q);
void set_q(queue *q,graph *g);
int sortfunc(const void *a,const void *b);

double distance_between_point(double x1,double y1,double x2,double y2)
{
	return (  sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) )   );
}

void main()
{
	long i,j,test,n,start;
	double distance,cost=0,min;
	graph g;
	bool directed=false;
	
	
	scanf("%ld",&test);
	
	while(test--)
	{
		
		scanf("%ld",&n);
		
		for(i=0;i<n;i++)
			scanf("%lf %lf",&point[i].x,&point[i].y);
		
		min=MAXINT;
		initialize_graph(&g);
		
		g.nvertices = n;
		
		
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
			{
				distance = distance_between_point(point[i].x,point[i].y,point[j].x,point[j].y);
				insert_edge(&g,i+1,j+1,distance,directed);
				if(distance<min){
					min = distance;
					start = j+1;
				}
				
			}
		}
		
		/*
		printf("%ld\n",g.nedges);
		
		  for(i=1;i<=g.nedges;i++)
		  {
		  for(j=0;j<g.degree[i];j++)
		  printf("%ld %ld %lf\n",i,g.edges[i][j].v,g.edges[i][j].weight);
		  
			}
		*/		
		
		
		cost = kruskal(&g);
		
		
		printf("%.2lf\n",cost);
		if(test>0)
			printf("\n");
		
		
	}//while
}//main


void initialize_graph(graph *g)
{
	long i;
	g->nvertices=0;
	g->nedges=0;
	for(i=1;i<=MAXV;i++)
		g->degree[i]=0;
}

void insert_edge(graph *g,long x,long y,double w,bool directed)
{
	g->edges[x][g->degree[x]].v=y;
	g->edges[x][g->degree[x]].weight=w;
	g->degree[x]++;
	if(directed==false)
		insert_edge(g,y,x,w,true);
	else
		g->nedges++;
}




double kruskal(graph *g)
{
	queue q;
	qedge now,store[MAXV+1];
	long set[MAXV+1];
	long cnt=0;
	long i,tmp;
	
	double cost;
	
	for(i=0;i<=MAXV;i++)
		set[i]=i;
	set_q(&q,g);
	while(q.head<q.tail)
	{
		now=deque(&q);
		if(set[now.x]!=set[now.y])
		{
			store[cnt]=now;
			cnt++;
			tmp=set[now.y];
			for(i=0;i<=MAXV;i++)
			{
				if(set[i]==tmp)
					set[i]=set[now.x];
			}
		}
		if(cnt==g->nvertices-1)
			break;
	}
	cost=0;
	//printf("The edges of MST are :(Kruskal's algorithm evaluated)\n");
	for(i=0;i<cnt;i++)
	{
		//printf("%ld %ld %lf\n",store[i].x,store[i].y,store[i].w);
		cost+=store[i].w;
	}
	return cost;
	//printf("The total length of MST is : %lf\n",cost);
}

qedge deque(queue *q)
{
	qedge ed;
	ed=q->element[q->head];
	q->head++;
	return(ed);
}

void set_q(queue *q,graph *g)
{
	long i,j;
	for(i=0;i<=MAXV;i++)
		q->element[i].w=MAXINT;
	q->head=q->tail=0;
	for(i=1;i<=g->nvertices;i++)
	{
		for(j=0;j<g->degree[i];j++)
		{
			q->element[q->tail].x=i;
			q->element[q->tail].y=g->edges[i][j].v;
			q->element[q->tail].w=g->edges[i][j].weight;
			q->tail++;
		}
	}
	qsort(&q->element,q->tail,sizeof(qedge),sortfunc);
}

int sortfunc(const void *a,const void *b)
{
	qedge *x,*y;
	x=(qedge *)a;
	y=(qedge *)b;
	
	if (fabs(x->w-x->w)<ERROR)return 0;  
	if(x->w>y->w)
		return 1;
	if(x->w<y->w)
		return -1;
	
	return 0;
	
}

[rahulshandilya]

following is my code it is running very well for the test cases which i fond in this forum but when i am submitting my solution it is giving Runtime error plz tell me where im wrong,i used simply kruskal algorithm..............

Code: Select all

#include<iostream>
#include<cmath>
#include<algorithm>
#include <iomanip>
using namespace std;
int rank[1000];
int p[1000];


struct node
{
       int s;
       int d;
       float w;
};

bool operator <(const node &x1,const node &x2)
{
     if(x1.w<x2.w)
     return true;
     
     return false;
}

void makeset(int x)
{
           p[x]=x;
           rank[x]=0;
     
}

int findset(int px)
{
     if(px!=p[px])
     return px=findset(p[px]);
     else
     return px;
}

void mergset(int px,int py)
{
     int x=findset(px);
     int y=findset(py);
     
     if(rank[x]>rank[y])
     p[y]=x;
     
     else
     p[x]=y;
     
     if(rank[x]==rank[y])
     rank[y]=rank[y]+1;
}

int main()
{
    int t;
    cin>>t;
    for(int k=0;k<t;k++)
    {
          
            int n;
            cin>>n;
            float ans=0.0;
            float a[1000][2];
            node x[1001];
           
            for(int i=0;i<n;i++)
            {
                    cin>>a[i][0]>>a[i][1]; 
            }
            int c=0;
           
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(i!=j)
                    {
                         float xx=a[i][0]-a[j][0];
                         float yy=a[i][1]-a[j][1];
                         
                         xx=xx*xx;
                         yy=yy*yy;
                         
                         xx=sqrt(xx+yy);
                           
                         x[c].s=i;
                         x[c].d=j;
                         x[c].w=xx;
                         c++;
                           
                    }
                }
           }
         
           for(int i=0;i<c;i++)
           makeset(i);
   
           sort(x,x+c);
           
   
           for(int i=0;i<c;i++)
           {
                   if(findset(x[i].s)!=findset(x[i].d))
                   {
                         ans+=x[i].w;
                         mergset(x[i].s,x[i].d);                           
                   }
            }
            if(k<t-1)
            printf("%.2lf\n\n",ans);
            else
            printf("%.2lf\n",ans);
   
   
    }
    
} 
  
            

[ovidiu]

You use too small data structures. Just think how many edges can be.

Reading your code I found that after last output there need only one endl and got ACC my code. Thank you!

In my beginner opinion, judging as WA if there are 0 or 2 endl it is a "little" ... unpleasant ...

[turcse143]

U got RTE with the signal of floating point error
there is no need to declare the array size 1000.

[lnr]

I have confusion about this problem.
Initially i thought that every vertex such as
1's coordinate is connected with 2,3,4,5,6,7.............up to freckle numbers.
Then I calculated the distances from every vertex to every vertex
considering this as an undirected graph.

Am i right or wrong.
Would someone please tell me.
I am getting wrong answer in 0.10s.

[Rocky]

yeah...
you are right.
you should calculate all the distance from one node to another node & build the the connection.
after that you need to optimize it as the problem say.

Best Of Luck
Rocky

[lnr]

To Rocky

yeah...
you are right.
you should calculate all the distance from one node to another node & build the the connection.
after that you need to optimize it as the problem say.

Would you please tell me more about optimization.
I tried using prims algorithm.

[Rocky]

i used primes too...
can you send me your code via pm?
It will easy for me to help you.

Best Of Luck
Rocky

[lnr]

Accepted.
I got the bug.

[Obaida]

I just coded Kruskal's Algorithm and got Accepted in very good time .

[codeworrior]

//code removed after AC








my code is giving me WA in .008 sec...i cant find any case in which my code is failing ...can anyone give a case in which it fails.....thnx in advance...