10959 - The Party, Part I

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

Moderator: Board moderators

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Post by Soarer » Sat Nov 19, 2005 11:31 am

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.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sat Nov 19, 2005 7:22 pm

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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Nov 19, 2005 7:46 pm

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;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Nov 19, 2005 7:50 pm

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
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Nov 19, 2005 8:09 pm

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;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sat Nov 19, 2005 8:13 pm

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...
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

10959 - The Party, Part I

Post by lovemagic » Wed Dec 07, 2005 4:47 pm

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.
Last edited by lovemagic on Wed Dec 07, 2005 6:24 pm, edited 1 time in total.
khobaib

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Wed Dec 07, 2005 6:23 pm

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

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Problem in 10959

Post by Ankur Jaiswal » Sat Apr 01, 2006 6:34 am

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

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Problem in 10959

Post by Ankur Jaiswal » Sat Apr 01, 2006 6:40 am

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
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

10959 - The Party, Part I

Post by Ankur Jaiswal » Sat Apr 01, 2006 9:35 am

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
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Sun May 07, 2006 6:19 pm

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


khobaib

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

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

Post by Martin Macko » Sat Aug 12, 2006 9:54 pm

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

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Tue Jul 17, 2007 12:05 am

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

Code: Select all

AC
Thank you.
Last edited by renato_ferreira on Wed Jul 18, 2007 12:20 am, edited 1 time in total.

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Tue Jul 17, 2007 4:38 pm

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

Post Reply

Return to “Volume 109 (10900-10999)”