208  Firetruck
Moderator: Board moderators

 Learning poster
 Posts: 53
 Joined: Sat Jul 29, 2006 7:33 am
 Location: (CSE,DU), Dhaka,Bangladesh
Re: 208 Why Time Limit Exceeded
I have no idea why it is TLE. Please try to help me. Here is my code
Code: Select all
/*
Problem No: 208
Problem : Firetruck
Algorithm: DFS
Author : Ishtiaq Ahmed
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define maximum(aa, bb) ((aa) > (bb) ? (aa) : (bb))
int destination;
int counting = 0;
bool array[1000][1000] = {false};
bool visited[1000] = {false};
int result[1000], indexx;
void DFS(int current, int max){
int i;
if(current == destination){
result[++indexx] = current;
for(i = 0; i <= indexx; i++){
if(indexx == i)
printf("%d\n", result[i]);
else
printf("%d ", result[i]);
}
counting++;
return;
}
result[++indexx] = current;
visited[current] = true;
for(i = 1; i <= max; i++){
if(array[current][i] == true && visited[i] == false){
DFS(i, max);
visited[i] = false;
indexx;
}
}
}
int main(){
//freopen("c:\\input.txt", "r", stdin);
//freopen("c:\\out.txt", "w", stdout);
int casno = 0, i, j, a, b;
int max = 99999;
while(scanf("%d", &destination) != EOF){
printf("CASE %d:\n", ++casno);
counting = 0;
indexx = 1;
for(i = 1; i <= max; i++)
for(j = 1; j <= max; j++)
array[i][j] = false;
for(i = 1; i <= max; i++)
visited[i] = false;
max = 9999999;
while(scanf("%d %d", &a, &b)){
if(!a && !b)
break;
array[a][b] = true;
array[b][a] = true;
max = maximum(max, a);
max = maximum(max, b);
}
DFS(1, max);
printf("There are %d routes from the firestation to streetcorner %d.\n", counting, destination);
}
return 0;
}
No venture no gain
with best regards

ishtiaq ahmed
with best regards

ishtiaq ahmed

 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
Re: 208 Why Time Limit Exceeded
Mr Ishtiaq try to realize if there are 10000 nodes and a node Ni may have only 1 adj node. Your program may search 10000 times to find the adj node though it is possible to find it in O(1).
Try to use List or vector in STL.
May it help u.
Try to use List or vector in STL.
May it help u.
http://www.newton.0fees.net is enough!
how Floyd can help backtracking?
Actually, I can not understand the idea of prunning backtracking with Floyd.
In backtracking, if I arrived to a node A from which the final node T is unreachable, still Floyd will give value
less than infinite, since from A I can reach T with some node I already used.
So, Floyd will not reject the specific node since with the matrix I will not be able to know the nodes I need to travel
from A to T.
Thanks in advance for any help
In backtracking, if I arrived to a node A from which the final node T is unreachable, still Floyd will give value
less than infinite, since from A I can reach T with some node I already used.
So, Floyd will not reject the specific node since with the matrix I will not be able to know the nodes I need to travel
from A to T.
Thanks in advance for any help
208 Firetruck WA
I use backtrack to get the path, and pruning the nodes that cannot get to the dest. But I always get WA, could anybody give me some critical I/O?
here is my code below:
here is my code below:
Code: Select all
removed after ACed.
Last edited by ryen on Wed Mar 03, 2010 1:32 pm, edited 1 time in total.
Re: 208 Firetruck WA
I've found the bug, and got Aced.
Re: how Floyd can help backtracking?
You're right assuming the graph is undirected. In reality it is undirected for every vertex except 1. However, I didn't take that into account and I still got accepted. My only guess is that they have a test case where 1 is part of a complete graph with 18 other nodes and the fire happens to be at the one node that is unreachable. I think my code would have timed out if they had connected that fire to the fire station since Floyd Warshall would compute a path from any vertex to the fire due to undirected pathsthales wrote:Actually, I can not understand the idea of prunning backtracking with Floyd.
In backtracking, if I arrived to a node A from which the final node T is unreachable, still Floyd will give value
less than infinite, since from A I can reach T with some node I already used.
So, Floyd will not reject the specific node since with the matrix I will not be able to know the nodes I need to travel
from A to T.
Thanks in advance for any help
Re: 208 Why Time Limit Exceeded
TLE:
All the above posts about TLE and how to optimize it.But I am still getting TLE in following code.Please Help anyone...
Finally Got Acc..I didn't notice sohel's stated tricks..thanks sohel nd also thanks goes to Sedefcho for his nice explanation...
All the above posts about TLE and how to optimize it.But I am still getting TLE in following code.Please Help anyone...
Code: Select all
Code Removed
Last edited by Imti on Sat Mar 12, 2011 1:39 pm, edited 2 times in total.
Re: 208 Why Time Limit Exceeded
Who are getting TLE
Just use floyedwarshall to check if it is possible to reach the destination via current streetcorner
if not then simply return else backtrack
Who are getting WA
Output must be in sorted order.
like >>
if there are two paths to 6
(1 5 3 6) and (1 4 2 3 6)
then output must be
Just use floyedwarshall to check if it is possible to reach the destination via current streetcorner
if not then simply return else backtrack
Who are getting WA
Output must be in sorted order.
like >>
if there are two paths to 6
(1 5 3 6) and (1 4 2 3 6)
then output must be
Code: Select all
1 4 2 3 6
1 5 3 6
There are 2 routes from the firestation to streetcorner 6.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 208 Why Time Limit Exceeded
Input:AC output:
Code: Select all
14
1 8
2 11
3 4
3 6
4 14
5 6
5 8
6 11
6 12
8 14
9 14
10 14
11 14
0 0
Code: Select all
CASE 1:
1 8 5 6 3 4 14
1 8 5 6 11 14
1 8 14
There are 3 routes from the firestation to streetcorner 14.
Check input and AC output for thousands of problems on uDebug!
Re: 208 Why Time Limit Exceeded
AC
Code: Select all
AC
Last edited by Scarecrow on Wed Feb 13, 2013 12:03 pm, edited 2 times in total.
Do or do not. There is no try.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 208 Why Time Limit Exceeded
Your output is not sorted correctly for the sample input.
Check input and AC output for thousands of problems on uDebug!
Re: 208 Why Time Limit Exceeded
Thanks Brianfry713! I thought any ordering of the routes would be fine as in the problem statement there's no mentioning of sorting the routes.
Do or do not. There is no try.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 208 Why Time Limit Exceeded
See:
http://uva.onlinejudge.org/index.php?op ... category=4
208 has a green check so there is only one acceptable output. Your code should match the sample I/O exactly. On the problems with a yellow check there is a special judge and it may accept multiple correct outputs.
http://uva.onlinejudge.org/index.php?op ... category=4
208 has a green check so there is only one acceptable output. Your code should match the sample I/O exactly. On the problems with a yellow check there is a special judge and it may accept multiple correct outputs.
Check input and AC output for thousands of problems on uDebug!