125 - Numbering Paths

[mukeshtiwari]

Thnkx jubin for such valuble observation .

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.

thnkx a lot

[Brainless]

Hello,

Can somebody post an input and output ?

I get WA but don't know where is the fault.

Thanks !

[dreadlord]

Hello,

Can somebody post an input and output ?
Thanks !

I would also appreciate it if someone were able to post some IO cases, and in particular some one for which my program gives WA. I've tried with the sample IO and also with the ones I found in these forums, and in all cases my program gives the right output.

My program follows. I tried to write it in a quite readable form:

Code: Select all

<<< Removed after AC >>>
Anyway, I would still appreciate IO cases

Any help will be greatly appreciated.

Thanks,

--Dread

[snublefot]

The problem text is ambiguous, so I'm posting two clarifying questions:

1:
If two streets in the input connect the same two intersections in the same direction, are they two distinct streets or just the same street stated twice?

2:
Can you double back on a two way street and call it a loop?

Example for question 1:
4
0 1 1 2 1 2 2 3
1 or 2 routes between 0 and 3?

Example for question 2:
4
0 1 1 2 2 1 2 3
How many routes from 0 to 3? 1 or infinitely many?


Snublefot

[snublefot]

I guess I'll have to anser my own question:

1. They are two distinct streets yielding two distinct sets of routes.

2. No. And you can't go from one intersection to another and back again even if there are several streets between them in both directions.

[tryit1]

i failed AC many times because when E=0 , i took nodes a 1 , it should nodes as 0. ie when E=0,n=0
, output is and case =10
matrix for city 10
matrix for city 11

[gosdep]

Hello, guys, I need your help in problem 125. My algorithm seems to be correct and it gives right answers to all inputs known to me, but it still gets WA.

Code: Select all

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#define SIZE 35
               
int main() {

  int n, cities, step, i, j, k, c, count, curNeighbour, case_no;
  int graph_matrix[SIZE][SIZE][SIZE], sum_matrix[SIZE][SIZE];
  int neighbours [SIZE][SIZE];
  int n_counter [SIZE];
  int cycled_vertices[SIZE], good_vertices[SIZE];
  int cycled_vertices_num, good_vertices_num;
  
  case_no = -1;
  while (1) {
     if (scanf ("%d", &n) == 1) {        
        case_no++;
        
        if (n == 0) {
           printf ("matrix for city %d\n", case_no);
           continue;
        };
        
        for (i=0; i<30; i++) {
            n_counter[i] = 0;
            for (j=0; j<30; j++) {
                graph_matrix [0][i][j] = 0; 
                neighbours[i][j] = -1;
            }     
        } 
        
        cities = 0;
        for (k=0; k<n; k++) {
            scanf ("%d %d", &i, &j);
            if (i>cities)
               cities = i;
            if (j>cities)
               cities = j;            
            graph_matrix[0][i][j] = 1;
            neighbours[i][ n_counter[i] ] = j;
            n_counter[i]++;
        }
        cities++;
        
        /* Iterative DP */
        step = 1;
        for (k=0; k<cities-1; k++) {
            for (i=0; i<cities; i++)
                for (j=0; j<cities; j++) {
                     count = 0;
                     curNeighbour = 0;
                     while (neighbours[i][curNeighbour] > -1) {
                          count += graph_matrix [step-1][ neighbours[i][curNeighbour] ][j];
                          curNeighbour++; 
                     }
                     graph_matrix[step][i][j] = count;
                }
            
            step++;
        } 
        
        for (i=0; i<cities; i++)
            for (j=0; j<cities; j++) {
                count = 0;
                for (k=0; k<cities; k++)
                    count += graph_matrix[k][i][j];
                sum_matrix[i][j] = count;    
            }
        
        /* cycle detection */
        cycled_vertices_num = 0;
        good_vertices_num = 0;
        for (i=0; i<cities; i++) {
            if (sum_matrix[i][i]>0) {
               cycled_vertices[cycled_vertices_num] = i;
               cycled_vertices_num++;                     
            } else {
               good_vertices[good_vertices_num] = i;
               good_vertices_num++;                      
            }
        }
        
        /*  replacing all values for accessible vertices of cycled vertices with -1 */
        for (i=0; i<cycled_vertices_num; i++) {
            k = cycled_vertices[i];
            for (j=0; j<cities; j++)
                if (sum_matrix[k][j]>0)
                   sum_matrix[k][j] = -1;   
        }
        
        /* scanning good vertices, if good vertex has a route to a cycled vertice, all accessible points for this cycled vertice
           must be replaced with -1 in good vertex */
        for (i=0; i<good_vertices_num; i++) {
            k = good_vertices[i];
            for (j=0; j<cities; j++) {
                if (sum_matrix[k][j] > 0 && sum_matrix[j][j] < 0) {
                   for (c=0; c<cities; c++)
                       if (sum_matrix[j][c] < 0)
                          sum_matrix[k][c] = -1;                     
                }
            }    
        }
        
        printf ("matrix for city %d\n", case_no);
        for (i=0; i<cities; i++) {
            for (j=0; j<cities; j++) {
                if (j != 0)
                   printf(" ");
                printf ("%d", sum_matrix[i][j]);
            }
            printf ("\n");    
        }
                      
     } else
       break;             
  }
  
  return 0; 
}

Maybe the problem lies in invalid input handling?

[LlatzerandToni]

Try with

Code: Select all

return 0;

at the end of the code.

[Pooria]

my code for output is:

cout<<"matrix for city "<<city<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<r[j]<<" ";
cout<<endl;
}

what is the problem?

[lighted]

You are printing extra space after last number.

Code: Select all

for(int j=0;j<n;j++)
cout<<r[i][j]<<" ";

Change it to

Code: Select all

for(int j = 0; j < n - 1; j++)
    cout<<r[i][j]<<" ";
cout<<r[i][n - 1]<<endl;

[Pooria]

got AC!!
ty so much :X

[brianfry713]

I accidentally deleted these posts:

125 numbering paths WA pl. help
Post Posted Mon Jan 19, 2004 8:37 pm by 40366

[cpp]# include<iostream>
using namespace std;
void copy(int a[][30],int b[][30],int n)
{
int i,j;
for(i = 0;i <= n;i++)
for(j = 0;j <= n;j++)
b[j] = a[j];
}
int main()
{
int m,count = 0;
while(cin >> m)
{
count++;
int i,j,k;
bool sel[30];
int a[30][30],b[30][30],c[30][30],d[30][30],e[30][30];
for(i = 0;i < 30;i++)
sel = false;
for(i = 0;i < 30;i++)
for(j = 0;j < 30;j++)
a[j] = 0;
for(i = 1;i <= m;i++)
{
cin >> j >> k;
a[j][k] = 1;
sel[j] = sel[k] = true;
}
int n;
for(i = 29;i >= 0;i--)
if(sel)
{
n = i;
break;
}
int p,q;
copy(a,b,n);
copy(b,d,n);
int x,y;
for(x = 1;x < n;x++)
{
copy(b,c,n);
for(i = 0;i <= n;i++)
{
for(j = 0;j <= n;j++)
{
int sum = 0;
for(k = 0;k <= n;k++)
sum += a[k] * c[k][j];
b[j] = sum;
}
}
for(i = 0;i <= n;i++)
for(j = 0;j <= n;j++)
d[j] += b[j];
}
copy(d,e,n);
for(x = 1;x <= m - n;x++)
{
copy(b,c,n);
for(i = 0;i <= n;i++)
{
for(j = 0;j <= n;j++)
{
int sum = 0;
for(k = 0;k <= n;k++)
sum += a[k] * c[k][j];
b[i][j] = sum;
}
}
for(i = 0;i <= n;i++)
for(j = 0;j <= n;j++)
e[i][j] += b[i][j];
}
cout << "matrix for city " << count - 1 << "\n";
for(i = 0;i <= n;i++)
{
if(d[i][0] == e[i][0])
cout << d[i][0];
else
cout << -1;
for(j = 1;j <= n;j++)
if(d[i][j] == e[i][j])
cout << " " << d[i][j];
else
cout << " " << -1;
cout << "\n";
}
}
return 0;
}[/cpp]

125 numbering paths WA pl. help
Post Posted Wed Jan 21, 2004 4:16 pm by El-idioto

Hi 40366,

Try the following input:

Code: Select all

0
3 0 1 1 2 2 1

It should return:

Code: Select all

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