423 - MPI Maelstrom

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

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

423 - MPI Maelstrom

Post by Dominik Michniewski » Tue Aug 13, 2002 8:23 am

Could anyone say me, why Floyd is wrong in this problem ?
I try to solve it using Floyd and got WA many times :-(

My code is very simple:

read_data();
Floyd();
found longest path from all paths to all other nodes in table of shortest path ....

could anyone tell me any traps in this problem ??

Best regards
Dominik

T.T.
New poster
Posts: 12
Joined: Mon Dec 31, 2001 2:00 am
Location: Taiwan

Post by T.T. » Sat Aug 17, 2002 5:05 pm

I get the input carefully, in it's input
5
50
30 5
100 20 50
10 x x 10
every number represent ( except the size 5 )
arr[2][1]
arr[3][1] arr[3][2]
arr[4][1] arr[4][2] arr[4][3]
arr[5][1] arr[5][2] arr[5][3] arr[5][4]
then I use the Floyd's algorithm too
but I do't know why you get WA, you can check it again :)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Aug 21, 2002 10:47 am

Only one thing, which I can imagine, is 'X' in input. I set this 'x' as MAX_INT-1 (2.000.000.000 and something ;-) ) - maybe it's wrong ?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Wed Aug 21, 2002 11:17 am

Dominik Michniewski wrote:read_data();
Floyd();
found longest path from all paths to all other nodes in table of shortest path ....
Are you searching all paths or you searching all paths from first processor to all other processors as it needed by problem description?
Dominik Michniewski wrote:Only one thing, which I can imagine, is 'X' in input. I set this 'x' as MAX_INT-1 (2.000.000.000 and something ) - maybe it's wrong ?
I'm not sure that there is an input like 2^31-1 but I've used zero for value of 'x' and it was OK.
Also I've used Dijkstra not Floyd because we need not all paths only ones that goes from first processor(node).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Aug 22, 2002 8:31 am

Thanks all for help :-) I got accepted yesterday :-)

But I still don't know why my previous code got WA. I change only two things: don't set way to unrecheable nodes to INT-MAX - 1 and print 0 if from node 1 I can't walk to some else node .... :-))

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:

horrible runtime error!!!!!!

Post by Shahid » Thu Sep 26, 2002 2:25 pm

i submitted 423 agin and agin and evrything seems ok except the judges response(offcourse i don't want to say that the judge is wrong) ...but i get all the time runtime error. can anyone help me..... :(

at first i thought the problem may be regarding the qsort function, so i change i, but no change....bellow in the code i commented the previous qsort portion...

here is my code:
[c]


/*@BEGIN_OF_SOURCE_CODE*/




#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int adj[200][200];

int sort_function( const void *a, const void *b);

struct table
{
int known;
int dist;
int path;
} t[200];


void main()
{
int i, j, k, n, start = 1;
char str[205], *p;



while(scanf("%d\n", &n) == 1)
{
memset(adj, 0, sizeof(adj));

for(i = 0; i < n-1; i++)
{
j = 0;
strcpy(str, "");
gets(str);

p = strtok(str, " ""\t");

if(p)
if(!strcmp(p, "x"))
k = 0;
else
k = atoi(p);



adj[i+1][j] = k;
adj[j][i+1] = k;


for(;;)
{
p = strtok(NULL, " \t");

if(p)
{
if(!strcmp(p, "x"))
k = 0;
else
k = atoi(p);
}

else
break;
j++;
adj[i+1][j] = k;
adj[j][i+1] = k;
}
}

for(i = 0; i < n; i++)
{
t.known = 0;
t.dist = 9999;
t.path = 0;
}

t[start-1].dist = 0;

int min = 10000, flag = 0, v;

for(;;)
{
flag = 0;
min = 10000;
for(i = 0; i < n; i++)
if(!t.known)
{
if(t.dist < min)
{
min = t.dist;
v = i;
}
flag = 1;
}

if(!flag)
break;

t[v].known = 1;

for(j = 0; j < n; j++)
if(adj[v][j])
if(!t[j].known)
if((t[v].dist + adj[v][j]) < t[j].dist)
{
t[j].dist = t[v].dist + adj[v][j];
t[j].path = v+1;
}
}

// qsort(t, n, sizeof(t[0]), sort_function);

int max = 0;
for(i = 0; i < n; i++)
if(t.dist > max)
max = t.dist;

printf("%d\n", max);

// printf("%d\n", t[0].dist);
}
}


int sort_function( const void *a, const void *b)
{
struct table aa, bb;

aa = *(struct table *)a;
bb = *(struct table *)b;

if(aa.dist < bb.dist)
return 1;
if(aa.dist > bb.dist)
return -1;
else
return 1;
}

/*@END_OF_SOURCE_CODE*/






[/c]


thanx in advance.

abhijit
New poster
Posts: 12
Joined: Mon May 24, 2004 2:13 pm

Post by abhijit » Fri Feb 11, 2005 8:31 am

Yes, with floyds, one must never set no-link to INT_MAX-1 or somewhere close.
Since, the algo has a line like :
mat[k]+mat[k][j]
This will lead to an overflow in range, and will wrap to a negetive value, making your algo fail.

So make sure that 2*YOUR_MAX <= INT_MAX.

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

I need some IO :)

