## 10681 - Teobaldo's Trip

Moderator: Board moderators

Accepted.

I modified my bfs() and got it AC in 0.04 seconds.

Larry wrote:Use dynamic programming by first finding a recurrence..

Can someone give some detail about this recurrence relation. I think most of the people used Larry's method.

I also saw many people taking a considerable time to solve this problem. So is there any method other than exhaustive BFS().

sohel
Guru

Posts: 865
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

I use memoization / dp approach. Here is some clue

memo[v][d]
can i reach the destination if i'm vertex no v and i have d days left.

I'm sure you can figure out the rest

regards,
stephanus
tep
New poster

Posts: 23
Joined: Fri Jun 13, 2003 6:08 am

### 10681 Teobaldo's Trip

Here is a tricky case.

INPUT:
Code: Select all
`3 21 22 32 2 0`

OUTPUT:
Code: Select all
`Yes, Teobaldo can travel.`
daveon
Experienced poster

Posts: 229
Joined: Tue Aug 31, 2004 2:41 am

### 10681 Problem..

I Get WA For This Problem....
Can Any One Give Me Some Tricky Case.....

Rocky

Rocky
Experienced poster

Posts: 124
Joined: Thu Oct 14, 2004 9:05 am

daveon
Experienced poster

Posts: 229
Joined: Tue Aug 31, 2004 2:41 am

### Thank's..

Thank's....

Rocky

Rocky
Experienced poster

Posts: 124
Joined: Thu Oct 14, 2004 9:05 am

### 10681 Teobaldo's Trip again.. Tell me what's wrong..!!

if Teobaldo can go j city on i-th day, i check dp[j][i] = i
it's kind of straightforward.. but getting WA..
plz tell me what's wrong..

Code: Select all
`code removed`
Last edited by helloneo on Sun Aug 06, 2006 7:43 am, edited 1 time in total.
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Try this input

Try this input:

2 1
1 2
1 2 3

your program gives NO, but must be YES.
The trip is: 1 - 2 - 1 - 2
medv
Learning poster

Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

i m not expert in DP
so i think u can use easily matrix multiplication for finding link between vertices. which is O(n^3).
then use another loop for days....then it would be O(n^4) by some extra checking. get it aceepted within 1.4/1.3

hope it helpssssssss.

N.B: dont use map[days][i][j] = map[days][i][j] | ( map[days][i][k]&map[days][k][j])

use IF condition for faster Running Time
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

I guess I don't understand this problem...
What would be the output for
Code: Select all
`2 11 21 2 4`

I think it's "No", because he can't make that trip in exactly 4 days?
Darko
Guru

Posts: 572
Joined: Fri Nov 11, 2005 9:34 am

That's right. Output is "No" if and only if there is no trip of length exactly D days.
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

### Re: 10681 - Teobaldo's Trip

I solved using dp but i am interested to know the matrix exponent solution. I am failing to raise the power to 200 as the elements are becoming too large. Do we need to use some kind of modular arithmetic?
Shafaet_du
Experienced poster

Posts: 147
Joined: Mon Jun 07, 2010 11:43 am

### Re: 10681 - Teobaldo's Trip

Code being judged ``WA" with me having no idea why. Any help in pointing out would be much appreciated.
Code: Select all
`[code]#include <stdio.h>#include <string.h>char mat[105][105], adj[105][105], temp[105][105], city[105];char ytic[100000];int main(){    int c, l, j, i, a, b, s, e, d, t, k;    while(scanf("%d %d", &c, &l)==2 && (c || l))    {        j=0;        while(l--)        {            scanf("%d %d", &a, &b);            if(ytic[a]==0)            {                city[j]=a;                ytic[a]=j++;            }            if(ytic[b]==0)            {                city[j]=b;                ytic[b]=j++;            }            adj[ytic[a]][ytic[b]]=adj[ytic[b]][ytic[a]]=mat[ytic[a]][ytic[b]]=mat[ytic[b]][ytic[a]]=1;        }        scanf("%d %d %d", &s, &e, &d);        t=1;        s=ytic[s];        e=ytic[e];        while((t<<1)<=d)        {            for(i=0; i<c; i++)                for(j=0; j<c; j++)                    for(k=0; k<c; k++)                        if(mat[i][k]>0 && mat[k][j]>0)                            temp[i][j]=1;            for(i=0; i<c; i++)                for(j=0; j<c; j++)                    mat[i][j]=temp[i][j];            t<<=1;        }        while(t<d)        {            for(i=0; i<c; i++)                for(j=0; j<c; j++)                    for(k=0; k<c; k++)                        if(mat[i][k]>0 && adj[k][j]>0)                            temp[i][j]=1;            for(i=0; i<c; i++)                for(j=0; j<c; j++)                    mat[i][j]=temp[i][j];            t++;        }        (mat[s][e]>0 ||(s==e && d==0))?printf("Yes, Teobaldo can travel.\n"):printf("No, Teobaldo can not travel.\n");        for(i=0; i<c; i++)        {            memset(mat[i], 0, c*sizeof(char));            memset(adj[i], 0, c*sizeof(char));        }        memset(city, 0, c*sizeof(char));    }    return 0;}[/code]`

pranon
New poster

Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

### Re: 10681 - Teobaldo's Trip

I'm getting WA in this problem.

My algo is : first make adjacency matrix with the given liunks. then journey is possible if [adj matrix]^d is nonzero.

i've implemented this with matrix exponentiation.

Can anybody help me?

my code is here:
Code: Select all
`removed after AC`
mostafiz93
New poster

Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Previous