208

Jalal · Post by **Jalal** » Fri Dec 27, 2002 11:19 am

The same thing has dont to me
cant cross the prob:
TLE

/* @JUDGE_ID: XXXXX 208 C++ */
#include <stdio.h>

int TR;

void FR( int a,int n,int corner,int route[],int RM[22][22])
{
int i, j;

if (a == n)
{
TR++;

printf("%d", route[0]);
for (i=1; i < corner; i++)
{
printf("%4d", route);
}

printf("\n");
return;
}

for (i=0; i<22; i++)
{
if (RM[a])
{
for (j=0; j<corner; j++)
{
if(route[j] == i)
break;
}

if (j == corner)
{
route[corner] = i;

FR(i, n, corner+1,route, RM);
}
}
}
}

void main()
{
int x, y, n, c, route[22], RM[22][22];

for(c=1;scanf("%d", &n)==1;c++)
{
for (x=0; x<22; x++)
for (y=0; y<22; y++)
RM[x][y] = 0;

while (scanf("%d %d", &x, &y))
{
if(!x && !y)
break;

RM[x][y] = 1;
RM[y][x] = 1;

}

printf("CASE %d:\n", c);
route[0] = 1;
TR = 0;
FR(1, n, 1, route, RM);

printf("There are %d routes from the firestation ", TR);
printf("to streetcorner %d.\n", n);
}

}
/*@END_OF_SOURCE_CODE */

Larry · Post by **Larry** » Sat Dec 28, 2002 8:41 pm

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

I think this is enough if you actually bother to read the post..

LTH · Post by **LTH** » Sun Dec 29, 2002 2:55 pm

i didnt mean that i got TLE.
I have done what was discussed and I got a 0.002 sec WA....
i dont know why....

Jalal · Post by **Jalal** » Tue Jan 07, 2003 11:45 pm

Can any body give me some input and output for 208(firetruc)
problem?
thanx

efr_shovo · Post by **efr_shovo** » Sat Oct 02, 2004 6:54 am

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[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[j]=0;
i=1;
max=0;
while(Path!=0)
{
Path=0;
i++;
}
printf("There are %d routs from the firestation to streetcorner %d.\n",PathNum,FireCorner);
PathNum=0;
}
}

sohel · Post by **sohel** » Sat Oct 02, 2004 7:02 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.

efr_shovo · Post by **efr_shovo** » Wed Oct 06, 2004 12:29 pm

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

cytmike · Post by **cytmike** » Thu Mar 31, 2005 4:13 pm

LTH wrote:i didnt mean that i got TLE.
I have done what was discussed and I got a 0.002 sec WA....
i dont know why....

I also got WA. dunno why. Can anybody give some I/O?

cytmike · Post by **cytmike** » Thu Mar 31, 2005 4:47 pm

i got AC. stupid mistake

yiuyuho · Post by **yiuyuho** » Fri May 06, 2005 10:53 am

Hi Fellows,

Just for your information, there are some more test cases:

Input:

Code: Select all

output:

Code: Select all

CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.
CASE 3:
1 2 5 9 12 4 13 18 20
1 2 5 9 12 4 14 10 15 16 8 6 7 17 19 20
1 2 5 9 12 4 14 10 15 16 11 17 19 20
1 2 5 9 12 4 14 10 15 16 19 20
1 2 5 9 12 4 14 10 15 17 7 6 8 16 19 20
1 2 5 9 12 4 14 10 15 17 11 16 19 20
1 2 5 9 12 4 14 10 15 17 19 20
1 2 5 9 12 4 14 20
1 2 5 9 13 4 14 10 15 16 8 6 7 17 19 20
1 2 5 9 13 4 14 10 15 16 11 17 19 20
1 2 5 9 13 4 14 10 15 16 19 20
1 2 5 9 13 4 14 10 15 17 7 6 8 16 19 20
1 2 5 9 13 4 14 10 15 17 11 16 19 20
1 2 5 9 13 4 14 10 15 17 19 20
1 2 5 9 13 4 14 20
1 2 5 9 13 18 20
1 2 5 14 4 12 9 13 18 20
1 2 5 14 4 13 18 20
1 2 5 14 10 15 16 8 6 7 17 19 20
1 2 5 14 10 15 16 11 17 19 20
1 2 5 14 10 15 16 19 20
1 2 5 14 10 15 17 7 6 8 16 19 20
1 2 5 14 10 15 17 11 16 19 20
1 2 5 14 10 15 17 19 20
1 2 5 14 20
1 2 5 17 7 6 8 16 15 10 14 4 12 9 13 18 20
1 2 5 17 7 6 8 16 15 10 14 4 13 18 20
1 2 5 17 7 6 8 16 15 10 14 20
1 2 5 17 7 6 8 16 19 20
1 2 5 17 11 16 15 10 14 4 12 9 13 18 20
1 2 5 17 11 16 15 10 14 4 13 18 20
1 2 5 17 11 16 15 10 14 20
1 2 5 17 11 16 19 20
1 2 5 17 15 10 14 4 12 9 13 18 20
1 2 5 17 15 10 14 4 13 18 20
1 2 5 17 15 10 14 20
1 2 5 17 15 16 19 20
1 2 5 17 19 16 15 10 14 4 12 9 13 18 20
1 2 5 17 19 16 15 10 14 4 13 18 20
1 2 5 17 19 16 15 10 14 20
1 2 5 17 19 20
1 5 9 12 4 13 18 20
1 5 9 12 4 14 10 15 16 8 6 7 17 19 20
1 5 9 12 4 14 10 15 16 11 17 19 20
1 5 9 12 4 14 10 15 16 19 20
1 5 9 12 4 14 10 15 17 7 6 8 16 19 20
1 5 9 12 4 14 10 15 17 11 16 19 20
1 5 9 12 4 14 10 15 17 19 20
1 5 9 12 4 14 20
1 5 9 13 4 14 10 15 16 8 6 7 17 19 20
1 5 9 13 4 14 10 15 16 11 17 19 20
1 5 9 13 4 14 10 15 16 19 20
1 5 9 13 4 14 10 15 17 7 6 8 16 19 20
1 5 9 13 4 14 10 15 17 11 16 19 20
1 5 9 13 4 14 10 15 17 19 20
1 5 9 13 4 14 20
1 5 9 13 18 20
1 5 14 4 12 9 13 18 20
1 5 14 4 13 18 20
1 5 14 10 15 16 8 6 7 17 19 20
1 5 14 10 15 16 11 17 19 20
1 5 14 10 15 16 19 20
1 5 14 10 15 17 7 6 8 16 19 20
1 5 14 10 15 17 11 16 19 20
1 5 14 10 15 17 19 20
1 5 14 20
1 5 17 7 6 8 16 15 10 14 4 12 9 13 18 20
1 5 17 7 6 8 16 15 10 14 4 13 18 20
1 5 17 7 6 8 16 15 10 14 20
1 5 17 7 6 8 16 19 20
1 5 17 11 16 15 10 14 4 12 9 13 18 20
1 5 17 11 16 15 10 14 4 13 18 20
1 5 17 11 16 15 10 14 20
1 5 17 11 16 19 20
1 5 17 15 10 14 4 12 9 13 18 20
1 5 17 15 10 14 4 13 18 20
1 5 17 15 10 14 20
1 5 17 15 16 19 20
1 5 17 19 16 15 10 14 4 12 9 13 18 20
1 5 17 19 16 15 10 14 4 13 18 20
1 5 17 19 16 15 10 14 20
1 5 17 19 20
1 6 7 17 5 9 12 4 13 18 20
1 6 7 17 5 9 12 4 14 10 15 16 19 20
1 6 7 17 5 9 12 4 14 20
1 6 7 17 5 9 13 4 14 10 15 16 19 20
1 6 7 17 5 9 13 4 14 20
1 6 7 17 5 9 13 18 20
1 6 7 17 5 14 4 12 9 13 18 20
1 6 7 17 5 14 4 13 18 20
1 6 7 17 5 14 10 15 16 19 20
1 6 7 17 5 14 20
1 6 7 17 11 16 15 10 14 4 12 9 13 18 20
1 6 7 17 11 16 15 10 14 4 13 18 20
1 6 7 17 11 16 15 10 14 5 9 12 4 13 18 20
1 6 7 17 11 16 15 10 14 5 9 13 18 20
1 6 7 17 11 16 15 10 14 20
1 6 7 17 11 16 19 20
1 6 7 17 15 10 14 4 12 9 13 18 20
1 6 7 17 15 10 14 4 13 18 20
1 6 7 17 15 10 14 5 9 12 4 13 18 20
1 6 7 17 15 10 14 5 9 13 18 20
1 6 7 17 15 10 14 20
1 6 7 17 15 16 19 20
1 6 7 17 19 16 15 10 14 4 12 9 13 18 20
1 6 7 17 19 16 15 10 14 4 13 18 20
1 6 7 17 19 16 15 10 14 5 9 12 4 13 18 20
1 6 7 17 19 16 15 10 14 5 9 13 18 20
1 6 7 17 19 16 15 10 14 20
1 6 7 17 19 20
1 6 8 16 11 17 5 9 12 4 13 18 20
1 6 8 16 11 17 5 9 12 4 14 20
1 6 8 16 11 17 5 9 13 4 14 20
1 6 8 16 11 17 5 9 13 18 20
1 6 8 16 11 17 5 14 4 12 9 13 18 20
1 6 8 16 11 17 5 14 4 13 18 20
1 6 8 16 11 17 5 14 20
1 6 8 16 11 17 15 10 14 4 12 9 13 18 20
1 6 8 16 11 17 15 10 14 4 13 18 20
1 6 8 16 11 17 15 10 14 5 9 12 4 13 18 20
1 6 8 16 11 17 15 10 14 5 9 13 18 20
1 6 8 16 11 17 15 10 14 20
1 6 8 16 11 17 19 20
1 6 8 16 15 10 14 4 12 9 5 17 19 20
1 6 8 16 15 10 14 4 12 9 13 18 20
1 6 8 16 15 10 14 4 13 9 5 17 19 20
1 6 8 16 15 10 14 4 13 18 20
1 6 8 16 15 10 14 5 9 12 4 13 18 20
1 6 8 16 15 10 14 5 9 13 18 20
1 6 8 16 15 10 14 5 17 19 20
1 6 8 16 15 10 14 20
1 6 8 16 15 17 5 9 12 4 13 18 20
1 6 8 16 15 17 5 9 12 4 14 20
1 6 8 16 15 17 5 9 13 4 14 20
1 6 8 16 15 17 5 9 13 18 20
1 6 8 16 15 17 5 14 4 12 9 13 18 20
1 6 8 16 15 17 5 14 4 13 18 20
1 6 8 16 15 17 5 14 20
1 6 8 16 15 17 19 20
1 6 8 16 19 17 5 9 12 4 13 18 20
1 6 8 16 19 17 5 9 12 4 14 20
1 6 8 16 19 17 5 9 13 4 14 20
1 6 8 16 19 17 5 9 13 18 20
1 6 8 16 19 17 5 14 4 12 9 13 18 20
1 6 8 16 19 17 5 14 4 13 18 20
1 6 8 16 19 17 5 14 20
1 6 8 16 19 17 15 10 14 4 12 9 13 18 20
1 6 8 16 19 17 15 10 14 4 13 18 20
1 6 8 16 19 17 15 10 14 5 9 12 4 13 18 20
1 6 8 16 19 17 15 10 14 5 9 13 18 20
1 6 8 16 19 17 15 10 14 20
1 6 8 16 19 20
There are 152 routes from the firestation to streetcorner 20.
CASE 4:
1 2
There are 1 routes from the firestation to streetcorner 2.
CASE 5:
1 2 3 4
1 5 3 4
There are 2 routes from the firestation to streetcorner 4.

