Discussion @ 1143. Electric Path @ Timus Online Judge

Why my greedy algorithm get WA? I think it's ok. Please, help me! ! !(+)

Posted by Nazarov Denis (nsc2001@rambler.ru) 30 Jan 2002 23:19

My program:

Program t1143;{$N+}

Type Point=record x,y :real end;

Var   N,i,j,k : integer;
      Pred,MP : integer;
      Poly     : array[1..200]of Point;
      D        : array[1..200,1..200]of real;
      Use      : array[1..200]of byte;
      Curl     : real;
      Minl,Min : real;

Function Dist(A,B : Point) : extended;
begin
Dist := sqrt ( sqr(A.x-B.x) + sqr(A.y-B.y) ) ;
end;

begin
Read(N);
for i:=1 to N do read(Poly[i].x,Poly[i].y);
if N=1 then begin
writeln('0.000');
halt(0);
end;
for i:=1 to N do
for j:=1 to N do
D[i,j]:=Dist(Poly[i],Poly[j]);
Minl:=1E30;
for k:=1 to N do begin
Pred:=k;
Curl:=0;
FillChar(Use,SizeOf(Use),0);
Use[Pred]:=1;
for i:=1 to N-1 do begin
    Min:=1E30;
    for j:=1 to N do
     if Use[j]=0 then
      if D[Pred,j]<Min then begin
       Min:=D[Pred,j];
       MP:=j;
      end;
    Pred:=MP;
    Use[Pred]:=1;
    Curl:=Curl+Min;
   end;
if Curl<Minl then
   Minl:=Curl;
end;
Writeln(Minl:0:3);
end.

I get AC. But all this look strange: I use my greedy algorithm if N>=10 else I use full search !(and I get AC). Can anybody explain it?

Posted by Nazarov Denis (nsc2001@rambler.ru) 30 Jan 2002 23:49

> My program:
>
> Program t1143;{$N+}
>
> Type Point=record x,y :real end;
>
> Var   N,i,j,k : integer;
>       Pred,MP : integer;
>       Poly     : array[1..200]of Point;
>       D        : array[1..200,1..200]of real;
>       Use      : array[1..200]of byte;
>       Curl     : real;
>       Minl,Min : real;
>
> Function Dist(A,B : Point) : extended;
> begin
>   Dist := sqrt ( sqr(A.x-B.x) + sqr(A.y-B.y) ) ;
> end;
>
> begin
> Read(N);
> for i:=1 to N do read(Poly[i].x,Poly[i].y);
> if N=1 then begin
> writeln('0.000');
> halt(0);
> end;
> for i:=1 to N do
> for j:=1 to N do
>   D[i,j]:=Dist(Poly[i],Poly[j]);
> Minl:=1E30;
> for k:=1 to N do begin
>   Pred:=k;
>   Curl:=0;
>   FillChar(Use,SizeOf(Use),0);
>   Use[Pred]:=1;
>   for i:=1 to N-1 do begin
>     Min:=1E30;
>     for j:=1 to N do
>      if Use[j]=0 then
>       if D[Pred,j]<Min then begin
>        Min:=D[Pred,j];
>        MP:=j;
>       end;
>     Pred:=MP;
>     Use[Pred]:=1;
>     Curl:=Curl+Min;
>    end;
>   if Curl<Minl then
>    Minl:=Curl;
> end;
> Writeln(Minl:0:3);
> end.

Re: Because the test cases are so easy !

Posted by Tran Nam Trung (trungduck@yahoo.com) 31 Jan 2002 13:44

> > My program:
> >
> > Program t1143;{$N+}
> >
> > Type Point=record x,y :real end;
> >
> > Var   N,i,j,k : integer;
> >       Pred,MP : integer;
> >       Poly     : array[1..200]of Point;
> >       D        : array[1..200,1..200]of real;
> >       Use      : array[1..200]of byte;
> >       Curl     : real;
> >       Minl,Min : real;
> >
> > Function Dist(A,B : Point) : extended;
> > begin
> >   Dist := sqrt ( sqr(A.x-B.x) + sqr(A.y-B.y) ) ;
> > end;
> >
> > begin
> > Read(N);
> > for i:=1 to N do read(Poly[i].x,Poly[i].y);
> > if N=1 then begin
> > writeln('0.000');
> > halt(0);
> > end;
> > for i:=1 to N do
> > for j:=1 to N do
> >   D[i,j]:=Dist(Poly[i],Poly[j]);
> > Minl:=1E30;
> > for k:=1 to N do begin
> >   Pred:=k;
> >   Curl:=0;
> >   FillChar(Use,SizeOf(Use),0);
> >   Use[Pred]:=1;
> >   for i:=1 to N-1 do begin
> >     Min:=1E30;
> >     for j:=1 to N do
> >      if Use[j]=0 then
> >       if D[Pred,j]<Min then begin
> >        Min:=D[Pred,j];
> >        MP:=j;
> >       end;
> >     Pred:=MP;
> >     Use[Pred]:=1;
> >     Curl:=Curl+Min;
> >    end;
> >   if Curl<Minl then
> >    Minl:=Curl;
> > end;
> > Writeln(Minl:0:3);
> > end.

Discussion of Problem 1143. Electric Path