208 - Firetruck

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

Moderator: Board moderators

kjus
New poster
Posts: 3
Joined: Sun Oct 22, 2006 6:59 pm

Post by kjus » Fri Jul 06, 2007 9:44 pm

For those who have WA :
actually, the different paths must be output in lexicographic order.

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

Post by ishtiaq ahmed » Sun May 04, 2008 12:58 pm

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

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 208 Why Time Limit Exceeded

Post by newton » Sun Jul 06, 2008 11:52 pm

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.

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

how Floyd can help backtracking?

Post by thales » Tue Sep 30, 2008 3:54 pm

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

ryen
New poster
Posts: 5
Joined: Mon Feb 01, 2010 6:25 pm

208 Firetruck WA

Post by ryen » Wed Mar 03, 2010 12:01 pm

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:

Code: Select all

removed after ACed.
Last edited by ryen on Wed Mar 03, 2010 1:32 pm, edited 1 time in total.

ryen
New poster
Posts: 5
Joined: Mon Feb 01, 2010 6:25 pm

Re: 208 Firetruck WA

Post by ryen » Wed Mar 03, 2010 1:31 pm

I've found the bug, and got Aced.

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

Re: how Floyd can help backtracking?

Post by 4ndypanda » Sat Jun 19, 2010 1:47 am

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 :wink:

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 208 Why Time Limit Exceeded

Post by Imti » Sat Jan 22, 2011 12:03 pm

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... 8)
Last edited by Imti on Sat Mar 12, 2011 1:39 pm, edited 2 times in total.

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

thanks...

Post by Zippie72 » Tue Feb 01, 2011 6:31 pm

thanks, that helped me a lot!
regards,
chantal

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 208 Why Time Limit Exceeded

Post by @li_kuet » Fri Aug 17, 2012 11:25 pm

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 6
1 5 3 6
There are 2 routes from the firestation to streetcorner 6.

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

Re: 208 Why Time Limit Exceeded

Post by brianfry713 » Mon Sep 10, 2012 1:36 am

Input:

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
AC output:

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!

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

Re: 208 Why Time Limit Exceeded

Post by Scarecrow » Wed Feb 06, 2013 11:14 pm

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.

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

Re: 208 Why Time Limit Exceeded

Post by brianfry713 » Tue Feb 12, 2013 9:03 pm

Your output is not sorted correctly for the sample input.
Check input and AC output for thousands of problems on uDebug!

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

Re: 208 Why Time Limit Exceeded

Post by Scarecrow » Wed Feb 13, 2013 12:02 pm

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.

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

Re: 208 Why Time Limit Exceeded

Post by brianfry713 » Wed Feb 13, 2013 9:40 pm

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 2 (200-299)”