10985 - Rings'n'Ropes

Moderator: Board moderators

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

10985 - Rings'n'Ropes

How was the correct solution's time complexity?

now I'm using is O((n^2)*m)

I did it because I thinked it should be close to time limit

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
O(n^3) algo exists.

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan
How the O(n^3) method work?

I'm running crazy

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
A variation of floyd's.

Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:
I had to use bit masks to get the O(N^3) complexity. I won't call my algorithm as Floyd's modification, although I used Floyd to find shortest distances between every pair of vertices. Is there any O(N^3) algorithm without bit masks?

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Is your algorithm truly O(n^3), or simply O(n^4) with a very small constant because of the bitmasks? There is a O(n^3) algorithm without bitmasks.
If only I had as much free time as I did in college...

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
Yes, I have a O(N^3+NM) algorithm without bitmasks. But it is not really a variation of floyd's. It requires you to precalculate for every pair of nodes u,v how many edges incident to u are on a shortest path from u to v.

Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:
Yes, actually my first solution was O(N^4) with small constant.
Thanks, krijger, I've understood your algorithm.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Finally got the O(n^3) algorithm instead of TLE. Thx for all the ideas on this board.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
Can someone explain me the algorithm here??
Or some hints from someone??

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
First hint: you should use floyd-warshall to find the distance between each pair of vertices.

Second hint: The question asks to find the number of edges that lies on shortest paths from each pair of vertices. Output the maximum of these.

Third hint: define function f(u,v) that counts the number of edges incident to u that is on some shortest path between u and v. Find a recurrence to compute f(u,v) for all u,v in O(n^3) time.

Fourth hint: figure out how to find the answers from the function f

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
[Edited] I got it! and I am 3rd on the rank!