10959 - The Party, Part I

[Soarer]

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.

[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

[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;
}

[Kallol]

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

[Kallol]

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

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;
}

[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...

[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.

[lovemagic]

I totally overlooked the line D<=p(p-1)/2.But i think they should give me RE in stead of WA.

[Ankur Jaiswal]

I too used BFS.
It's still giving WA.
Can u tell me what u did to solve ur problem?[/code]

[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;
}

[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;
}

[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;              
        }  

[Martin Macko]

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

[renato_ferreira]

Hello, I cant find the error of this code, but I get WA.

Code: Select all

AC

Thank you.

[renato_ferreira]

Can anyone help me to find the wrong? My code is right for all inputs for this problem...