## 11090 - Going in Cycle!!

Moderator: Board moderators

### 11090 - Going in Cycle!!

Can this problem be done in O(n^3)?
My AC solution is O(n^4) in the worse case. More precisely, my solution is O(mn^2)
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

A bit faster algorithm exists.
There is a way to check for some mean M if there is a cycle with mean at least M in O(n*m). So you can do a binary search on the mean to find the result.
kalinov
New poster

Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

I never thought about using binary search here, thanks for the idea.
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

FAQ
Learning poster

Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

There exist "many" O(mn) algorithms for this problem. See http://citeseer.ist.psu.edu/dasdan98experimental.html

Learning poster

Posts: 66
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz

It also can be solved using binary search + Floyd.
kp
Learning poster

Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Be sure you handle cases with muliple edges from a to b correctly.

Test:

1
3 5
1 2 1
2 3 5
3 1 1
3 1 5
2 3 1

Case #1: 1.00
kp
Learning poster

Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

I got AC !! Thanks kp
FAQ
Learning poster

Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Hadi wrote:There exist "many" O(mn) algorithms for this problem. See http://citeseer.ist.psu.edu/dasdan98experimental.html

I followed the link but couldn't get to any implementation (or pseudo code) for any of them, can you help with a link to the steps or implementation of any of these algorithms?
cpphamza
New poster

Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

kp wrote:It also can be solved using binary search + Floyd.

I think you binary search for the mean value, but can you explain how you use floyd warshall to test if a cycle with this mean (or less) exists?
cpphamza
New poster

Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

1. To get an idea how to do the binary-search approach, see http://www.topcoder.com/stat?c=problem_ ... 50&rd=9984 and its editorial at http://www.topcoder.com/tc?module=Stati ... s_analysis

2. There are some pseudo-codes at the end of that article

Learning poster

Posts: 66
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz

cpphamza wrote:I think you binary search for the mean value, but can you explain how you use floyd warshall to test if a cycle with this mean (or less) exists?

Learning poster

Posts: 66
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz

Thanks alot, I tried to solve the prob using the pseudo code for karp's algorithm but got WA, the only different thing i changed from the pseudo code is replacing max by min in line 12 of the pseudo code (I suspect this is a mistake in the pseudo code).

here is my program
Code: Select all
`#include<iostream>using namespace std;int INF = 100000000;const int MAX = 50;int weight[MAX][MAX];int n, m;double min(double x, double y){   return x < y ? x : y;}double max(double x, double y){   return x > y ? x : y;}int d[MAX+1][MAX];double MMC(){      //Initialize   int k, u, v, s = 0;   for(k = 0 ; k <= n ; k++)      for(u = 0 ; u < n ; u++)         d[k][u] = INF;   d[0][s] = 0;   //Compute the distances   for(k = 1 ; k <= n ; k++)      for(v = 0 ; v < n ; v++)         for(u = 0 ; u < n ; u++)            if(weight[u][v] < INF)               d[k][v] = min(d[k][v], d[k-1][u]+weight[u][v]);   //Compute lamda using karp's theorem   double lamda = INF;   for(u = 0 ; u < n ; u++){      double currentLamda = INF;      for(int k = 0 ; k < n ; k++)         if(d[n][u] < INF && d[k][u] < INF)            currentLamda = min(currentLamda, 1.0*(d[n][u]-d[k][u])/(n-k) );            lamda = min(lamda, currentLamda);   }         return lamda;}int main(){   freopen("1.in", "r", stdin);   int tt; cin >> tt;   for(int t = 0 ;  t < tt ; t++){      cin >> n >> m;      int i;      for(i = 0 ; i < n ; i++)         for(int j = 0 ; j < n ; j++)            weight[i][j] = INF;      for(i = 0 ; i < m ; i++){         int l, r, c;         cin >> l >>r >> c;         weight[l-1][r-1] = min(c,weight[l-1][r-1]);      }      cout << "Case #" << t+1 << ": ";      double l = MMC();      if(l < INF){         cout.setf(ios::fixed);         cout.setf(ios::showpoint);         cout.precision(2);         cout << l;      }      else         cout << "No cycle found.";      cout << endl;   }   return 0;}`

it also fails a testcase like this,
1
3 4
1 2 2
2 3 4
3 1 6
1 3 6

any ideas?
cpphamza
New poster

Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

I haven't implemented the code myself, but I guess I know what's your mistake. You should note that the input to Karp's algorithm is a "strongly connected directed graph" not a "general directed graph". This means that there should be a path from every vertex u to every vertex v in the graph.

To use it for a general graph, first step is detecting the strongly connected components which can be done using 2 dfs's in O(v+e). Then run the algorithm for each of the strongly connected components. If you don't know the algorithm for detecting Strongly Connected Components, tell.

I hope this can help ...

Learning poster

Posts: 66
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz

Thanks alot it helped very much, I got AC after getting over a couple of things,

1- The Karp's pseudo code in the paper has a mistake in line 10, we should set lamda to a small value instead of INF.

2- I've applied Kosaraju's Algorithm for SCC as you've advised.

by the way do you know if these algorithms has extensions to cases more than finding a cycle, for example can we use them for solving the TopCoder problem you posted a link to?

also are these algorithms applied to find the maximum mean cycle?
cpphamza
New poster

Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Next