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
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
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
which part is it incorrect? i get WA too

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
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
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
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

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

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! But I am really confused about why the answer is correct! 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? I am really confused!!
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]

Mg9H
New poster
Posts: 18
Joined: Sun Oct 14, 2001 2:00 am
Location: Ohio University
Contact:
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
It's bellman-ford, not ford-bellman

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:
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:
I think Bellman Ford Algorithm suits well in this problem...

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:
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
Contact:
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:
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?