Page 1 of 4
Prob 125 Numbering Paths
Posted: Sun Apr 14, 2002 12:33 pm
by Revenger
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;
Read(input,S); if S=0 then begin
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
Read(Input,j,k);
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
Posted: Sun Apr 14, 2002 3:39 pm
by C8H10N4O2
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[50][50],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++;
}
}
Posted: Mon Apr 15, 2002 4:12 am
by Stefan Pochmann
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...
[125] Numbering Path ... WA, again and again
Posted: Thu Jul 25, 2002 3:52 pm
by Chung Ha, Yun
Sample Input and Output is correct...
But, Judge Server is WA, again....
Please Help Me...~*
[c]
#include<stdio.h>
void main()
{
int i, j, k, x, y, maxinput;
int count, max, city = 0;
int input[30][30];
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]
Posted: Wed Jul 31, 2002 1:30 pm
by visser
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
I have the same problem
Posted: Wed Sep 11, 2002 4:24 pm
by zbogi
but the input you give is ok on my computer.
125-Numbering Paths PLZ help
Posted: Wed Dec 04, 2002 6:04 am
by rakeb
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");
}
}
}
125 - Numbering Paths
Posted: Mon Mar 03, 2003 12:56 am
by minskcity
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[30][30];
int exist[30];
int used[30];
int used_by_full[30];
int double_used[30];
int answer[30][30];
// 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;
answer[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);
answer[j] = count;
for(int k = 0; k < max; k++)
if(double_used[k] && used_by_full[k])
answer[j] = -1;
}
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]
Posted: Wed Mar 12, 2003 3:03 pm
by hank
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].
Posted: Thu Mar 13, 2003 3:22 am
by minskcity
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?
Posted: Fri Mar 14, 2003 5:16 pm
by hank
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
Posted: Mon Mar 31, 2003 8:25 am
by Dominik Michniewski
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
Problem 125 : Path Numbering
Posted: Mon Aug 25, 2003 3:14 pm
by xbeanx
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
Posted: Tue Aug 26, 2003 7:53 am
by Dominik Michniewski
HINT: This problem can be solved using array multiplications ... and array for graph you can create when you read input
Best regards
DM
Posted: Tue Aug 26, 2003 5:41 pm
by xbeanx
Hey! Thanks for your advice. I tried solving it by making a total accessibility matrix, and didn't get too far.
Then I tried using a modified Floyd Warshall to build up a total paths matrix. That worked, so I used another Floyd Warshall to destroy all cycles.
My final algorithm had running time of O(n^6) but got accepted in less than a second.
I found a solution on the net that actually did all these computations while reading the input, but it didn't make much sense to me. I think the running time for that one was O(n^3).
I was reading a post here earlier that mentioned constraints like (k!=i) or (j!=i) when multiplying the matrices. Unfortunately that delayed my solution by a while. In the end, when I removed such constraints my program got accepted.
I guess that's one of the disadvantages of reading the message boards for help -- you get biased very quickly.