558 - Wormholes

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

Moderator: Board moderators

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sun Dec 23, 2001 12:00 pm

Is there any tricks in this problem? I keep on getting "Memory limit exceeded", but I have checked my array time and again and found no problem! Is there any other reason for memory limit exceeded?

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Mon Dec 24, 2001 5:48 am

Nvm, I solved the problem using pointers... but that also means that the problem description is not correct...

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Wed Dec 26, 2001 8:33 am

which part is it incorrect? i get WA too

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Thu Dec 27, 2001 7:52 am

I think the limits for the number of wormholes or star systems are wrong, because when I used arrays, I got "Memory Limit Exceeded". However, when I turned to malloc, I got accepted. That should be all the problems that I faced. If you still don't get accepted, maybe you could reply to this thread and I will see how I can help you.

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Sat Dec 29, 2001 11:06 am

thanks for your help.

i think the input is 1<=n<=1000, and 0<=m<=2000. anyway, one question is,

is that you have to find a loop <0 that must be started with system 0? or any loop will output 'possible'?

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Mon Dec 31, 2001 5:54 am

The loop wil have to start at 0, but the loop does not have to include 0. Eg:

1
4 4
0 1 10
1 2 20
2 3 30
3 1 -1000

Here the loop is from 1 2 3 1 2 3..., but 0 is the starting point.

j0rdi
New poster
Posts: 6
Joined: Sun May 04, 2003 10:52 am

558

Post by j0rdi » Tue May 06, 2003 5:59 pm

I get all times Wrong Answer(WA), but i can't find where is the error. Someone can help me.

Here is my code in C.

[c]#include <stdio.h>

struct nodo
{
int val;
int dist;
struct nodo *sig;
};


struct nodo *a[1000], *z;
int aa[1000];


void inicializar(int n_stars,int n_worm)
{
int i;
int x,y,d;
char line[80];
struct nodo *t;

z=(struct nodo *)malloc(sizeof(struct nodo));
z->sig=z;

for(i=0; i<n_stars;i++)
{
aa=0;
}
for(i=0; i<n_stars;i++)
{
a=z;
}

for (i=0; i<n_worm; i++)
{
gets(line);
sscanf(line,"%d %d %d",&x,&y,&d);
t=(struct nodo *)malloc(sizeof(struct nodo));
aa[y]=1;
t->val=y; t->dist=d; t->sig=a[x]; a[x]=t;
}
}

int find_cycle(int n_stars)
{
int i=0;
int j=0;
int find=0;


while(i<n_stars && find!=1)
{
if(aa==1)
{
find=tract_starsyst(a,i,0);
for(j=0;j<n_stars;j++)
{
if (aa[j]==2)
{
aa[j]=1;
}
}
}
i++;

}
return(find);
}

int tract_starsyst(struct nodo *t,int orig, int time)
{

int temps;
int trobat=0;
int j;
struct nodo *aux;


temps=time;

aux=t;

while (aux!=z && aa[aux->val]!=2 && trobat!=1)
{

aa[aux->val]=2;
if (aux->val==orig)
{
temps=temps+aux->dist;
if(temps<0)
{
trobat=1;
}
}
else
{
temps=temps+aux->dist;
trobat=tract_starsyst(a[aux->val],orig,temps);
}
aux=aux->sig;
}


return(trobat);
}


main (int argc,char *arv[])
{

int indx=0;
int i;
char line[80];
int n_cases;
int n_stars_system=0;
int n_wormholes=0;
int possible=0;


gets(line);
sscanf(line,"%d",&n_cases);

for(i=0;i<n_cases;i++)
{
gets(line);
sscanf(line,"%d %d",&n_stars_system,&n_wormholes);
inicializar(n_stars_system,n_wormholes);

if (find_cycle(n_stars_system)==1)
{
printf("possible\n");
}
else
{
printf("not possible\n");
}
}
}[/c]

jai166
New poster
Posts: 10
Joined: Mon May 12, 2003 11:10 am

558

Post by jai166 » Tue Sep 23, 2003 6:58 am

