125 - Numbering Paths

Revenger · Post by **Revenger** » Sun Apr 14, 2002 12:33 pm

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

C8H10N4O2 · Post by **C8H10N4O2** » Sun Apr 14, 2002 3:39 pm

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++;
	}
}

Stefan Pochmann · Post by **Stefan Pochmann** » Mon Apr 15, 2002 4:12 am

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 · Post by **Chung Ha, Yun** » Thu Jul 25, 2002 3:52 pm

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]

visser · Post by **visser** » Wed Jul 31, 2002 1:30 pm

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 · Post by **zbogi** » Wed Sep 11, 2002 4:24 pm

but the input you give is ok on my computer.

rakeb · Post by **rakeb** » Wed Dec 04, 2002 6:04 am

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 · Post by **minskcity** » Mon Mar 03, 2003 12:56 am

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]

hank · Post by **hank** » Wed Mar 12, 2003 3:03 pm

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 · Post by **minskcity** » Thu Mar 13, 2003 3:22 am

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 · Post by **hank** » Fri Mar 14, 2003 5:16 pm

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 · Post by **Dominik Michniewski** » Mon Mar 31, 2003 8:25 am

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

xbeanx · Post by **xbeanx** » Mon Aug 25, 2003 3:14 pm

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 · Post by **Dominik Michniewski** » Tue Aug 26, 2003 7:53 am

HINT: This problem can be solved using array multiplications ... and array for graph you can create when you read input

Best regards
DM

xbeanx · Post by **xbeanx** » Tue Aug 26, 2003 5:41 pm

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.

OJ Board

125 - Numbering Paths

Prob 125 Numbering Paths

[125] Numbering Path ... WA, again and again

I have the same problem

125-Numbering Paths PLZ help

125 - Numbering Paths

Problem 125 : Path Numbering