125 - Numbering Paths

[Eduard]

help please i whant to know doesn't this problem solved whith the multipling of matrixes n time or i must do something like Floids algoritm.
thanks.

[svelasqu]

the problem doesnt say how many intersections you have, so you need to find the biggest name. If it says 1 5 2 3, for instance, intersections are 0, 1, 2, 3, 4, 5. I recommend you using DFS, i tried with floyd-warsshall and I messed up, seems to be cases that doesnt handle it. I used floyd-warsshall after that, from cycles, to find out infinite paths.

[Almost Human]

Thank you svelasqu for your explanation. I have got AC ...

[sohel]

I first applied F. Warshall's Algorithm to find the total number of ways.
And then applied another one to test for cycles. But I am getting WA.

This function generates the sum;
[cpp]
for(k=0;k<max;k++)
for(i=0;i<max;i++)
for(j=0;j<max;j++)
{
d[j] += d[k]*d[k][j];
}
[/cpp]

And this one finds cycle.
[cpp]
for(i=0;i<max;i++)
for(j=0;j<max;j++)
for(k=0;k<max;k++)
{
if( d[j] && d && d[k])
d[j][k] = -1;
}
[/cpp]

Is my method wrong?

[kamrul]

I used DFS to find the nodes which are in the cycle and marked them
with -1. Then used F. Warshall to find the path matrix .

Could you explain the following code what you are doing here.

Code: Select all

        if( d[j][i] && d[i][i] && d[i][k])
              d[j][k] = -1;

Thanks.

[40366]

if A is the adjacency matrix



summation from i = 1 to n-1(A ^ i) gives me the no of walk bet any two vert of len <= n-1



similarly i do upto 2(n-1) and see if the no has increased if it has then the no of paths is inf else the no of paths bet x and y is the entry[x][y] in the summed matrix



but i get WA



by the way i dont know how to include my code in this[/code][/cpp][/c]

[junbin]

infinite does not necessary mean up to 2(n-1)...

a much better way to test for infinite paths is to check if path[x][x] is valid. If there is a path from x, to x, then every path with x in the path is infinite.

[hiloshi]

hi sohel.

I used Floyd too, and got WA.

So I check following test case:

Code: Select all

6
0 1
0 2
1 2
2 3
3 2
3 4

Output shoud be follow:

Code: Select all

matrix for city 0
0 1 -1 -1 -1
0 0 -1 -1 -1
0 0 -1 -1 -1
0 0 -1 -1 -1
0 0 0 0 0

But My first program outputed follow:

Code: Select all

matrix for city 0
0 1 -1 -1 4
0 0 -1 -1 2
0 0 -1 -1 -1
0 0 -1 -1 -1
0 0 0 0 0

The cause of my mistake was method to check the cycle.
Then I change My code, I got Accept.

The cause of your mistake is...

And this one finds cycle.
C++:

Code: Select all

for(i=0;i<max;i++) 
     for(j=0;j<max;j++) 
         for(k=0;k<max;k++) 
        { 
              if( d[j][i] && d[i][i] && d[i][k]) 
              d[j][k] = -1; 
        } 

The program says, "There will never be a one-way street from an intersection to itself.",
so d is always 0.
But if you use Warshall, d may be more than or equal to 1.
But this check is not needed.
If and only if the path 0->1 and the path 1->0 exists, you can find the cycle, without check the path 0->0 or 1->1.

And you will check d[j] and d[k], but you can't find ｔwo sections which contain the cycle in the middle of the path.
For example, 0->4 and 1->4 in above test case which I showed.
This is the cause of your mistake.
If you change the method to find cycle, you will get accept.

But you may already get accept...

[coldfire]

Please someone tell me where i'm wrong .. or at least give me some test data :| ?

const maxN = 101;

var a, b: array[0..maxN, 0..maxN] of longint;
l, n, m, x, y, k, i, j: longint;

procedure read_data;
begin

// assign(input, '125.in'); reset(input);
// assign(output, '125.out'); rewrite(output);

l := 0;
while not eof(input) do begin

read(n);

inc(l); m := -1;
fillchar(a, sizeof(a), 0);
fillchar(b, sizeof(b), 0);
for i := 1 to n do begin
read(x, y);
a[x, y] := a[x, y] + 1;
b[x, y] := b[x, y] + 1;
if x > m then m := x;
if y > m then m := y;
end;

for k := 0 to m do
for i := 0 to m do
for j := 0 to m do a[i, j] := a[i, j] + a[i, k] * a[k, j];

for k := 0 to m do
if a[k, k] = 0 then
for i := 0 to m do
if a[i, i] = 0 then
for j := 0 to m do
if a[j, j] = 0 then b[i, j] := b[i, j] + b[i, k] * b[k, j];

for i := 0 to m do
for j := 0 to m do
if b[i, j] <> a[i, j] then b[i, j] := -1;

writeln('matrix for city ', l - 1);
for i := 0 to m do begin
for j := 0 to m do write(b[i, j], ' ');
writeln;
end;

end;

// close(input); close(output);

end;

begin

read_data;

end.

I'm first doing Floyd Warshal, then i'm removing the nodes which have a[x, x] > 0. I'm doing Floyd Warshal again and write solution. It's been working for all test cases i've tried.

[Relja]

My idea is following :
let A be a starting matrix ( relations between verteces ).
i am calculating next : A + A^2 + A^3 + ... + A^n ( for n=1 to e 60 ).
And, if in some step (A^2) > 0 then RESULT=-1..
So in future, when i am multiplying and situation is i,j,k

if ( EDGE[k][j] && RESULT[k]==-1 ) RESULT[j]=-1

otherwise continue calculating..

Is my idea ok ?
I am getting WA..

[rk]

hi,

i m consttantly getting WA in 125....
kindly give test cases that fail in this using floyd warshall

code is

Code: Select all

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
int main()
    {int X[35][35],X2[35][35],n,mx,cc=-1,Z[35][35];
     vector<int> v1[35];
     //vector<int> ex;
     while(cin>>n)
        {mx=-1;cc++;//ex.clear();
         for(int a=0;a<35;a++) v1[a].clear();
         for(int a=0,b,c;a<n;a++)
            {cin>>b>>c;mx=max(mx,b);mx=max(mx,c);
             //if(find(v1[b].begin(),v1[b].end(),c)==v1[b].end()) 
                v1[b].push_back(c);//if same sides entered twice
            }mx++;
         vector<int>::iterator i,i2;
         for(int a=0;a<mx;a++) for(int b=0;b<mx;b++) {X[a][b]=0;Z[a][b]=0;}
         for(int a=0;a<mx;a++)
            for(i=v1[a].begin();i!=v1[a].end();i++)
               {X[a][*i]=1;Z[a][*i]++;}
         for(int a=2;a<=2*mx;a++)
            {for(int aa=0;aa<mx;aa++) for(int b=0;b<mx;b++) X2[aa][b]=X[aa][b];
             for(int b=0;b<mx;b++)
                for(int bb=0;bb<mx;bb++)
                    {
                     for(i2=v1[b].begin();i2!=v1[b].end();i2++)
                          if(X[*i2][bb]==a-1) 
                               {//if(b==bb) ex.push_back(bb);
                                X2[b][bb]=a;
                                //if(find(ex.begin(),ex.end(),b)==ex.end() && find(ex.begin(),ex.end(),bb)==ex.end() && find(ex.begin(),ex.end(),*i)==ex.end() && Z[b][bb]!=-1) 
                                   Z[b][bb]++; 
                                //else Z[b][bb]=-1;
                               }
                     
                    }
             for(int aa=0;aa<mx;aa++) for(int b=0;b<mx;b++) X[aa][b]=X2[aa][b];
            }
        for(int k = 0; k < mx; k++) 
           if(Z[k][k] > 0) 
               for(int i = 0; i < mx; i++) 
                  for(int j = 0; j < mx; j++) 
                          if(Z[i][k] != 0 && Z[k][j] != 0) 
                              Z[i][j] = -1;
        if(cc!=0) cout<<endl;
        cout<<"matrix for city "<<cc;
        for(int a=0;a<mx;a++)
           {cout<<endl;
            cout<<Z[a][0];for(int b=1;b<mx;b++) cout<<" "<<Z[a][b];
           }
       }
     return 0;
    }