I found the test cases interesting because my AC program that ran in 0.004 sec on judge actually TLE on my computer (I waited too long I gave up, but its a lot more than 10 sec.). I posed them so you can check whether your program will pass TLE with these input.

I wrote another program that computes the result of the above input in about 8sec., and that one actually ran for 7 sec. (AC) on judge.

Sedefcho · Post by **Sedefcho** » Sun Aug 07, 2005 6:19 pm

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.

arbiter_tl · Post by **arbiter_tl** » Sat Jun 03, 2006 11:53 am

I get time limit exceed, but I'm sure that algorithm is quiet fast. I guess problem is in input section. Can anyone help plz? This is my first problem to be solved, and I don't know the input standarts for the Judge system

Code: Select all

#include <iostream.h>
#include <stdio.h>

struct {
  int taint;
  int adj[20];
  int nadj;
} corner[20];

int paths;
int path[20];
int npath;

void print_paths(int a, int b) {
  if (corner[a].taint) return;
  if (a==b) {
    for (int i=0; i<npath; i++)
      printf("%-4d", path[i]+1);
    printf("%d\n", b+1);
    paths++;
    return;
  }
  corner[a].taint = 1;
  path[npath++] = a;
  for (int i=0; i<corner[a].nadj; i++)
    print_paths(corner[a].adj[i], b);
  npath--;
  corner[a].taint = 0;
}

