## 10034 - Freckles

Moderator: Board moderators

### 10034 - Freckles

This looks like a basic application of Prim's algo, and that's how I treat it. But I keep getting WA. Can anybody point me to my mistake?

[pascal]program p10034(input,output);

{SPOILER DELETED}

[/pascal]

Thanks so much,
-xenon
Last edited by xenon on Sat Aug 17, 2002 7:24 am, edited 1 time in total.
xenon
Learning poster

Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

I use Prim algorithm too, but I use to implement it priority queue and got accepted ... maybe try to change your code in this way ?
your code looks the same (at first look)
Greetings
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

Does 'Priority cue' mean sorting the distances first? I can see that that would improve the speed, but not the outcome. I don't think speed is a factor here, because my program WA's in 0.000 seconds.
Something else must be wrong. Could rounding be an issue?
xenon
Learning poster

Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

I don't think, that precision error should be a problem. I didn't worry about that....
I use queue to insert distances, which I found, in right place ... it's a kind of insertion sort for first loop
and Prim works like BFS with this priority queue ...
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### hi...xenon

hello....xenon...

you can try to print one blank line after the last case...

for this stupid bug...I try Kruskal and Prim and spend two hours on it...

finally, I mark off my last line ( if( T ) puts("") )...

just like your ( if (caseno > 1) then writeln ; )

and then...it work...=.=....
Even
Learning poster

Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

hmm, very strange. I had the exact same problem as xenon
with constant WA's...print a newline after the last case, and you get
PE. What I don't understand is how that can result in WA?

thanks for the tip

broderick
broderic
New poster

Posts: 34
Joined: Thu Jun 06, 2002 4:35 am

Thanks even, now I also get PE by adding just one writeln statement!
This is really stupid. The judges should look into it.
xenon
Learning poster

Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

### 10034 why runtime error?

what's the change after rejudge????
Last edited by DreamLinuxer on Tue Oct 01, 2002 3:39 pm, edited 1 time in total.
DreamLinuxer
New poster

Posts: 8
Joined: Tue Oct 01, 2002 3:22 pm

Now it has multiple input, read the description.
Ivan Golubev
Experienced poster

Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Ivan Golubev wrote:Now it has multiple input, read the description.

DreamLinuxer
New poster

Posts: 8
Joined: Tue Oct 01, 2002 3:22 pm

### 10034

I just use simple Kruskal algo. But it keeps getting WA. I even read my friend's code and still can't find out the bug. What's wrong with my code?
[c]
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define SQUARE(x) ((x)*(x))
typedef struct edges
{
int v1,v2;
double len;
}edge;
int comp(const void*,const void*);
void main(void)
{
int count,x,y,z,a,n,set[100],temp;
double pos[100][2],sum;
edge e[5000];
scanf("%d",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
scanf("%d",&n);
for(y=0;y<n;y++)
scanf("%lf %lf",&pos[y][0],&pos[y][1]);
a=0;
for(y=0;y<n;y++)
for(z=y+1;z<n;z++)
e[a].v1=y,e[a].v2=z,e[a++].len=sqrt(SQUARE(pos[y][0]-pos[z][0])+SQUARE(pos[y][1]-pos[z][1]));
qsort(e,a,sizeof(edge),comp);
for(y=0;y<n;y++)
set[y]=y;
for(y=0,sum=0;y<a;y++)
if(set[e[y].v1]!=set[e[y].v2])
{
temp=set[e[y].v1];
for(z=0;z<n;z++)
if(set[z]==temp)
set[z]=set[e[y].v2];
sum+=e[y].len;
}
printf("%.2lf\n",sum);
}
}
int comp(const void *a,const void *b)
{
return ((edge *)a)->len-((edge *)b)->len;
}
[/c]
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

I don't know why I got WA when I use the qsort function.
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Your sort function is wrong, you don't sort integers here!!
use perhaps:
int comp(const void *a,const void *b)
{
if (((edge *)a)->len>((edge *)b)->len) return 1;
if (((edge *)a)->len<((edge *)b)->len) return -1;
return 0;
}
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Thanks very much.
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 10034

honestly, if someone could explain me why on earth I get runtime error with this problem, would appreciate it... thanx
[c]#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MX 101

typedef struct _edge {
int v1,v2;
double cost;
}edge;

edge e[5001];
double x[MX],y[MX];

int compare(const void *a, const void *b) {
double x;
edge *i,*j;

i=(edge *)a;
j=(edge *)b;
x=i->cost-j->cost;
if(x==0.0) return 0;
else if(x>0) return 1;
else return -1;
}

void getData(int n) {
int i,j,k;
double dx,dy;

for(i=0;i<n;i++) scanf("%lf %lf",&x[i],&y[i]);
for(i=0,k=0;i<n;i++) {
for(j=i+1;j<n;j++) {
dx=x[i]-x[j];
dy=y[i]-y[j];
e[k].v1=i;
e[k].v2=j;
e[k].cost=sqrt(dx*dx+dy*dy);
k++;
}
}
qsort(e,k,sizeof(edge),compare);
}

void kruskal(int n) {
char status[n];
int i;
double cost=0.0;

for(i=0;i<n;i++) status[i]='0';
n--;
i=0;
cost=0;
while(n>0) {
if(status[e[i].v1]=='0' || status[e[i].v2]=='0') {
cost+=e[i].cost;
status[e[i].v1]='1';
status[e[i].v2]='1';
n--;
}
i++;
}
printf("%.2lf\n",cost);
}

main() {
int N,n;

scanf("%d",&N);
while(N-->0) {
scanf("%d",&n);
getData(n);
kruskal(n);
if(N!=0) printf("\n");
}
}[/c]
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
zsepi
Learning poster

Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

Next