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

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

To Problem setter: Problem 208 Firetruck

Post by 10153EN » Wed Jun 12, 2002 7:30 pm

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?

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Thu Jun 13, 2002 1:40 am

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. :-?

Shih-Chia Cheng
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:

Post by Shih-Chia Cheng » Thu Jun 13, 2002 9:27 am

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... :-? ?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Jun 13, 2002 10:11 am

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.

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Thu Jun 13, 2002 5:23 pm

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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

208 - Firetruck

Post by Dominik Michniewski » Thu Jul 11, 2002 8:08 am

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 ?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Jul 11, 2002 9:05 am

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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Jul 11, 2002 10:09 am

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

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » Thu Jul 11, 2002 10:19 am

BTW: Firetruck is #208 :-?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Jul 11, 2002 11:38 am

Xenon, you have absolutely right !!
I must be tired at morning, when I post this message .... to hot for me (and my comp too ... ) :-)

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » Thu Jul 11, 2002 11:49 am

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?

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Wow!

Post by Whinii F. » Wed Aug 21, 2002 12:11 am

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!
JongMan @ Yonsei

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Wed Aug 21, 2002 3:15 am

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...
Time makes a fool of memory
And yet my memories still shine

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Mon Sep 23, 2002 2:20 pm

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.

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:

Post by LTH » Thu Dec 26, 2002 6:09 pm

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]

Post Reply

Return to “Volume 2 (200-299)”