Page 2 of 3

Posted: Sat Nov 19, 2005 11:31 am
by Soarer
ayon wrote:did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).
I am new to C++ so i don't know bfs as well, can you kindly tell me what it is? thanks.

Posted: Sat Nov 19, 2005 7:22 pm
by ayon
bfs is a graph algorithm. You better see your algorithm book for bfs. it is too large to describe in the forum. You cannot understand without proper figure. the procedure and description takes at least 4-5 pages with enough figures. once you learn bfs, many problems(graphs) will be very easy to solve very quickly.

best regards

Posted: Sat Nov 19, 2005 7:46 pm
by Kallol
Yap, bfs does the trick, but i am confused .... whats the prob with my code? I got WA :-?
here is my c code :

#include<stdio.h>


unsigned long P[1010];
unsigned long a[1005][1005];

void setP(unsigned long n)
{
unsigned long i;
P[0]=0;
for(i=1;i<n;i++)
{
P=2000;
}
return;
}

void refresh(unsigned long p)
{
unsigned long i,j;

for(i=0;i<p;i++)
{
for(j=0;j<p;j++)
{
a[j]=0;
}
}
return;
}

void sort(unsigned long p)
{
unsigned long i,j,temp;
for(i=0;i<p;i++)
{
for(j=i+1;j<p;j++)
{
if(P>P[j])
{
temp=P;
P=P[j];
P[j]=temp;
}
}
}
return;
}

void calculate(unsigned long p)
{
unsigned long i,j;
for(i=0;i<p;i++)
{
for(j=0;j<p;j++)
{
if(a[j] && (P+1)<P[j])
{
P[j]=P+1;
}
}
sort(p);
}

return;
}

unsigned long main(void)
{
unsigned long test,tc;
unsigned long p,d;
unsigned long i;
unsigned long r,c;
scanf("%lu",&test);
for(tc=0;tc<test;tc++)
{
scanf("%lu%d",&p,&d);
refresh(p);
setP(p);
for(i=0;i<d;i++)
{
scanf("%lu%d",&r,&c);
a[r][c]=1;
a[c][r]=1;
}
calculate(p);
for(i=1;i<p;i++)
{
printf("%lu\n",P);
}
printf("\n");
}
return 0;
}

Posted: Sat Nov 19, 2005 7:50 pm
by Kallol
Soarer wrote:
ayon wrote:did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).
I am new to C++ so i don't know bfs as well, can you kindly tell me what it is? thanks.
Well , u may use internet to know abou bfs, its not a tough one....the book of Cormen is also cool :D

Posted: Sat Nov 19, 2005 8:09 pm
by Kallol
misof wrote:
Wei-Ming Chen wrote:Oh~ That line is check code. I will delete when I submit it.
And why the outputs are 1 & 2
I thought it was 1 & (can't wrote it)
The order of the dances doesn't matter. Even if 2 danced with 1 before 1 danced with Don Guilianni, the D. G. number of 2 is still 2.
hey my code does print right those two outputs , still WA :cry:

Code: Select all

#include<stdio.h>


unsigned long P[1010];
unsigned long a[1005][1005];

void setP(unsigned long n)
{
	unsigned long i;
	P[0]=0;
	for(i=1;i<n;i++)
	{
		P[i]=2000;
	}
	return;
}

void refresh(unsigned long p)
{
	unsigned long i,j;

	for(i=0;i<p;i++)
	{
		for(j=0;j<p;j++)
		{
			a[i][j]=0;
		}
	}
	return;
}

void sort(unsigned long p)
{
	unsigned long i,j,temp;
	for(i=0;i<p;i++)
	{
		for(j=i+1;j<p;j++)
		{
			if(P[i]>P[j])
			{
				temp=P[i];
				P[i]=P[j];
				P[j]=temp;
			}
		}
	}
	return;
}

void calculate(unsigned long p)
{
	unsigned long i,j;
	for(i=0;i<p;i++)
	{
		for(j=0;j<p;j++)
		{
			if(a[i][j] && (P[i]+1)<P[j])
			{
				P[j]=P[i]+1;
			}
		}
		sort(p);
	}
	
	return;
}

unsigned long main(void)
{
	unsigned long test,tc;
	unsigned long p,d;
	unsigned long i;
	unsigned long r,c;
	scanf("%lu",&test);
	for(tc=0;tc<test;tc++)
	{
		scanf("%lu%d",&p,&d);
		refresh(p);
		setP(p);
		for(i=0;i<d;i++)
		{
			scanf("%lu%d",&r,&c);
			a[r][c]=1;
			a[c][r]=1;
		}
		calculate(p);
		for(i=1;i<p;i++)
		{
			printf("%lu\n",P[i]);
		}
		printf("\n");
	}
	return 0;
}

Posted: Sat Nov 19, 2005 8:13 pm
by ayon
implemention often makes trouble when that can be solved with known algo. try the following input

Code: Select all

4 4
1 2
1 3
0 2
0 3
your program gives

Code: Select all

1
1
2
but it should be

Code: Select all

2
1
1
better try with bfs, that will make your life easier...

10959 - The Party, Part I

Posted: Wed Dec 07, 2005 4:47 pm
by lovemagic
here is my code

Code: Select all


code removed after AC....... :)    