Post by nymo » Sun Apr 23, 2006 6:02 pm

Hi, I 've implemented dijkstra algo. with binary heap and want to check whether it produces correct answer... so, I try 423 and get WA :(
I need some tricky IO on this problem... thanks.

[EDIT] My implementation of Dijkstra is okay, it was a silly mistake on the input part. :oops: , AC now :D

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Re: I need some IO :)

Post by chunyi81 » Sun Jul 30, 2006 8:26 am

nymo wrote:Hi, I 've implemented dijkstra algo. with binary heap and want to check whether it produces correct answer... so, I try 423 and get WA :(
I need some tricky IO on this problem... thanks.

[EDIT] My implementation of Dijkstra is okay, it was a silly mistake on the input part. :oops: , AC now :D
I used Dijkstra for this problem as well, because we only need the longest transmission time from processor 1 to all other processors. Single-source is sufficient for this problem. Floyd is ok, but I think it is a bit of an overkill since Dijkstra can be used for finding all shortest paths from a single souce.

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

help

Post by JetBrain » Thu Oct 26, 2006 3:25 pm

Dominik Michniewski wrote:Only one thing, which I can imagine, is 'X' in input. I set this 'x' as MAX_INT-1 (2.000.000.000 and something ;-) ) - maybe it's wrong ?
Hi Dominik & T.T.
I used the same method u used to solve this problem.. but I'm still getting WA.. I use -1 instead of 'x' & add a condition to neglect it while trying to solve using warshall algorithm..

Code: Select all

if (d[i][k] + d[k][j] < d[i][j] && d[i][k] >= 0 && d[k][j] >= 0) 
				{
					d[i][j] = d[i][k] + d[k][j];
					p[i][j] = p[k][j];
				}
if anyone has any idea about this, let me know please..
Thanks..

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

Post by JetBrain » Thu Oct 26, 2006 3:33 pm

What do u think will be the output to the case where i = 1 ???
(as the problem statment mentioned 1<=i<=N )

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

423 WA :(

Post by JetBrain » Thu Oct 26, 2006 4:23 pm

I've been trying to solve this problem , but I keep getting WA :(
Please if anyone has sample tricky inputs, I'll be really so grateful..

I'm using warshall algo..
please help me cause I really fed up :(

Thanks...

vfa88
New poster
Posts: 1
Joined: Tue Feb 22, 2011 4:19 pm

Re: 423 - MPI .... please help

Post by vfa88 » Tue Feb 22, 2011 4:22 pm

Hi all,

I have been having some trouble with this particular problem. I kept looking through my code but I see no problems with it.

Basically, I'm using Floyd Warshall and I iterate through the first row (shortest distance from first node to all other nodes) and I find the maximum. But still WA.

Can someone help me? Thanks!

Code: Select all

#include <iostream>
#include <cmath>
#define INF 1000000000

using namespace std;

int arr[110][110];

int main()
{
	//freopen("in.txt", "r", stdin);
	int n;

	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			arr[i][j] = INF;

	for(int i = 0; i < n; ++i)
	{
		arr[i][i] = 0;
		for(int j = 0; j < i; ++j)
		{
			while(cin.peek() == ' ') cin.get();
			if(cin.peek() == 'x')
			{
				cin.get();
				continue;
			}
			scanf("%d", &arr[i][j]);
			arr[j][i] = arr[i][j];
		}
	}

	for(int k = 0; k < n; ++k)
		for(int i = 0; i < n; ++i)
			for(int j = 0; j < n; ++j)
				arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);

	int mini = 0;
	for(int i = 0; i < n; ++i)
		if(arr[0][i] != INF && mini < arr[0][i])
			mini = arr[0][i];

	printf("%d\n", mini);

	return 0;
}

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 423 - MPI .... please help

Post by mahade hasan » Sun Oct 14, 2012 8:59 pm

Just change ur Line 14 as
while(scanf("%d", &n)==1)
{
your code
}
chears!
we r surrounded by happiness
need eyes to feel it!

melkiy
New poster
Posts: 1
Joined: Thu Nov 07, 2013 1:04 am

Re: 423 - MPI .... please help

Post by melkiy » Thu Nov 07, 2013 1:10 am

Oh, boys, it requires '\n' at the end to get AC!!!

printf("%d\n", answer);

Post Reply

Return to “Volume 4 (400-499)”