10308 - Roads in the North

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

Moderator: Board moderators

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

10308 - Roads in the North

Post by Joe Smith »

Am I wrong in assuming the graph is a tree? I interpret the statement "there is only one route from a village to a village that does not pass through some other village twice" as meaning there are no cycles, and it says there's only 1 component. If this is right then it's easy, just dfs, but I'm getting WA.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Post by shahriar_manzoor »

There can be inputs with zero cities!!!

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Post by Joe Smith »

shahriar_manzoor wrote:There can be inputs with zero cities!!!
Oops, I guess I can't read.

Thanks!

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger »

I use DFS. But :x Can anybody say why this program get WA?

[pascal]Program p10308;

Const MaxN = 10000;
p1 = 5000;
p2 = 500;

Type Comp = Integer;

Var Map : Array[1..MaxN]of Record A,B : Integer; L : Comp; End;
list,p : Array[0..MaxN]of Integer;
Road,R : Array[1..MaxN]of Comp;
i,N,M : Integer;
a,b,j : Integer;
lmin : Integer;
min,mid : Comp;
l,max : Comp;
tt : byte;

Function GetLast(E : Integer) : Integer;
Var Use : Array[1..MaxN]of byte;
i,j : Integer;
ok : Byte;
begin
FillChar(Use,SizeOf(Use),0);
Use[E]:=1;
Road[E]:=0;
l:=0;
GetLast:=E;
While True Do begin
ok:=1;
for i:=1 to M do
if (Use[Map.A]=1)and(Use[Map.B]=0) then begin
ok:=0;
Use[Map.B]:=1;
Road[Map.B]:=Road[Map.A]+Map.L;
if Road[Map.B]>l then begin
l:=Road[Map.B];
GetLast:=Map.B;
end;
end else
if (Use[Map.A]=0)and(Use[Map[i].B]=1) then begin
ok:=0;
Use[Map[i].A]:=1;
Road[Map[i].A]:=Road[Map[i].B]+Map[i].L;
if Road[Map[i].A]>l then begin
l:=Road[Map[i].A];
GetLast:=Map[i].A;
end;
end;
if ok=1 then Break;
end;
end;

begin
While Not Eof(InPut) Do begin
N:=0;
M:=0;
i:=1;
While True do begin
if (Eof(InPut))or(Eoln(InPut)) then Break;
Readln(a,b,l);
if a>N then N:=a;
if b>N then N:=b;
Map[i].A:=a;
Map[i].B:=b;
Map[i].L:=l;
i:=i+1;
M:=M+1;
if (Eof(InPut))or(Eoln(InPut)) then Break;
end;
if Eoln(InPut) then Readln;
if N=0 then Readln;
i:=GetLast(1);
GetLast(i);
Writeln(l:0);
end;
end.[/pascal]

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

10308

Post by Rivaldo »

It says "The villages are numbered from 1."
Does it mean the villages are numberd 1, 2, 3, 4, ..., n, when the number of village is n.

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Post by Maxim »

What like looks input case when there are zero villages? Is it a blank line, or it consists of line with 0 for village i or j? Please, help. I've solved it and tested it on my computer, but when I send it, it gets Runtime Error (Invalid memory reference). I decrease index of each vilage after scaning it. Upper bound sure doesn't make any trouble.

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

Re:

Post by scythe »

Uhm.. yeah

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar »

I has not solved this problem but from the problem statement i cant asure that the cities are numered sequentially 1, 2, ..., n. Maybe some data set could be 1, 2, 6, 12, maybe not. But the problem statement leave the second posibility open so you shuld take care of.
Those Who Don't Know History are doomed to repeat it

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

Ah, could be right

Post by scythe »

I got ac, but my source code works for that kind of tests.
I'm sorry, I guess the cities could be numbered in a non-compact manner. (I misunderstood your question)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

shahriar_manzoor wrote:There can be inputs with zero cities!!!
Well, I know we're required to answer '0' in this case, but it makes no sense. The distance between two non-existent cities is zero? That's only because one particular implementation of an algorithm to solve this problem would answer '0'. Mathematical sense would give 'undefined'.

It's a pitty to see a perfect problem spoiled by this kind of nonsense.

(Shahriar, I know you're not the problemsetter, just the messenger; this is not a personal attack :wink: )

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

little joey wrote:Well, I know we're required to answer '0' in this case, but it makes no sense. The distance between two non-existent cities is zero? That's only because one particular implementation of an algorithm to solve this problem would answer '0'. Mathematical sense would give 'undefined'.
It would also be consistent with mathematical sense (more so than letting it be undefined, in my opinion) to define the distance as negative infinity in such cases (cf. the degree of the zero polynomial, for example).

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

Post by Dominik Michniewski »

I use DFS() to solve this problem, but I got WA several times ...
Is any trap in this problem ?
My program outputs 0 when input has na cities. When I traverse graph in every node I remember two maximal distances from this node to any children. Sum of this values in every node is maximal distance between nodes. If I compute all nodes, I should get correct answer. Of course if graph is connected ... Am I wrong with this algorithm ? Could anyone help me ?

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

Post by artem »

Dominik your algorithm is right (I got AC with same algorithm).
In this algorithm only one intersting place:

Code: Select all

DFS(...){
 int max1=0,max2=0,.....; 
 ......  // cycle
 t=DFS(.....);
 if (t > max1){
 max2=max1;
 max1=t;
 }
 else  if (t > max2) max2=t;
 ....... // end cycle
 if (max1+max2 > max) max=max1+max2;
 return max1;
}
where max - is our answer and max1,max2 - two maximal distances from this node ( max1 >= max2)

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

INPUT:

Code: Select all

5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
(blank line)
(blank line)
(blank line)
(blank line)
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
OUTPUT:

Code: Select all

22
0
22

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

daveon wrote:INPUT:

Code: Select all

5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
(blank line)
(blank line)
(blank line)
(blank line)
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
OUTPUT:

Code: Select all

22
0
22

Why is it like that..?
Problem statement say
Two consecutive sets are separated by a blank line

Post Reply

Return to “Volume 103 (10300-10399)”