125 - Numbering Paths

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by 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
New poster
Posts: 11
Joined: Sat Dec 29, 2007 2:39 pm

Post by Brainless »

Hello,

Can somebody post an input and output ?

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

Thanks !

dreadlord
New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

Re:

Post by dreadlord »

Brainless wrote: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
New poster
Posts: 6
Joined: Wed May 25, 2005 8:21 pm

Clarifying questions - 125 Numbering Paths

Post by 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
New poster
Posts: 6
Joined: Wed May 25, 2005 8:21 pm

Re: Clarifying questions - 125 Numbering Paths

Post by 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
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 125-Numbering Paths PLZ help

Post by 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
New poster
Posts: 1
Joined: Wed Sep 16, 2009 7:13 am

125 - Numbering Ways - WA

Post by 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
New poster
Posts: 15
Joined: Sun Apr 23, 2006 1:35 pm

Re: 125-Numbering Paths PLZ help

Post by LlatzerandToni »

Try with

Code: Select all

return 0;
at the end of the code.
Lol

Pooria
New poster
Posts: 4
Joined: Thu May 29, 2014 9:56 pm

125 why PE ?

Post by 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
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 125 why PE ?

Post by 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;
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Pooria
New poster
Posts: 4
Joined: Thu May 29, 2014 9:56 pm

Re: 125 why PE ?

Post by Pooria »

got AC!!
ty so much :X

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 125 - Numbering Paths

Post by 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
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”