Page 1 of 3

10583 - Ubiquitous Religions

Posted: Mon Jan 12, 2004 9:34 am
by rotoZOOM
Hi !

This problem very simple. It was easiest on online contest.
But I don't understand how to solve it.
In order to merge two groups of the same religions we have to O(N^2) algo. But N can be 50000, so I can't use this algorithm.

Posted: Mon Jan 12, 2004 10:49 am
by Andrey Mokhov
Hello!

You needn't O(N^2) operations to merge two groups. O(N) is enough, I suppose.
And moreover when you merge two groups you have to attach the smaller one to the bigger one. :wink:

All this results in O(NlogN) algorithm.

Have AC. :P
Andrey.

Posted: Tue Jan 13, 2004 1:46 pm
by Larry
Ya, look up "Union-Find".

10583

Posted: Thu Jan 22, 2004 5:36 pm
by Eduard
Ithing this is a problem which whant to find how many components does the graph have.Am i wrong???
if not then tell me why this program gets WA.
[pascal]label 1;
var a,u,v:array[1..50000] of longint;
i,j,k,n,m,number:longint;
procedure kap(var k:longint);
var i,j,p:longint;
f:boolean;
s:array[1..50000] of longint;
begin
k:=0;
for i:=1 to 50000 do
s:=0;
for p:=1 to n do
if s[p]=0 then
begin
k:=k+1;
s[p]:=k;
repeat
f:=true;
for i:=1 to n do
if s=k then
for j:=1 to m do
if (u[j]=i) and (s[v[j]]<>k) then begin s[v[j]]:=k;f:=false; end else
if (v[j]=i) and (s[u[j]]<>k) then begin s[u[j]]:=k;f:=false; end;
until f=true;
end;
end;
begin
number:=0;
repeat
for i:=1 to 50000 do
begin u:=0;v:=0;end;
number:=number+1;
read(n,m);
if (m=0) and (n=0) then goto 1;
for i:=1 to m do
read(u,v);
kap(k);
writeln('Case ',number,': ',k);
until (m=0) and (n=0);
1:
end.
[/pascal]

10583

Posted: Mon Feb 02, 2004 2:54 am
by lord_burgos
No entiendo por que es WA, creo que el problemas se resuelve de este modo.

1) si los dos numero que te dan no pertenecen a una religion se marcan como una nueva religion
2) Si uno no tiene religion y el otro si , entoces , al que no tiene religion pertenece a la religion del otro
y 3) si los dos tiene religion y no son de la misma, entoces eliminamos una por que no hay razon para contarla, ya que estas dos son la misma

Mi codigo:
[cpp]
# include <stdio.h>
# define N 50000

long a[N+1];
char b[N+1];

main(){
long n, m, i, j, k, x, y,min , max,set=0;
while(scanf("%ld %ld",&n,&m) != EOF && (n || m)){
printf("Case %ld:",++set);
for(i=0;i<=N;i++) b = a = 0;
k = 1;
for(i=0;i<m;i++){
scanf("%ld %ld",&x,&y);
if(!a[x] && !a[y]) a[x] = a[y] = ++k;
else
if((!a[x] && a[y])||(!a[y] && a[x])) a[x] = a[y] =(a[x] > a[y])?a[x]:a[y];
else
if(a[x] != a[y]){
max =(a[x] > a[y])?a[x]:a[y];
b[max] = 1;
}
}
k = 0;
for(i=1;i<=n;i++)
if(a && !b[a]){ k++; b[a]=1;}
else if(!a) k++;

printf(" %ld\n",k);
}
return 0;
}

[/cpp]

Re: 10583

Posted: Mon Feb 02, 2004 6:56 am
by horape
El idioma de este foro es ingles, por favor trata de usarlo.


lord_burgos wrote:No entiendo por que es WA, creo que el problemas se resuelve de este modo:

...
Prueba con:

Code: Select all

20 20
12 4
6 11
17 7
10 7
7 17
10 16
14 16
19 15                                                                                                         10 13
9 17                                                                                                          18 2
10 12                                                                                                         8 18
9 19
9 15                                                                                                          17 8
5 15                                                                                                          12 17
19 11
4 3
0 0
El resultado correcto es 3, tu programa da 4.

Saludos,
HoraPe

Posted: Tue Feb 03, 2004 4:52 am
by Dmytro Chernysh
Was it Spanish? ;-) Or Espaniol :D

Posted: Tue Feb 03, 2004 5:29 am
by horape
Dmytro Chernysh wrote:Was it Spanish? ;-) Or Espaniol :D
Yes. Espa

Posted: Tue Feb 03, 2004 5:47 am
by Dmytro Chernysh
However, we all should post here English and only English! :-)
Moreover, you are a member of Algorithmic Team... so you should give good examples :D

Posted: Tue Feb 03, 2004 6:38 am
by horape
Dmytro Chernysh wrote:However, we all should post here English and only English! :-)
Moreover, you are a member of Algorithmic Team... so you should give good examples :D
Yes, english is to be preferred, and that's what my reply said, but it is corteous to answer in the same language that the question was done.

If you like, i'll edit my post and add a translation.

Saludos,
HoraPe

10583....WA.....sample input needed

Posted: Mon May 24, 2004 10:01 am
by rlatif119
I think my algorithm to solve this problem is very simple and correct (i hope). :roll: but it generates WA. :roll: can someone please help me finding the problem or giving me more sample input so i can check.
Here is my code

[c]

#include<stdio.h>

void religion_count(long n,long m);

long tot;
main()
{
long i,j,n,m;
while(1)
{
scanf("%ld%ld",&n,&m);
if(n==0 && m==0)
break;
religion_count(n,m);
}

}


void religion_count(long n,long m)
{
long rel[50000],i,j,s1,s2,count;

for(i=0;i<n;++i)
rel=0;
count=0;

for(i=0;i<m;++i)
{
scanf("%ld%ld",&s1,&s2);
if(rel[s1-1]!=0)
rel[s2-1]=rel[s1-1];
else if(rel[s2-1]!=0)
rel[s1-1]=rel[s2-1];
else if(rel[s1-1]==0 && rel[s2-1]==0)
rel[s1-1]=++count; rel[s2-1]=count;
}
if(n==0)
printf("Case %ld: 0\n",++tot);
else if(m==0)
printf("Case %ld: %ld\n",++tot,n);
else
{
for(i=0;i<n;++i)
if(rel==0)
++count;

printf("Case %ld: %ld\n",++tot,count);
}
}[/c]

Posted: Fri May 28, 2004 4:09 pm
by angga888
Hi,

Try this input:
4 3
1 2
3 4
1 3
0 0
Output should be 1, but I think your program will output 2.


Anggakusuma

10583 WA, help!

Posted: Fri Aug 27, 2004 4:18 pm
by Silverfox03
My Code:
[cpp]
#include <iostream.h>
#include <fstream.h>

#ifdef ONLINE_JUDGE
istream &fin=cin;
#else
ifstream fin("10583.in");
#endif

void Judge(long int rel[2],long int group[50001],long int rels[50001][2],long int *p,long int *g,long int *r)
{
if (group[rel[0]]==0&&group[rel[1]]==0)
{
(*p)+=2;
(*g)++;
group[rel[0]]=group[rel[1]]=*g;
}
else if (group[rel[0]]!=0&&group[rel[1]]==0)
{
(*p)++;
group[rel[1]]=group[rel[0]];
}
else if (group[rel[0]]==0&&group[rel[1]]!=0)
{
(*p)++;
group[rel[0]]=group[rel[1]];
}
else if (group[rel[0]]!=group[rel[1]])
{
rels[*r][0]=group[rel[0]];
rels[*r][1]=group[rel[1]];
(*r)++;
}
}

void Print(long int c,long int num)
{
cout<<"Case "<<c<<": "<<num<<endl;
}

main()
{
long int group[50001],rel[50001][2],n,m,p,g,r,num,i,c,t[2];

fin>>n>>m;
c=0;
while (!(n==0&&m==0))
{
c++;
p=g=r=0;
num=n;
for (i=0;i<n+1;i++)
group=0;
for (i=0;i<m;i++)
{
fin>>t[0]>>t[1];
Judge(t,group,rel,&p,&g,&r);
}
num=num-p+g;
while (r!=0)
{
for (i=0;i<g+1;i++)
group=0;
m=r;
p=g=r=0;
for (i=0;i<m;i++)
Judge(rel,group,rel,&p,&g,&r);
num=num-p+g;
}
Print(c,num);
fin>>n>>m;
}

return 0;
}
[/cpp]

I know my algo maybe strange, but I think it's right.
Can someone help me, or give me some input?
Thanks!

My algo

Posted: Sat Aug 28, 2004 12:43 am
by Silverfox03
My algo is:
read pair(x,y)
1.if neither of x and y is labeled
person+2;(person is the number of person that I have visited)
group++;(group is the number of groups)
label x and y with group;
2.if one of them is labeled and another isn't
person++;
make them label the same
3.if both of them are labeled but have different group number
record their group number for a new pair

After I check all the original pairs, there are a lot of pairs left that created by step 3. I regard a group as a person, and do above again. By this, I finish the union of different group.
What's wrong with it?

Posted: Thu Jun 02, 2005 9:32 pm
by N|N0
There may also be a pair where i == j, so a pair of the same student. :wink: