11047 - The Scrooge Co Problem

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

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

11047 - The Scrooge Co Problem

Post by Jan » Sun Jun 04, 2006 6:20 am

I have some questions about this problem. I have got a lot of Wa's. :-?

1. What if there are multiple paths with min cost?
2. If the source and the destination are the same location and the cost is zero then what should be the output?
3. The problem states -
The next P lines contain the minimum cost to go from one location to another one
The first sample case contains that it is too expensive to go from 1 to 4. But the sample output says that there is a route, for which the cost is less than the input given.
So, how can the given input be the 'minimum cost'?

Weird description? Or I m missing something?

Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11047 - The Scrooge Co Problem

Post by helloneo » Sun Jun 04, 2006 7:56 am

Jan wrote:I have some questions about this problem. I have got a lot of Wa's. :-?

1. What if there are multiple paths with min cost?
2. If the source and the destination are the same location and the cost is zero then what should be the output?
3. The problem states -
The next P lines contain the minimum cost to go from one location to another one
The first sample case contains that it is too expensive to go from 1 to 4. But the sample output says that there is a route, for which the cost is less than the input given.
So, how can the given input be the 'minimum cost'?

Weird description? Or I m missing something?

Thanks in advance.
I think the statement means that 'minimum cost' is the minimum cost among the costs of directly connected roads from a city to another ..
So you can simply ignore the word 'minimum' to solve the problem ..

And I didn't consider the case 1, 2

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sun Jun 04, 2006 8:49 am

to jan:
the input is just adjacent matrix. -1 means there is no edge between the two nodes, but there might be some path consisiting two or more edges between the two nodes. i just run simple FW(AC), so if there are multiple paths with min cost anyone can be taken. but i wonder this problem is not yellow marked, might be there is no test case with multiple paths with minimum costs. if source and destination is same you have to printf("Path:%s %s\n", source, dest) i tested this. printing only source or destination will give WA.
"Path:<orig name> <locations separated by a blank> <dest name>"
<locations separated by a blank> is optional, but <orig name> and <dest name> must be present.
hope it make 991 ac
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Jun 04, 2006 1:30 pm

accepted
:lol:
Last edited by arsalan_mousavian on Sun Jun 04, 2006 8:16 pm, edited 3 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jun 04, 2006 1:35 pm

Thanks helloneo. And special thanks to ayon. I got it accepted and made it to 991 as you wished :D .

Sometimes we have to ignore a lot of parts from the description.

To arsalan_mousavian,
Try the following test case

Input:

Code: Select all

1
3
Murcia	Alicante	Albacete
-1	3	-1
10	0	4
-1	-1	0
1
Jan Murcia Murcia
Output:

Code: Select all

Mr Jan to go from Murcia to Murcia, you will receive 13 euros
Path:Murcia Alicante Murcia
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Please someone post some i...

Post by nymo » Sun Jun 04, 2006 3:17 pm

Hi, I am getting WA, can you post some io? ... and is the above io posted by Jan okay, it seems diagonal (i == i) should contain 0[ here, matrix[0][0] contains -1].

[EDIT] Thanks lord_burgos, your i/o helps me to find my error, it has been in the function to print path.
Last edited by nymo on Mon Jun 05, 2006 1:21 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jun 04, 2006 3:49 pm

I have tested the input. And I m sure that there are test cases where a is not equal to zero.

You can try it by assert() function.

If you are still getting WA then try reading the post given by ayon.
Ami ekhono shopno dekhi...
HomePage

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Mon Jun 05, 2006 7:36 am

Input

Code: Select all

2
5
Puebla Mexico Queretaro Durango San_Pedro
2 3 0 1 1
3 0 2 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0
2
Nalley Puebla Puebla
Xuxa Mexico Mexico
3
hola como estas
2 3 0
3 0 2
0 1 0
2
Pedro hola como
Juan como como
Output (Solution AC):

Code: Select all

Mr Nalley to go from Puebla to Puebla, you will receive 0 euros
Path:Puebla Queretaro Durango Puebla
Mr Xuxa to go from Mexico to Mexico, you will receive 0 euros
Path:Mexico Mexico
Mr Pedro to go from hola to como, you will receive 1 euros
Path:hola estas como
Mr Juan to go from como to como, you will receive 0 euros
Path:como como

lukasP
New poster
Posts: 3
Joined: Mon Aug 08, 2005 12:44 pm
Location: Pezinok, Slovakia

Post by lukasP » Tue Jun 06, 2006 9:28 am

Hello,
I am getting WA. My program works good for input posted here. Did you assume that the names of cities don't contain spaces?

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Tue Jun 06, 2006 11:54 am

Names of cities don't contain spaces.

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

Post by C » Tue Jun 06, 2006 5:19 pm

My code also passes all i/os here,but i still got WA. Could anyone give some more i/os?

It is a simple shortest-path problem, right ??

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Tue Jun 06, 2006 6:13 pm

C wrote:My code also passes all i/os here,but i still got WA. Could anyone give some more i/os?

It is a simple shortest-path problem, right ??
yes , but maybe you do some thing wrong in printing the path , or you assign too high value when cost of 2 vertex is -1 that cause integer overflow
Hope it Helps
Arsalan
In being unlucky I have the record.

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

Post by C » Tue Jun 06, 2006 8:30 pm

or you assign too high value
Thanks Arsalan, but I didn't assign a big value instead of -1, but judge each time if the distance is -1 or not.
but maybe you do some thing wrong in printing the path
I saved the "parent vertex" of each vertex, and then my print algo seems like:

Code: Select all

print(startVertex);
k= endVertex;
while(k.parent!=startVertex)
{
        k= k.parent;
        stack.push(k);
}
while(!empty(stack))
{
       print(s.pop());
}
print(endVertex);
Actually I only used a array to work as a stack.

Any other advices ?? Thanks in advance!!!

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Tue Jun 06, 2006 11:13 pm

add small part to the FW algorithm

Code: Select all

if ( map [i][j] > ( map [i][k] + map [k][j] ) )
				  {
					  map [i][j] = map [i][k] + map [k][j] ;
					  prev[i][j] = k ;
				  }
and you can simply print it recursively
Have Fun !! :wink:
In being unlucky I have the record.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

For printing path:)

Post by nymo » Wed Jun 07, 2006 6:53 am

Let, d[SIZE][SIZE] and parent[SIZE][SIZE] are respectively the matrix for distance and parent.

Code: Select all

INITIALIZE PORTION:
================
for parent, I use something like this,

void initParent(int noCity)
{
	int i, j;
	
	for (i=0; i<noCity; i++)
	{
		for (j=0; j<noCity; j++)
		{
			if (i == j || d[i][j] == INFINITY) 
				parent[i][j] = NIL;

			else if (i != j && d[i][j] < INFINITY)
				parent[i][j] = i;
		}
	}
}

Inside FW
=======
my code fragment goes something like this...

	if (d[i][j] > d[i][k] + d[k][j])
	{
	    d[i][j] = d[i][k] + d[k][j];
	    parent[i][j] = parent[k][j];
	}

May be I am wrong, but I don't think prev[i][j] = k demonstrated by arsalan_mousavian would produce correct result all the time. Shouldn't it be prev[i][j] = prev[k][j]?
[EDIT] May be we initialize our parent matrix in different ways, It was unwise on my side to say that your fragment may be wrong without considering init portion... sorry. :oops: , don't mind :D 

A simple recursive function then does the trick of printing path:)
Last edited by nymo on Wed Jun 07, 2006 8:58 am, edited 1 time in total.

Post Reply

Return to “Volume 110 (11000-11099)”