i use bfs.But i donno where is my wrong.Give me sm i/o.

Posted: Wed Dec 07, 2005 6:23 pm
by lovemagic
I totally overlooked the line D<=p(p-1)/2.But i think they should give me RE in stead of WA.

Problem in 10959

Posted: Sat Apr 01, 2006 6:34 am
by Ankur Jaiswal
I too used BFS.
It's still giving WA.:(
Can u tell me what u did to solve ur problem?[/code]

Problem in 10959

Posted: Sat Apr 01, 2006 6:40 am
by Ankur Jaiswal
I too used BFS.
but it is giving WA.
Can smbd help me?
Here is the code-

Code: Select all

#include<stdio.h>
int main(){
        int dance[1000][1000],i,j,p,d,t,k,a,b,don[1000],c[1000];
        scanf("%d",&t);
        don[0]=0;
        for(i=0;i<t;i++){
                scanf("%d%d",&d,&p);
                for(j=0;j<d;j++)
                        for(k=0;k<d;k++)
                                dance[j][k]=-1;
                for(j=0;j<d;j++)
                        don[j]=c[j]=-1;
                for(j=0;j<p;j++){
                        scanf("%d%d",&a,&b);
                        dance[a][b]=dance[b][a]=1;
                }
                j=0,p=1;
                don[0]=0;
                c[0]=0;
                while(j!=d){
                        for(k=0;k<d;k++){
                                if(dance[j][k]==1 && c[k]==-1){
                                        don[p]=k;
                                        p++;
                                        c[k]=c[j]+1;
                                }
                        }
                        j++;
                }
                for(j=1;j<d;j++)
                        printf("%d\n",c[j]);
                printf("\n");
        }
        return 0;
}

10959 - The Party, Part I

Posted: Sat Apr 01, 2006 9:35 am
by Ankur Jaiswal
For this question, i used BFS.
But it's giving WA.
Can smbd help me?
Here is the code :

Code: Select all

#include<stdio.h>
int main(){
        int dance[1000][1000],i,j,p,d,t,k,a,b,don[1000],c[1000];
        scanf("%d",&t);
        don[0]=0;
        for(i=0;i<t;i++){
                scanf("%d%d",&d,&p);
                for(j=0;j<d;j++)
                        for(k=0;k<d;k++)
                                dance[j][k]=-1;
                for(j=0;j<d;j++)
                        don[j]=c[j]=-1;
                for(j=0;j<p;j++){
                        scanf("%d%d",&a,&b);
                        dance[a][b]=dance[b][a]=1;
                }
                j=0,p=1;
                don[0]=0;
                c[0]=0;
                while(j!=d){
                        for(k=0;k<d;k++){
                                if(dance[j][k]==1 && c[k]==-1){
                                        don[p]=k;
                                        p++;
                                        c[k]=c[j]+1;
                                }
                        }
                        j++;
                }
                for(j=1;j<d;j++)
                        printf("%d\n",c[j]);
                printf("\n");
        }
        return 0;
}

Posted: Sun May 07, 2006 6:19 pm
by lovemagic
sorry for late reply.

my bfs approach......
psudocode

Code: Select all

	for(k=0 to inf){
		for(i=0 to num_of_guests_of_(k-1)th_step){
			for(j=0 to D(num_of_dancing_couple) ){
				if(guest_1 of j_th couple alredy marked){
					check if guest_2 alredy marked or not;
				}
				else if(guest_2 of j_th couple alredy marked){
					check if guest_1 alredy marked or not;
				}
			}
		}
	}
here is the bfs-code part....

Code: Select all



        st[0][0]=0;
        t[0]=1;

        for(k=0;;k++){
            t[(k+1)%2]=0;
            for(i=0;i<t[k%2];i++){           
                for(j=0;j<d;j++){
                    if(d1[j]==st[k%2][i]){
                        if(mark[d2[j]]>=mark[d1[j]]+1){
                            mark[d2[j]]=mark[d1[j]]+1;
                            st[(k+1)%2][t[(k+1)%2]++]=d2[j];
                        }    
                    } 
                    else if(d2[j]==st[k%2][i]){
                        if(mark[d1[j]]>=mark[d2[j]]+1){
                            mark[d1[j]]=mark[d2[j]]+1;
                            st[(k+1)%2][t[(k+1)%2]++]=d1[j];
                        }  
                    }      
                }    
            } 
            if(t[(k+1)%2]==0)break;              
        }  



Re: 10959 The Party Part I.... Getting WA :(

Posted: Sat Aug 12, 2006 9:54 pm
by Martin Macko
Ankur Jaiswal wrote:For this question, i used BFS.
But it's giving WA.
Can smbd help me?
Here is the code :
Your code isn't working for

Code: Select all

1

5 5
0 1
1 2
2 3
3 4
0 4
The correct output:

Code: Select all

1
2
2
1

Posted: Tue Jul 17, 2007 12:05 am
by renato_ferreira
Hello, I cant find the error of this code, but I get WA.

Code: Select all

AC
Thank you.

Posted: Tue Jul 17, 2007 4:38 pm
by renato_ferreira
Can anyone help me to find the wrong? My code is right for all inputs for this problem... :(