10681 - Teobaldo's Trip

[sohel]

Accepted.

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

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.

[tep]

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

[daveon]

Here is a tricky case.

INPUT:

Code: Select all

3 2
1 2
2 3
2 2 0

OUTPUT:

Code: Select all

Yes, Teobaldo can travel.

[Rocky]

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

Thank's In Advance
Rocky

[daveon]

Hi,

Check my previous post:

http://online-judge.uva.es/board/viewto ... ight=10681

[Rocky]

Thank's....

Rocky

[helloneo]

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

Code: Select all

code removed

[medv]

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

[asif_rahman0]

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][j] = map[days][j] | ( map[days][k]&map[days][k][j])

use IF condition for faster Running Time

[Darko]

I guess I don't understand this problem...
What would be the output for

Code: Select all

2 1
1 2
1 2 4

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

[mf]

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

[Shafaet_du]

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?

[pranon]

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]
Thanks in advance.

[mostafiz93]

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

[sdipu]

When you are solving this problem using matrix exponentiation, don't forget to use modulo operation.
Try this-

input:

Code: Select all

3 2
1 2
2 3
3 1 200

5 7
1 5
2 4
3 5
1 3
2 4
3 2
2 5
3 4 200

0 0

output:

Code: Select all

Yes, Teobaldo can travel.
Yes, Teobaldo can travel.