10034 - Freckles

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Solution solved

Post by troy » Mon Nov 22, 2004 11:12 pm

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?

Post by GavinLan » Wed Apr 27, 2005 8:09 am

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

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Sun Jun 12, 2005 12:30 am

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!

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Sun Jun 12, 2005 2:29 am

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
Location: Bangladesh

WA in 10034

Post by Biks » Thu Jun 28, 2007 12:52 am

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
New poster
Posts: 1
Joined: Thu Nov 08, 2007 11:10 am

Runtime error

Post by rahulshandilya » Thu Nov 08, 2007 11:31 am

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
New poster
Posts: 10
Joined: Fri Dec 07, 2007 10:42 am

Post by ovidiu » Fri Dec 07, 2007 11:16 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
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Fri Mar 21, 2008 4:57 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: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

10034 - Freckles

Post by lnr » Thu Oct 02, 2008 5:18 pm

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

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

Re: 10034 - Freckles

Post by Rocky » Mon Oct 06, 2008 8:34 pm

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: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 10034 - Freckles

Post by lnr » Tue Oct 07, 2008 4:43 am

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

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

Re: 10034 - Freckles

Post by Rocky » Tue Oct 07, 2008 10:42 am

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

Re: 10034 - Freckles

Post by lnr » Tue Oct 07, 2008 3:41 pm

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 10034 - Freckles

Post by Obaida » Sun Apr 18, 2010 8:44 am

I just coded Kruskal's Algorithm and got Accepted in very good time :D.
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

Post by codeworrior » Tue May 11, 2010 1:49 pm

//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.

Post Reply

Return to “Volume 100 (10000-10099)”