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

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

Prob 125 Numbering Paths

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! :cry:

(* 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 8)

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

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...

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

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

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
New poster
Posts: 8
Joined: Mon Jun 10, 2002 11:13 am
Location: Netherlands

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
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

I have the same problem

Post by zbogi » Wed Sep 11, 2002 4:24 pm

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

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

125-Numbering Paths PLZ help

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

125 - Numbering Paths

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... :cry: 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]

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

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?

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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
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
Location: Newfoundland, Canada (St. John's)

Problem 125 : Path Numbering

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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
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
Location: Newfoundland, Canada (St. John's)

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.

Post Reply

Return to “Volume 1 (100-199)”