## 208 Why Time Limit Exceeded

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

Moderator: Board moderators

### 208 Why Time Limit Exceeded

208 Gives Me TLE.Please Help me.

This is My code

#include<stdio.h>

int FireCorner;
int StreetCornerS=1,StreetCornerD=1;
int AdjMat[100][100];
int Path[1000];
int mutex,mutex1;
int max=0,i,j,PathNum;

void DFS(int u,int z)
{
int k=0;

Path[z]=u;
z++;
for(int j=1;j<=max;j++)
{
if(u==FireCorner)
break;
if(AdjMat[u][j]!=0)
{
mutex=0;
for(k=1;k<z;k++)
{
if(Path[k]==j)
{
mutex=1;
break;
}
}
if(mutex!=1)
{
mutex1=1;
DFS(j,z);
}
}
}
if(mutex1==1&&Path[z-1]==FireCorner)
{
PathNum++;
for(int k1=1;k1<z;k1++)
printf("%d ",Path[k1]);
printf("\n");
}
}

void main()
{

int cas=0;
while(1==scanf("%d",&FireCorner))
{ cas++;
if(FireCorner<=0||FireCorner>=21)
break;
while(StreetCornerS!=0&&StreetCornerD!=0)
{
scanf("%d %d",&StreetCornerS,&StreetCornerD);
AdjMat[StreetCornerS][StreetCornerD]=1;
AdjMat[StreetCornerD][StreetCornerS]=1;
if(max<StreetCornerS)
max=StreetCornerS;
if(max<StreetCornerD)
max=StreetCornerD;
}
printf("CASE %d:\n",cas);
DFS(1,1);
StreetCornerS=1;
StreetCornerD=1;
for(i=1;i<=max;i++)
for(j=1;j<=max;j++)
AdjMat[i][j]=0;
i=1;
max=0;
while(Path[i]!=0)
{
Path[i]=0;
i++;
}
printf("There are %d routs from the firestation to streetcorner %d.\n",PathNum,FireCorner);
PathNum=0;
}
}
efr_shovo
New poster

Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

I haven't gone through your code thoroughly, but from what it looks, I think you are just running a plain dfs() and it is likely to get TLE..

... You can prune at certain nodes once you know that going through that node will not lead you to the destination.

.. I used FW to find those nodes and then applied DFS() and it passed TL.

Hope it helps.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

How Can you use FW .Cozz.. There is No Weight. And What Is Prune.

Please Describe the Sentence That you say-----"... You can prune at certain nodes once you know that going through that node will not lead you to the destination."
efr_shovo
New poster

Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

### Floyd-Warshall And Then Backtracking With Some Prunning

Efr_shovo,

Have you already got ACC on problem 208 ?
I am asking because I can see your last post in this
thread is quite old.

If you haven't solved it yet - here are the answers
of your questions.

1) Use Floyd-Warshall by first defining some weights yourself.
In case there's an edge between two nodes n1 and n2 just
define weight[n1][n2] = weight[n2][n1] = 1.
If no edge exists between n1 and n2 just define
weight[n1][n2] = weight[n2][n1] = INFINITE
( INFINITE could be some constant like -1000000 for example,
but the exact value of this constant is not important ).

2) Prunning means that when we do some backtracking procedure
we just do not follow certain subtrees in the backtracking recursion
tree. We call this prunning the backtracking tree or just prunning.
In our case we should do it as follows. Say our route ( path )
has started at node 1. And say also that we have just reached node N.
Say also that our target node is T. So ... our current node is N.
Well, then in our backtracking procedure the first thing we should do
is to check if dist[N][T]==INFINITE. If so then it makes no sense
to continue with that branch ( subtree ) of our backtracking
procedure as we know for sure that there is no route(path)
from N to T. Here by dist[][] I have denoted the distance
matrix which has been initialized with correct values by
the Floyd-Warshall algorithm. If dist[n1][n2]==INFINITE after
we have applied the Floyd-Warshall algorithm this means there's
no route(path) in the graph between the nodes n1 and n2.

Hope this will help you or at least someone else who
is still working on this problem.

I can see it has been solved till now by just 440 people. And it
is not so difficult actually, if we follow the idea which Sohel
has posted above.

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### 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
ishtiaq ahmed
Learning poster

Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

### 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.

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh

### 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
thales
New poster

Posts: 2
Joined: Sat Sep 20, 2008 11:44 pm

### Re: how Floyd can help backtracking?

thales 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

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 paths
4ndypanda
New poster

Posts: 2
Joined: Wed May 26, 2010 4:25 am

### 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...
Code: Select all
`Code Removed`

Finally Got Acc..I didn't notice sohel's stated tricks..thanks sohel nd also thanks goes to Sedefcho for his nice explanation...
Last edited by Imti on Sat Mar 12, 2011 1:39 pm, edited 2 times in total.
Imti
Learning poster

Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh

### thanks...

thanks, that helped me a lot!
regards,
chantal
Zippie72
New poster

Posts: 1
Joined: Tue Feb 01, 2011 6:30 pm
Location: Germany Nortrhine-Westfalia

### Re: 208 Why Time Limit Exceeded

Who are getting TLE
Just use floyed-warshall 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 61 5 3 6There are 2 routes from the firestation to streetcorner 6.`
@li_kuet
New poster

Posts: 24
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

### Re: 208 Why Time Limit Exceeded

Input:
Code: Select all
`141 82 113 43 64 145 65 86 116 128 149 1410 1411 140 0`
AC output:
Code: Select all
`CASE 1:1 8 5 6 3 4 141 8 5 6 11 141 8 14There are 3 routes from the firestation to streetcorner 14.`
brianfry713
Guru

Posts: 1742
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### 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.
Scarecrow
Learning poster

Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 208 Why Time Limit Exceeded

Your output is not sorted correctly for the sample input.
brianfry713
Guru

Posts: 1742
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### 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.
Scarecrow
Learning poster

Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Next

Return to Volume II

### Who is online

Users browsing this forum: No registered users and 1 guest