int main() {
  int dest, count=1;
  while (cin >> dest) {
    dest--;
    int i;
    for (i=0; i<20; i++) corner[i].taint = corner[i].nadj = 0;
    int a, b;
    while (cin >> a >> b && a && b) {
      a--, b--;
      corner[a].adj[corner[a].nadj++] = b;
      corner[b].adj[corner[b].nadj++] = a;
    }
    paths = npath = 0;
    cout << "CASE " << count++ << ":" << endl;
    print_paths(0, dest);
    if (paths == 1)
      cout << "There is 1 route from the firestation to streetcorner " <<
        dest+1 << "." << endl;
    else
      cout << "There are " << paths <<
        " routes from the firestation to streetcorner " << dest+1 << "." <<
        endl;
  }
  return 0;
}

arbiter_tl · Post by **arbiter_tl** » Sat Jun 03, 2006 11:54 am

http://acm.uva.es/p/v2/208.html - here is the link for the problem itself

dumb dan · Post by **dumb dan** » Sun Jun 04, 2006 10:13 am

If there is a thread about your problem, please use it.
This question has already been asked in this thread:
http://online-judge.uva.es/board/viewtopic.php?t=6581

i.kokan · Post by **i.kokan** » Fri Oct 06, 2006 2:06 am

Can someone tell me what's wrong with my solution? Thanks in advance.

Code: Select all

/* acm.uva.es */

#include <stdio.h>
#include <stdlib.h>

int N, length, was[21], array[21], list[21][21], poss[21], cnt;
unsigned long sol;

int cmp (const void *a, const void *b) {
  if (* (const int *) a > * (const int *) b)
    return 1;
  
  return -1;
}

void recursion (int id) {
  int i, remember_sol;
  
  array[++length] = id;
  was[id] = 1;
  
  if (id == N) {
    sol++;
    
    printf ("1");
    
    for (i = 2; i <= length; i++)
      printf (" %d", array[i]);
    
    printf ("\n");
  }
  else {
    remember_sol = sol;
    
    for (i = 1; i <= list[id][0]; i++)
      if (was[list[id][i]] == 0 && poss[list[id][i]] == 1)
        recursion (list[id][i]);
    
    if (remember_sol == sol)
      poss[id] = 0;
  }
  
  length--;
  was[id] = 0;
  
  return;
}

int main (void) {
  int a, b;
  
  while (scanf ("%d", &N) != EOF) {
    cnt++;
    length = sol = 0;
    
    for (a = 1; a <= 20; a++) {
      was[a] = 0;
      list[a][0] = 0;
      poss[a] = 1;
    }
    
    while (1) {
      scanf ("%d %d", &a, &b);
      
      if (a == 0 && b == 0)
        break;
      
      list[a][0]++;
      list[a][list[a][0]] = b;
      
      list[b][0]++;
      list[b][list[b][0]] = a;
    }
    
    for (a = 1; a <= 20; a++)
      qsort (&list[a][1], list[a][0], sizeof (int), cmp);
    
    printf ("CASE %d:\n", cnt);
    
    recursion (1);
    
    printf ("There are %lu routes from the firestation to streetcorner %d.\n", sol, N);
  }
  
  return 0;
}

OJ Board

208 - Firetruck

208 Why Time Limit Exceeded

Floyd-Warshall And Then Backtracking With Some Prunning

208 HELP PLZ

208 - WA