thnx

[helloneo]

Search first and don't make a new thread if there is one already..
If you need to post, use one of the old one to post..

[vinaychander]

i am attempting to solve problem number 125 : numbering paths..
i am getting a wrong anwer..
could ny of u pls help me out???

#include<stdio.h>
#include<stdlib.h>
#define G 1
#define W 0
#define B 2
int func(int i,int j,int **graph,int **out,int *visited,int max);
void init(int **arr);
void reset(int *visited);
void prin(int count,int **arr,int max);
int main()
{
int noi,k,max=0,a,b,i,j,ret,count;
int *graph[30],visited[30],*out[30];
for(k=0;k<30;k++)
{
graph[k]=(int *)malloc(sizeof(int)*30);
out[k]=(int *)malloc(sizeof(int)*30);
}
for(count=0;scanf("%d",&noi)!=EOF;count++)
{
ret=0;
max=-1;
init(graph);
init(out);
for(k=0;k<noi;k++)
{
scanf("%d",&a);
scanf("%d",&b);
graph[a]=1;
if(a>max)
max=a;
if(b>max)
max=b;
}
for(i=0;i<=max;i++)
{
reset(visited);
for(j=0;j<=max;j++)
{
if(visited[j]==W&&j!=i)
{
visited[j]=G;
for(k=0;k<=max;k++)
{
if(graph[j][k]==1&&visited[k]==W)
{
ret=func(i,k,graph,out,visited,max);
out[j]+=ret;
}
else if(graph[j][k]==1&&visited[k]==B)
{
out[j]+=out[k];
}
}
visited[j]=B;
}
}
}
for(i=max;i>=0;i--)
{
for(j=max-i;j<=max;j++)
{
if(out[max-i][j]>0&&out[j][max-i]>0)
{
out[max-i][j]=-1;
out[j][max-i]=-1;
out[max-i][max-i]=-1;
out[j][j]=-1;
}

}
}
for(i=0;i<=max;i++)
{
if(out==-1)
{

for(j=0;j<=max;j++)
{
if((i!=j)&&(out[j]>0))
out[j]=-1;
}
}
}

prin(count,out,max);
}
}
int func(int i,int j,int **graph,int **out,int *visited,int max)
{
int ret=0;
int k;
if(j==i)
return(1);
else
{
visited[j]=G;
for(k=0;k<=max;k++)
{
if(graph[j][k]==1)
{
if(visited[k]==W)
{
ret+=func(i,k,graph,out,visited,max);
out[j]=ret;
}
else if(visited[k]==B)
{
out[j]+=out[k];
ret+=out[k][i];
}
else if(visited[k]==G)
{
visited[j]=W;
return 0;
}
}

}
visited[j]=B;
return(ret);
}
}
void init(int **arr)
{
int i,j;
for(i=0;i<30;i++)
{
for(j=0;j<30;j++)
{
arr[i][j]=0;
}
}
}
void reset(int *visited)
{
int i;
for(i=0;i<30;i++)
{
visited[i]=W;
}
}
void prin(int count,int **out,int max)
{
int i,j;
printf("matrix for city %d\n",count);
for(i=0;i<=max;i++)
{
for(j=0;j<=max;j++)
{
printf("%d ",out[i][j]);
}
printf("\n");
}
}

[Jan]

Search the board first. Dont open a new thread if there is one already.

[mukeshtiwari]

@xbeanx

g8 observation . thnkx a lot . ur observation really helped me lot to solve the problem.