11838 - Come and Go

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

Moderator: Board moderators

User avatar
sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

11838 - Come and Go

Post by sitz » Mon Sep 20, 2010 1:40 am

Hi All !
I was trying this question from the Brazilian Contest. Though, it seems to be standard Floyd-Warshall Algorithm, I was using simpler queue implementation.
I think my approach is correct, but, getting TLE :( Any reasons for TLE in this code :

Code: Select all

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;

using namespace std;

int main(){
    while(true){
                int N, test;
                int i, j, k;
                cin>>N>>test;
                if(N==0 && test==0)
                        break;
                bool mat[N][N];
                memset( mat, false, sizeof(bool)*N*N );
                while(test--){
                              int X, Y, ctr;
                              cin>>X>>Y>>ctr;
                              if(ctr == 1)
                                     mat[X-1][Y-1] = true;
                              else{
                                   mat[X-1][Y-1] = true;
                                   mat[Y-1][X-1] = true;
                              }
                }
                for(i=0; i<N; i++){
                         queue<int> que;
                         bool stat[N][N];
                         memset( stat, false, sizeof(bool)*N*N );
                         for(j=0; j<N; j++){
                                  if(mat[i][j] && !stat[i][j] && i!=j){
                                               que.push(j);
                                               stat[i][j]=true;
                                  }
                         }
                         while(!que.empty()){
                                           int ind = que.front();
                                           mat[i][ind] = true;
                                           for(j=0; j<N; j++){
                                                    if(mat[ind][j] && !stat[ind][j] && ind!=j){
                                                                   que.push(j);
                                                                   stat[ind][j]=true;
                                                    }
                                           }
                                           que.pop();
                         }
                }
                int cnt=0;
                for(i=0; i<N; i++)
                         for(j=0; j<N; j++)
                                  cnt+=mat[i][j];
                if(cnt == N*N)
                       cout<<"1\n";
                else
                    cout<<"0\n";
    }
    return 0;
}
Thanx in advance :)

Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

Re: 11838 - Come And Go

Post by Khongor_SMCS » Mon Sep 20, 2010 4:07 am

Problem is asking the given directed graph is connected or not.
You can solve it using Tarjan's algorithm.

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

Re: 11838 - Come And Go

Post by pdwd » Mon Sep 20, 2010 9:02 pm

You can use dfs to find strongly connected components and check if there is only 1 such component.

User avatar
sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

Re: 11838 - Come And Go

Post by sitz » Mon Sep 20, 2010 9:08 pm

As I told before... I know that it can be solved by standard graph algorithm and, I have done it too with "Floyd-Warshall" Algorithm.
But, can anyone tell me is it possible to do the same by QUEUE implementation as in my above code ?

And if yes, then where is the problem in my code... It gives TLE when submitted.. though complexity seems to be the same as "Floyd-Warshall" :o

krien
New poster
Posts: 5
Joined: Mon Sep 20, 2010 12:51 pm

Re: 11838 - Come And Go

Post by krien » Mon Sep 20, 2010 9:49 pm

The main problem of floyd-warshall is the complexity of the algorithm O(n^3) while using a bfs or dfs per node the complexity is O(n^2).
I hope that will help you.

wazaaaap
New poster
Posts: 7
Joined: Thu Sep 23, 2010 12:55 am

Re: 11838 - Come And Go

Post by wazaaaap » Thu Sep 23, 2010 1:02 am

Run DFS from each node, after each run, check if you have visited all the nodes, if yes, tmp++ and at the end, if tmp == n print YES otherwise NO.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11838 - Come And Go

Post by saiful_sust » Thu Sep 23, 2010 12:20 pm

it's a easy problem..
It can be solve with standard SCC algorithm :D
  • IMPOSSIBLE MEANS I M POSSIBLE

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11838 - Come And Go

Post by Shafaet_du » Tue Sep 28, 2010 9:15 pm

sample I/O;

Code: Select all

3 3
1 2 2
1 3 1
2 3 1
5 7
1 5 2
1 2 2
2 5 1
2 4 1
5 3 1
3 4 1
2 3 1
5 7
1 5 2
1 2 2
2 5 1
2 4 1
5 3 2
3 4 2
2 3 1
0 0
output from my ac code:

Code: Select all

0
0
1

User avatar
sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

Re: 11838 - Come And Go

Post by sitz » Tue Sep 28, 2010 11:50 pm

@Shafeet_du : My TLE code (given above) aslo gives the same outputs...
But, can we do it the way I have done it ? Or, not ?

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11838 - Come And Go

Post by Igor9669 » Fri Oct 01, 2010 2:14 pm

Certanly you will get TLE on this problem with Floyd!

It could be solve with simple dfs or bfs with little modification!

User avatar
sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

Re: 11838 - Come And Go

Post by sitz » Fri Oct 01, 2010 2:20 pm

Hi Igor9669 !
But, I don't understand how people can't understand the simple question that I have posted here :(
I said I have got Accepted with a time of around 0.338 s using Floyd-Warshall Algorithm...

I just wanted to ask if the above implementation using queues can be optomized to get Ac or its not possible at all

PS-1 : Above code is different than that with which I got Accepted...
PS-2 : Floyd Warshall doesn't give TLE at all :o

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11838 - Come And Go

Post by Igor9669 » Fri Oct 01, 2010 2:44 pm

I couldn't belive that Floyd could get Ac here....
it complexity O(n^3), where n=2000, how it could be pass at 2 sec???

User avatar
sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

Re: 11838 - Come And Go

Post by sitz » Fri Oct 01, 2010 2:48 pm

Well, I thought the same way, but, actually it did pass :o
For ur belief you can check the verdict of judge here : http://felix-halim.net/uva/hunting.php? ... hrivastava

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11838 - Come And Go

Post by Igor9669 » Fri Oct 01, 2010 2:58 pm

May be bad tests there....((
Or you make a mistake in complexity of your algo...
Your implementation with queue got TLE,because it's O(N^3)!

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11838 - Come And Go

Post by Shafaet_du » Sat Oct 02, 2010 6:29 pm

Floyd should get TLE with a good data set.

Post Reply

Return to “Volume 118 (11800-11899)”