208 - Firetruck
Moderator: Board moderators
To Problem setter: Problem 208 Firetruck
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?
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?
-
- Learning poster
- Posts: 63
- Joined: Thu Apr 04, 2002 2:00 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.![:-?](./images/smilies/icon_confused.gif)
This is the "official" backtracking solution, which should make the output format clearer, but don't try it on Valladolid, it gets TLE.
![:-?](./images/smilies/icon_confused.gif)
-
- New poster
- Posts: 17
- Joined: Fri May 24, 2002 4:24 am
- Location: Taiwan
- Contact:
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
208 - Firetruck
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 ?
I use DFS in my solution, but got TLE .... Could anyone help me ?
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
-
- Experienced poster
- Posts: 151
- Joined: Wed Aug 21, 2002 12:07 am
- Location: Seoul, Korea
- Contact:
Wow!
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![:)](./images/smilies/icon_smile.gif)
Learned a lot from this problem. Thanks!
2
1 2
1 3
1 4
..
1 20
.. and nodes from 3 to 20 form a completed graph. Huh
![:)](./images/smilies/icon_smile.gif)
Learned a lot from this problem. Thanks!
JongMan @ Yonsei
1... if you use link list... you should sort it firstxenon 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?
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.
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]
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]