The following is the way I count the path......
[c]/*for(k=0;k<maxwarm-1;k++)*/
for(i=0;i<maxstar;i++)/* Step */
for(j=0;j<maxstar;j++)/* End */
if(len[0][j]>len[0]+len[j])
len[0][j]=len[0]+len[j];[/c]

Actually, I Accepted! :D But I am really confused about why the answer is correct! :o In my opinion, this loop should be done by N-2 times.

After that, I check if there is negative path......
[c] for(pass=1,i=0;i<maxstar&&pass;i++)/* Step */
for(j=0;j<maxstar&&pass;j++)/* End */
if(len[0][j]>len[0]+len[j])pass=0;[/c]


Could you do me a favor? :D I am really confused!! :o
The following is my source code:
[c]/* 558 Wormholes */
#include<stdio.h>
#define MAX 1000
#define MAXNUM 10000000
int len[MAX][MAX];

void main(void)
{
int i,j,k,maxstar,maxwarm,x,y,t;
unsigned int alltimes;
unsigned char pass;

scanf("%ld",&alltimes);
while( alltimes ){
alltimes--;
scanf("%d%d",&maxstar,&maxwarm);
/* Set First Value - MAXNUM */
for(i=0;i<maxstar;i++)
for(j=0;j<maxstar;j++)
len[j]=MAXNUM;

/* Input */
for(i=0;i<maxwarm;i++){
scanf("%d%d%d",&x,&y,&t);
len[x][y]=t;
}

/*for(k=0;k<maxwarm-1;k++)*/
for(i=0;i<maxstar;i++)/* Step */
for(j=0;j<maxstar;j++)/* End */
if(len[0][j]>len[0]+len[j])
len[0][j]=len[0]+len[i][j];

for(pass=1,i=0;i<maxstar&&pass;i++)/* Step */
for(j=0;j<maxstar&&pass;j++)/* End */
if(len[0][j]>len[0][i]+len[i][j])pass=0;

if(pass)puts("not possible");
else puts("possible");
}
}[/c]

User avatar
Mg9H
New poster
Posts: 18
Joined: Sun Oct 14, 2001 2:00 am
Location: Ohio University
Contact:

Post by Mg9H » Thu Nov 24, 2005 1:38 pm

It's a little late for replying this but your algorithm works correctly because

the first loop is a Ford-Bellman loop, which works perfectly in graph with negative edges but no negative cycle.

Since Ford-Bellman algorithm broke when graphs have negative cycle (by "broke", i mean the minimum distance can still be decreased), the second loop repeat Ford-Bellman again to see if it broke or not. If it did, there's at least 1 negative cycle in some path from 0 to some node, which means the answer is "possible".

Thank you very much for posting this question, i cannot solve this one within the time-limit and your code made me recall this interesting property of Ford-Bellman ;)

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Post by roticv » Tue Nov 29, 2005 5:03 pm

It's bellman-ford, not ford-bellman :D

User avatar
Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

Post by Ming Han » Fri Mar 03, 2006 5:04 pm

What algorithm is recommended?
Bellman-Ford or Floyd Warshall?
:: HanWorks ::

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Jun 04, 2006 8:56 pm

I think Bellman Ford Algorithm suits well in this problem... :D

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Wed May 02, 2007 4:11 pm

what's wrong with the judge?

when i set INFINITY as "20000000" and got AC
when i set INFINITY as "2000000" and got WA

any suggestion?

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

Post by Jan » Wed May 02, 2007 7:35 pm

sjn wrote:what's wrong with the judge?

when i set INFINITY as "20000000" and got AC
when i set INFINITY as "2000000" and got WA

any suggestion?
So, there are values in the judge input for which your calculation result is greater than 2000000.
Ami ekhono shopno dekhi...
HomePage

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Thu May 03, 2007 4:35 am

Jan wrote:
sjn wrote:what's wrong with the judge?

when i set INFINITY as "20000000" and got AC
when i set INFINITY as "2000000" and got WA

any suggestion?
So, there are values in the judge input for which your calculation result is greater than 2000000.
But the thing is that
1: the description of input says the value of t (time) is between -1000 and 1000;
2: when i set INFINITY as "20000" and got AC

strange? :-? :-? :-?

Post Reply

Return to “Volume 5 (500-599)”