## 125 - Numbering Paths

Moderator: Board moderators

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### Prob 125 Numbering Paths

Why I get WA? My program work fine work fine at all my and not my tests but on acm.uva.es it failed. Please, help me! (* Numbering Paths *)
(*Algorithm O(n^4)*)

Program p125 (input, output);

Const MaxN = 30;

Var A : array[1..MaxN*2,1..MaxN,1..MaxN]of extended;
Result : array[1..MaxN,1..MaxN]of extended;
City : array[1..MaxN,1..MaxN]of byte;
i,j,N,S,k,p : integer;
count : integer;

begin
count:=-1;
while not eof(input) do begin
count:=count+1;
for i:=1 to MaxN do
for j:=1 to MaxN do begin
City[i,j]:=0;
for p:=1 to MaxN do A[p,i,j]:=0;
Result[i,j]:=0;
end;
Writeln(Output,'matrix for city ',count:0);
Writeln(Output,'0');
end else begin
N:=1; if eof(input) then break;
for i:=1 to S do begin
City[j+1,k+1]:=1;
A[1,j+1,k+1]:=1;
Result[j+1,k+1]:=1;
if j+1>N then N:=j+1;
if k+1>N then N:=k+1;
end;
for p:=2 to 2*N do begin
for i:=1 to N do
for j:=1 to N do
if A[p-1,i,j]>0 then
for k:=1 to N do
if City[j,k]=1 then begin
A[p,i,k]:=A[p,i,k]+A[p-1,i,j];
if p<=N-1 then Result[i,k]:=Result[i,k]+A[p-1,i,j] else Result[i,k]:=-1;
end;
end;
Writeln(Output,'matrix for city ',count:0);
for i:=1 to N do begin
for j:=1 to N-1 do Write(Output,Result[i,j]:0:0,' ');
Writeln(Output,Result[i,N]:0:0);
end;
end;
end;
end.

With best regrads, Revenger C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
This is just a modified All Points Shortest Path, right? Anyone know why my code does the WA thing? Repost of previous thread=)

Code: Select all

``````#include <cstdio>

void main()
{
int i,j,k,N,T,C,M,L;
T=0;
while(scanf("%d",&N)!=EOF)
{
M=0;
for(i=0;i<50;i++)
for(j=0;j<50;j++)
C[i][j]=0;
for(i=0;i<N;i++)
{
scanf("%d%d",&j,&k);
C[j][k]=1;
}
printf("matrix for city %dn",T);
for(i=0;i<50;i++)
for(j=0;j<50;j++)
if(C[i][j]!=0)
{
if(i>M)M=i;
if(j>M)M=j;
}

for(j=0;j<=M;j++)
for(i=0;i<=M;i++)
for(k=0;k<=M;k++)
{
if(C[i][j]!=0&&C[j][k]!=0)
{
C[i][k]+=C[i][j]*C[j][k];
}
}

for(i=0;i<=M;i++)
if(C[i][i]>0)
{
for(j=0;j<=M;j++)
if(C[i][j]>0)C[i][j]=-1;
}

for(i=0;i<=M;i++)
for(j=0;j<=M;j++)
if(C[i][j]>0&&C[j][j]==-1)
C[i][j]=-1;

for(i=0;i<=M;i++)
{
for(j=0;j<=M;j++)
{
printf("%d",C[i][j]);
if(j!=M)
printf(" ");
}
printf("n");
}
T++;
}
}
``````

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
If I remember right, this algorithm scheme has the problem that the union of path sets is not necessarily disjoint, so you might end up counting paths more than once. I think I fixed it by making it a special case when i=k or j=k or sth like that...

Chung Ha, Yun
New poster
Posts: 19
Joined: Tue Jul 16, 2002 5:56 pm
Location: Seoul
Contact:

###  Numbering Path ... WA, again and again

Sample Input and Output is correct...

But, Judge Server is WA, again....

