10583 - Ubiquitous Religions

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

Moderator: Board moderators

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

10583 - Ubiquitous Religions

Post by rotoZOOM » Mon Jan 12, 2004 9:34 am

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.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Mon Jan 12, 2004 10:49 am

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Jan 13, 2004 1:46 pm

Ya, look up "Union-Find".

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

10583

Post by Eduard » Thu Jan 22, 2004 5:36 pm

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]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

10583

Post by lord_burgos » Mon Feb 02, 2004 2:54 am

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]

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Re: 10583

Post by horape » Mon Feb 02, 2004 6:56 am

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

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Tue Feb 03, 2004 4:52 am

Was it Spanish? ;-) Or Espaniol :D

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Tue Feb 03, 2004 5:29 am

Dmytro Chernysh wrote:Was it Spanish? ;-) Or Espaniol :D
Yes. Espa

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Tue Feb 03, 2004 5:47 am

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

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Tue Feb 03, 2004 6:38 am

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

rlatif119
New poster
Posts: 16
Joined: Mon Mar 01, 2004 4:00 pm
Location: Dhaka

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

Post by rlatif119 » Mon May 24, 2004 10:01 am

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]

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Fri May 28, 2004 4:09 pm

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

Silverfox03
New poster
Posts: 6
Joined: Fri Aug 27, 2004 4:05 pm

10583 WA, help!

Post by Silverfox03 » Fri Aug 27, 2004 4:18 pm

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!

Silverfox03
New poster
Posts: 6
Joined: Fri Aug 27, 2004 4:05 pm

My algo

Post by Silverfox03 » Sat Aug 28, 2004 12:43 am

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?

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Thu Jun 02, 2005 9:32 pm

There may also be a pair where i == j, so a pair of the same student. :wink:

Post Reply

Return to “Volume 105 (10500-10599)”