Page 1 of 4

To Problem setter: Problem 208 Firetruck

Posted: Wed Jun 12, 2002 7:30 pm
by 10153EN
I feel exhausted about this problem. I am quite sure I have implemented a correct algorithm to this problem, which handled all cases, at least for those I thought of.

Could the problem setter give me a clear image on the problem description? Since the problem description is not clear enough, for example how to handle some special cases.
1. What if the nearest corner is #1, i.e. the firestation? Should I output 1 route or 0 route?
2. What's the output format in detail? Are the numbers of width 4? Should I obmit the 's' when there's only 1 route?

Posted: Thu Jun 13, 2002 1:40 am
by Christian Schuster
http://www.acm.inf.ethz.ch/ProblemSetAr ... 1/acm91a.c

This is the "official" backtracking solution, which should make the output format clearer, but don't try it on Valladolid, it gets TLE. :-?

Posted: Thu Jun 13, 2002 9:27 am
by Shih-Chia Cheng
I feel confused with this problem, too.
I don't know why I always get TLE.......
Since we need to enumerate all possible paths. Can we come up with a better solution than backtracking?
So many doyens tried to solve this problem, but in vain.
Is there anything wrong with input or output... :-? ?

Posted: Thu Jun 13, 2002 10:11 am
by Adrian Kuegel
I can't think of a solution without backtracking, but perhaps one can find some break conditions to avoid trying a path which does not lead to the fire.
I think the "official" solution is not very good, at least my solution is faster, and I get TLE, too.

Posted: Thu Jun 13, 2002 5:23 pm
by wyvmak
ans to 10153EN:
1. if the nearest corner is #1, only 1 route, ie. "1"
2. i output "1 routes". but i get P.E. and seems all justified with width 4 cannot get me AC.

208 - Firetruck

Posted: Thu Jul 11, 2002 8:08 am
by Dominik Michniewski
Does anyone know faster method than simple DFS to solve this problem ?
I use DFS in my solution, but got TLE .... Could anyone help me ?

Posted: Thu Jul 11, 2002 9:05 am
by Adrian Kuegel
Try to avoid using edges that does not lead to the destination. Use only edges that you have not used or that lead to a street corner from wich a path is known.

Posted: Thu Jul 11, 2002 10:09 am
by Dominik Michniewski
That means, that I could use kind of DP algorithm ? not full DFS ?

Thanks Adrian .... i try to change my code later ;-) now I must working ...

Posted: Thu Jul 11, 2002 10:19 am
by xenon
BTW: Firetruck is #208 :-?

Posted: Thu Jul 11, 2002 11:38 am
by Dominik Michniewski
Xenon, you have absolutely right !!
I must be tired at morning, when I post this message .... to hot for me (and my comp too ... ) :-)

Posted: Thu Jul 11, 2002 11:49 am
by xenon
No problem :)
I had a long standing TLE on this problem too. Adrian's hints made me look at the code again, and make some adjustments.
Now I have WA in 0.000 seconds! So obviously the code is bad in some cases, although it still solves the examples.
Any tips?

Wow!

Posted: Wed Aug 21, 2002 12:11 am
by Whinii F.
Adrian's idea is absolutely COOL! Never thought about that and was wondering why would I get a TLE.. so, the judging data should include one like:
2
1 2
1 3
1 4
..
1 20

.. and nodes from 3 to 20 form a completed graph. Huh :)
Learned a lot from this problem. Thanks!

Posted: Wed Aug 21, 2002 3:15 am
by obayashi
i got TLE too with this problem at first. my friend gave me some hints.
first, use floyd or warshall to determine whether the node is reachable to the destination while using dfs... then i got AC...

Posted: Mon Sep 23, 2002 2:20 pm
by Even
xenon wrote:No problem :)
I had a long standing TLE on this problem too. Adrian's hints made me look at the code again, and make some adjustments.
Now I have WA in 0.000 seconds! So obviously the code is bad in some cases, although it still solves the examples.
Any tips?
1... if you use link list... you should sort it first
2... if input like

1
2 3
2 4
3 3
0 0

output is

1
There are 1 routes from the firestation to streetcorner 1.

Posted: Thu Dec 26, 2002 6:09 pm
by LTH
I have done what u had said and i still cant past the judge....
can anyone give me more special cases?? Thanks

The following is my code(i will appreciate very much if u can point out my mistakes):

[cpp]
#include <stdio.h>
#include <stdlib.h>
#define MAX 22


int i,j,k,t,m,cnt,tar,num,count,a,b,tmp,map[MAX][MAX],n[MAX],p[MAX][MAX],ans[MAX];
int next[MAX][MAX],nu[MAX];
bool used[MAX],l,d[MAX];

void dfs2(int x)
{
int e,f;
used[x]=1;
ans[tmp++]=x;
if(x==tar)
{
for(e=0;e<tmp;e++)
{
if(e>0)
printf(" ");
printf("%d",ans[e]);
}
printf("\n");
tmp--;
used[x]=0;
count++;
return ;
}
for(e=0;e<nu[x];e++)
{
if(!used[next[x][e]])
dfs2(next[x][e]);
}
tmp--;
used[x]=0;
}

void dfs(int x)
{
int e,f,g;
used[x]=1;
if(x==1)
{
used[x]=0;
return;
}
for(e=0;e<n[x];e++)
{
if(!used[p[x][e]])
{
for(f=0,g=0;f<nu[p[x][e]];f++)
{
if(next[p[x][e]][f]==x)
{
g=1;
break;
}
}
if(g==0)
{
next[p[x][e]][nu[p[x][e]]++]=x;
dfs(p[x][e]);
}
}
}
used[x]=0;
}

int presort(const void *m1, const void *m2)
{
return *((int*)m1)-*((int*)m2);
}

void main()
{
cnt=0;
while(scanf("%d",&tar)!=EOF)
{
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
map[j]=0;
for(i=1;i<MAX;i++)
map=1,used=0,nu=0,d=0,n=0;
while(1)
{
scanf("%d %d",&a,&b);
if(a==0&&b==0)
break;
map[a]=1,map[a]=1;
}
d[1]=1;
for(i=1;i<MAX;i++)
{
for(j=1,t=0;j<MAX;j++)
{
if(d[j]&&!used[j])
{
t=j;
break;
}
}
used[t]=1;
for(j=1;j<MAX;j++)
if(map[t][j])
d[j]=1,p[j][n[j]++]=t;
}
for(i=1;i<MAX;i++)
used=0;
printf("CASE %d:\n",++cnt);
count=0,tmp=0;
dfs(tar);
for(i=1;i<MAX;i++)
if(nu>0)
qsort(next,nu[i],sizeof(int),presort);
dfs2(1);
printf("There are %d routes from the firestation to streetcorner %d.\n",count,tar);
}
}
[/cpp]