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

Post Reply
xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

10034 - Freckles

Post by xenon » Tue Aug 06, 2002 9:48 am

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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Aug 06, 2002 10:01 am

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

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

Post by xenon » Tue Aug 06, 2002 10:49 am

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?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Aug 06, 2002 11:33 am

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 ...
maybe this help you :-)

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

hi...xenon

Post by Even » Fri Aug 16, 2002 8:25 pm

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

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

Post by broderic » Sat Aug 17, 2002 3:10 am

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

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

Post by xenon » Sat Aug 17, 2002 7:28 am

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

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

10034 why runtime error?

Post by DreamLinuxer » Tue Oct 01, 2002 3:24 pm

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

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

Post by Ivan Golubev » Tue Oct 01, 2002 3:36 pm

Now it has multiple input, read the description.

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

Post by DreamLinuxer » Tue Oct 01, 2002 3:41 pm

Ivan Golubev wrote:Now it has multiple input, read the description.
appreciate your help :D

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

10034

Post by htl » Tue Oct 22, 2002 11:10 am

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

Post by htl » Wed Nov 27, 2002 1:12 am

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

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

Post by Adrian Kuegel » Wed Nov 27, 2002 9:02 am

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

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

Post by htl » Wed Nov 27, 2002 5:32 pm

Thanks very much.

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

10034

Post by zsepi » Wed Jan 15, 2003 6:00 am

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,&y);
for(i=0,k=0;i<n;i++) {
for(j=i+1;j<n;j++) {
dx=x-x[j];
dy=y-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='0';
n--;
i=0;
cost=0;
while(n>0) {
if(status[e.v1]=='0' || status[e.v2]=='0') {
cost+=e.cost;
status[e.v1]='1';
status[e.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.

Post Reply

Return to “Volume 100 (10000-10099)”