[c]
#include<stdio.h>

void main()
{
int i, j, k, x, y, maxinput;
int count, max, city = 0;
int input;
while(scanf("%d", &count) > 0)
{
/* Initialize */
for(i=0;i<30;i++)
for(j=0;j<30;j++)
input[j] = 0;
max = 0;
/* Input */
for(i=0;i<count;i++)
{
scanf("%d %d", &x, &y);
input[x][y] = 1;
maxinput = (x > y ? x : y);
if(max < maxinput)
max = maxinput;
}

/* Check Repeat */
for(i=0;i<=max;i++)
for(j=0;j<=max;j++)
if(i > j && input[j] == 1 && input[j] == 1)
input[j] = input[j] = -1;

/* Modify Floyd Algorithm */
for(k=0;k<=max;k++)
for(i=0;i<=max;i++)
for(j=0;j<=max;j++)
if(i != k && j != k)
if(input[k] != 0 && input[k][j] != 0)
{
if(input[k] == -1 || input[k][j] == -1)
input[j] = -1;
else
input[j] += input[k] * input[k][j];
}

/* Output */
printf("matrix for city %d\n", city++);
for(i=0;i<=max;i++)
{
for(j=0;j<=max;j++)
{
if(j != 0)
printf(" ");
printf("%d", input[i][j]);
}
printf("\n");
}
}
}[/c]

visser
New poster
Posts: 8
Joined: Mon Jun 10, 2002 11:13 am
Location: Netherlands
try for input:

3
2 1
0 2
1 2

output should be:

0 -1 -1
0 -1 -1
0 -1 -1

you get:

0 -1 1
0 -1 -1
0 -1 -1

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

### I have the same problem

but the input you give is ok on my computer.
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

### 125-Numbering Paths PLZ help

i just used allpair shortest path but giving me WA,is there any tricky case. can anybody help

my code:

Code: Select all

``````#include <stdio.h>
#include <values.h>

#define size 35
int m[size][size];

void allpair(int n)
{

int i,j,k;
for(k=0;k<=n;k++)
{
for(i=0;i<=n;i++)
{
if(i!=k)
{
for(j=0;j<=n;j++)
{
//if(j!=k && i!=j)
if(m[i][k]!=0 && m[k][j]!=0)
{
m[i][j] += m[i][k] * m[k][j];

}
}
}
}
}
}

void main()
{

int N,i,j,max,u,v,count=0;
// freopen("125.in","r",stdin);
while(scanf("%d",&N)==1)
{

for(i=0;i<size;i++)
for(j=0;j<size;j++)
m[i][j]=0;

max=0;
for(i=0;i<N;i++)
{
scanf("%d%d",&u,&v);
m[u][v]=1;
if(u>max) max=u;
if(v>max) max=v;

}

allpair(max);

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

for(i=0;i<=max;i++)
for(j=0;j<=max;j++)
if(m[i][j]>0 && m[j][j]==-1)
m[i][j]=-1;

printf("matrix for city %d\n", count++);
for(i=0;i<=max;i++)
{
for(j=0;j<=max;j++)
{
if(j)
printf(" ");
printf("%d", m[i][j]);
}
printf("\n");
}

}

}
``````

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

### 125 - Numbering Paths

Can anybody provide me with test samples that are likely to result in Time Limit Error with my program? It takes my program 0.1 seconds to solve first 13 Judge's inputs, but it takes more then 10 seconds for input #14... What kind of input can it be?
[cpp]#include <iostream.h>
int n,count,max;
int intrs;
int exist;
int used;
int used_by_full;
int double_used;

// this is most likely the function that causes TLE
void culc_pass(int i1, int i2, int depth){
if((used[i1]) && (i1 != i2)){
double_used[i1] = 1;
return;
}
if(depth)
used[i1] = 1;
if((i1 == i2) && (depth)){
count++;
for(int i = 0; i < max; i++)
if(used) used_by_full = 1;
}
for(int i = 0; i < max; i++)
if(intrs[i1]) culc_pass(i,i2,depth + 1);
used[i1] = 0;
return;
}
//**********************************

