125 - Numbering Paths

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

Moderator: Board moderators

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Tue Aug 26, 2003 6:14 pm

Build your paths matrix (as you did) then use a modified Floyd Warshall to remove cycles.

ie

Code: Select all

for(int k = 0; k < nodes; k++)
	if(matrix[k][k] > 0)
		for(int i = 0; i < nodes; i++)
			for(int j = 0; j < nodes; j++)
				if(matrix[i][k] != 0 && matrix[k][j] != 0)
					matrix[i][j] = -1
Also, remove the constraints from your path building section (i!=k) it just messes things up. I would do this instead:

Code: Select all

for(int k = 0; k < nodes; k++)
	for(int i = 0; i < nodes; i++)
		for(int j = 0; j < nodes; j++)
			matrix[i][j] += matrix[i][k] * matrix[k][j]


xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Tue Aug 26, 2003 6:18 pm

It has to do with your pruning methods. You are not removing all the nodes along all the cycles. In fact, I could only find 1 test case where this failed, and even then it was only 1 element of the matrix that was off.

About the constraints (i!=k): You can safely ignore these constraints.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Aug 27, 2003 5:40 am

Mine was O(n^3). What I did was use Floyd-Warshall and then I used it again..

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Wed Aug 27, 2003 1:23 pm

I'm not sure why your algorithm is O(n^6) but you can split them up and get into 2 parts that each runs in O(n^3) time.
O(n^3) time to run Floyd to find the number of paths,
O(n^3) time to find cycles.
Then for each (u, v), if the second part reports a cycle print -1, else print the number of paths found in part 1...

Hope this helps.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Wed Aug 27, 2003 4:34 pm

You are correct junjieliang. It was my mistake. My program is actually O(N^3). I should have thought a bit more before I started typing. :)

My program does exactly what you specified. Of course, my stupid mistake was saying that n^3 + n^3 == n^6 :roll:

Thanks!

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Wed Oct 08, 2003 11:21 am

I am having trouble with this problem. getting WA. please help me :cry:
here is my code:
[c]removed[/c]
Last edited by Subeen on Wed Oct 08, 2003 1:14 pm, 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 » Wed Oct 08, 2003 11:43 am

Graphs in input can be multigraphs ....

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)

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Wed Oct 08, 2003 1:13 pm

finally got AC. the bug is in my findpath function.

anyway, Dominik, what do u mean by
Graphs in input can be multigraphs ....
please, expain.

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

Post by Dominik Michniewski » Wed Oct 08, 2003 1:17 pm

That means that input could be in form of:
I don't remember exact format, so I write idea only ...)
1->2
1->3
1->2
....
so from 1 to 2 exist two paths, not one ....

Best regards
DM

PS. This is my mistake, when I try to solve this problem :-)
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)

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Wed Oct 08, 2003 3:10 pm

thanks, Dominik.
but I think I didn't handle the case (same input more than once) but got AC. :-?

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

Post by Dominik Michniewski » Thu Oct 09, 2003 8:08 am

Maybe test cases doesn't contian such cases or you have 'mistake' in your code such that you got correct answer :-) I don't know ...
But I remember, that I found some IO in net from original contest and such cases were there. So I think, that probably exists in judge data. BTW.I got Acc when I handle multigraphs:-)

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)

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

125 : "Numbering Paths" WA - please help

Post by Almost Human » Tue Nov 18, 2003 11:46 am

Is there any special or tricky input to consider ?

In all cities, intersections are numbered sequentially from 0 to the ``largest'' intersection

It means that if there is 5 intersection, then those intersections would be 0 , 1 , 2 , 3 , and 4 right ?

My idea to solve it is using a modified Floyd-Warshall algorithm.

I use edge[k+1][j] += edge[k][k] * edge[k][k][j] rather than
edge[k+1][j] = min ( edge[k][j] , edge[k][k] + edge[k][k][j] ). this is where I made the modification.

After that, I just print the result after checking if a cycle exist for all vertex v that included in the path of u-v.

Sorry about my bad english.

Any help and suggestion would be highly appreciated.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

125 : "Numbering Paths" WA - please help

Post by Almost Human » Tue Nov 18, 2003 11:48 am

Is there any special or tricky input to consider ?

In all cities, intersections are numbered sequentially from 0 to the ``largest'' intersection

It means that if there is 5 intersection, then those intersections would be 0 , 1 , 2 , 3 , and 4 right ?

My idea to solve it is using a modified Floyd-Warshall algorithm.

I use edge[k+1][j] += edge[k][k] * edge[k][k][j] rather than
edge[k+1][j] = min ( edge[k][j] , edge[k][k] + edge[k][k][j] ). this is where I made the modification.

After that, I just print the result after checking if a cycle exist for all vertex v that included in the path of u-v.

Sorry about my bad english.

Any help and suggestion would be highly appreciated.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

125 problem:WA

Post by Eduard » Sun Nov 23, 2003 8:15 am

I get WA when i submit it but it works correct for any test on my computer(also for multigraphs too)
Can someone help me.
This is my code.
[pascal]program acm125;
var a,b,c,s,sum:array[0..30,0..30] of integer;
number,i,j,n,k,u,v,max:integer;
procedure mult;
var i,j,k:integer;
begin
for i:=0 to n do
for j:=0 to n do
c[i,j]:=0;
for i:=0 to n do
for j:=0 to n do
for k:=0 to n do
begin
c[i,j]:=c[i,j]+b[i,k]*a[k,j];
end;
for i:=0 to n do
for j:=0 to n do
begin
s[i,j]:=s[i,j]+c[i,j];
b[i,j]:=c[i,j];
c[i,j]:=0;
end;
end;
begin
number:=-1;
while not eof do
begin
number:=number+1;
read(n);
for i:=0 to n do
for j:=0 to n do
a[i,j]:=0;
v:=0;
max:=0;
for i:=1 to n do
begin
read(u,v);
if max<u then max:=u;
if max<v then max:=v;
a[u,v]:=a[u,v]+1;
end;
n:=max;
for i:=0 to n do
for j:=0 to n do
begin
b[i,j]:=a[i,j];
s[i,j]:=a[i,j];
end;

for i:=1 to n do
mult;
for i:=0 to n do
for j:=0 to n do
sum[i,j]:=s[i,j];
for i:=1 to n+1 do
mult;
for i:=0 to n do
for j:=0 to n do
if sum[i,j]<>s[i,j] then sum[i,j]:=-1;
writeln('matrix for city ',number);
for i:=0 to n do
begin
for j:=0 to n do
write(sum[i,j],' ');
writeln;
end;
end;
end.[/pascal]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Sat Nov 29, 2003 9:55 pm

got AC, thanks

Post Reply

Return to “Volume 1 (100-199)”