## 10034 - Freckles

Moderator: Board moderators

troy
New poster
Posts: 8
Joined: Fri Jul 23, 2004 10:39 am
Location: New Zealand

### Solution solved

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
New poster
Posts: 1
Joined: Wed Apr 27, 2005 7:44 am

### 10034Freckles keeps WA! Any help for me?

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

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 )
{
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] )
{
}
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
for(i=0; i<edgeNum; ++i)
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)
{
{
SelectCount++;
minsum += edge[i];
}
}

return minsum;
}

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
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
keep it real!

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
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.
You should never take more than you give in the circle of life.

Biks
New poster
Posts: 6
Joined: Sat Jun 03, 2006 12:55 pm

### WA in 10034

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;

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 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);
{
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;
return(ed);
}

void set_q(queue *q,graph *g)
{
long i,j;
for(i=0;i<=MAXV;i++)
q->element[i].w=MAXINT;
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
New poster
Posts: 1
Joined: Thu Nov 08, 2007 11:10 am

### Runtime error

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;
int p;

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;
node x;

for(int i=0;i<n;i++)
{
cin>>a[i]>>a[i];
}
int c=0;

for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i!=j)
{
float xx=a[i]-a[j];
float yy=a[i]-a[j];

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
New poster
Posts: 10
Joined: Fri Dec 07, 2007 10:42 am
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
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
U got RTE with the signal of floating point error
there is no need to declare the array size 1000.
''I want to be most laziest person in the world''

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

### 10034 - Freckles

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.
I am getting wrong answer in 0.10s.
Last edited by lnr on Fri Oct 17, 2008 9:04 pm, edited 1 time in total.

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

### Re: 10034 - Freckles

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
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

### Re: 10034 - Freckles

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.
I tried using prims algorithm.
Last edited by lnr on Fri Oct 17, 2008 9:04 pm, edited 1 time in total.

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

### Re: 10034 - Freckles

i used primes too...
can you send me your code via pm?

Best Of Luck
Rocky

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm

### Re: 10034 - Freckles

Accepted.
I got the bug.
Last edited by lnr on Thu Oct 09, 2008 3:47 pm, edited 2 times in total.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10034 - Freckles

I just coded Kruskal's Algorithm and got Accepted in very good time .
try_try_try_try_&&&_try@try.com
This may be the address of success.

codeworrior
New poster
Posts: 14
Joined: Wed Oct 21, 2009 11:04 am

### Re: 10034 - Freckles

//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...
Last edited by codeworrior on Fri May 28, 2010 10:46 am, edited 1 time in total.