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

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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;
unsigned long a;

void setP(unsigned long n)
{
unsigned long i;
P=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

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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 Syed Ishtiaque Ahmed Kallol
CSE,BUET

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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 Code: Select all

#include<stdio.h>

unsigned long P;
unsigned long a;

void setP(unsigned long n)
{
unsigned long i;
P=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

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh
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

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

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

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

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,i,j,p,d,t,k,a,b,don,c;
scanf("%d",&t);
don=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;
c=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

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,i,j,p,d,t,k,a,b,don,c;
scanf("%d",&t);
don=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;
c=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
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;
t=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

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 :(

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
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
Can anyone help me to find the wrong? My code is right for all inputs for this problem... 