10985 - Rings'n'Ropes

All about problems in Volume 109. 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
polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

10985 - Rings'n'Ropes

Post by polone » Tue Jan 24, 2006 4:46 pm

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:

Post by mf » Tue Jan 24, 2006 4:52 pm

O(n^3) algo exists.

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

Post by polone » Wed Jan 25, 2006 8:18 am

How the O(n^3) method work?

please tell me :oops:

I'm running crazy

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

Post by Larry » Wed Jan 25, 2006 5:10 pm

A variation of floyd's.

Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:

Post by Renat » Thu Jan 26, 2006 3:16 pm

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?

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Jan 26, 2006 5:43 pm

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

Post by krijger » Thu Jan 26, 2006 5:43 pm

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:

Post by Renat » Thu Jan 26, 2006 8:08 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Jan 28, 2006 1:18 am

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

Post by asif_rahman0 » Tue Aug 08, 2006 7:34 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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Thu Aug 10, 2006 9:03 am

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:

Post by Moha » Mon Aug 21, 2006 1:23 am

[Edited] I got it! and I am 3rd on the rank!

Post Reply

Return to “Volume 109 (10900-10999)”