int main(){
int i1,i2,city;
city = 0;
while(cin >> n){
max = 0;
for(int i = 0; i < 30; i++) exist = 0;
for(int i = 0; i < 30; i++)
for(int j = 0; j < 30; j++){
intrs[j] = 0;
}
for(int i = 0; i < n; i++){
cin >> i1 >> i2;
intrs[i1][i2] = 1;
exist[i1] = 1;
exist[i2] = 1;
if(max < i1 + 1) max = i1 + 1;
if(max < i2 + 1) max = i2 + 1;
}

for(int i = 0; i < max; i++)
for(int j = 0; j < max; j++)
if(exist && exist[j]){
for(int k = 0; k < max; k++){
used[k] = 0;
used_by_full[k] = 0;
double_used[k] = 0;
}
count = 0;
culc_pass(i,j,0);
for(int k = 0; k < max; k++)
if(double_used[k] && used_by_full[k])
}
cout << "matrix for city " << city << endl;
city++;
for(int i = 0; i < max; i++){
for(int j = 0; j < max; j++) cout << answer[j] << " ";
cout << "\n";
}
}

return 0;
}[/cpp]

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
Such a problem can be solved by Warshall algorithm.
for example:
(MAP[J] is the number of different routes from intersection I to intersection J.)
if there is a way to go from MAP[K] to MAP[K][J],
then you should add MAP[K]*MAP[K][J] to MAP[J].

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Thanks for your reply. I did not know such algorith exists. I'm going to write another solution according to this algorithm.
Are you sure I get TLE because my code is too slow?
It takes my program 0.1 seconds to solve first 13 Judge's inputs, but it takes more then 10 seconds for input #14...
Here is some question I have about Warshall algorithm:
if there is a way to go from MAP[K] to MAP[K][J]
,where
MAP[J] is the number of different routes from intersection I to intersection J
How can we go from one number of routes to another? Where do we get K?
then you should add MAP[K]*MAP[K][J] to MAP[J].
Should I put PAM[J] = 0 first and go through all possible k? All k from one of possible routes between I and J?

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
I give you some tips.
Here is my method ( warshall algo. ):

Code: Select all

``````for( k=0 to n )
for( i=0 to n )
for( j=0 to n )
if( map[i][k] AND map[k][j] ){
if( i=j ) map[i][j]=FLASE
if( map[i][k] OR map[k][j] ) map[i][j]=FALSE
else map[i][j]+=map[i][k]*map[k][j]
}
// scan again
for( k=0 to n )
for( i=0 to n )
for( j=0 to n)
if( map[i][k] AND map[k][j] AND (map[i][k]=FLASE OR map[k][j]=FALSE) )
map[i][j]=FLASE
``````

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Consider in this part of your code

Code: Select all

``````      /* Input */
for(i=0;i<count;i++)
{
scanf("%d %d", &x, &y);
input[x][y] = 1;
maxinput = (x > y ? x : y);
if(max < maxinput)
max = maxinput;
}

``````
this sample
3
1 2
1 2
1 2
output should be obvious ....

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm

### Problem 125 : Path Numbering

I'm trying to figure out an algorithm for problem 125. From what I've read on the net, this is an "experts only" problem.

I dunno. It doesn't seem TOO hard.

Obviously, this can be solved by calculating a total accessibility matrix (well known in network theory). But my algorithm has horrible running time.

The things I would like to know are:
1) Am I correct in assuming this is a TA problem?
2) Is there an efficient way to calculate the diameter of the graph whilst parsing the input?

If anyone has any suggestions to a better algorithm I'd like to know.

Thanks

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
HINT: This problem can be solved using array multiplications ... and array for graph you can create when you read input Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm