thnkx a lotcheck 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.
125  Numbering Paths
Moderator: Board moderators

 Learning poster
 Posts: 63
 Joined: Tue Mar 07, 2006 6:51 pm
 Location: india
Re:
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.Brainless wrote:Hello,
Can somebody post an input and output ?
Thanks !
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
Thanks,
Dread
Clarifying questions  125 Numbering Paths
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
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
Re: Clarifying questions  125 Numbering Paths
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.
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.
Re: 125Numbering Paths PLZ help
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
, output is and case =10
matrix for city 10
matrix for city 11
125  Numbering Ways  WA
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.
Maybe the problem lies in invalid input handling?
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<cities1; 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 [step1][ 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;
}

 New poster
 Posts: 15
 Joined: Sun Apr 23, 2006 1:35 pm
125 why PE ?
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?
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?
Re: 125 why PE ?
You are printing extra space after last number.
Change it to
Code: Select all
for(int j=0;j<n;j++)
cout<<r[i][j]<<" ";
Code: Select all
for(int j = 0; j < n  1; j++)
cout<<r[i][j]<<" ";
cout<<r[i][n  1]<<endl;
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Re: 125 why PE ?
got AC!!
ty so much :X
ty so much :X

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 125  Numbering Paths
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 Elidioto
Hi 40366,
Try the following input:
It should return:
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 Elidioto
Hi 40366,
Try the following input:
Code: Select all
0
3 0 1 1 2 2 1
Code: Select all
matrix for city 0
matrix for city 1
0 1 1
0 1 1
0 1 1
Check input and AC output for thousands of problems on uDebug!