10985 - Rings'n'Ropes

polone · 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 · Post by mf » Tue Jan 24, 2006 4:52 pm

O(n^3) algo exists.

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

How the O(n^3) method work?

please tell me

I'm running crazy

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

A variation of floyd's.

Renat · 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?

Abednego · 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.

krijger · 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 · 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 · 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 · Post by **asif_rahman0** » Tue Aug 08, 2006 7:34 pm

Can someone explain me the algorithm here??
Or some hints from someone??

sclo · 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 · Post by **Moha** » Mon Aug 21, 2006 1:23 am

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