496  Simply Subsets
Moderator: Board moderators

 New poster
 Posts: 38
 Joined: Thu Dec 11, 2003 3:40 pm
 Location: Bangalore
Not Specified
Hello eXon:
I checked your inputs with my accepted program and did not find any mistake.
But, May be, there is no such input that contain blank lines. Because, I got accepted without considering this.
I checked your inputs with my accepted program and did not find any mistake.
But, May be, there is no such input that contain blank lines. Because, I got accepted without considering this.
1 2 3
1 3 3  A equals B
This answer is wrong. This answer will be B is a proper subset of A.

 New poster
 Posts: 42
 Joined: Sun Jul 31, 2005 2:07 am
 Location: SUST. Bangladesh
 Contact:

 New poster
 Posts: 42
 Joined: Sun Jul 31, 2005 2:07 am
 Location: SUST. Bangladesh
 Contact:
Re: Not Specified
are you sure??Mahmud776 wrote:Hello eXon:
I checked your inputs with my accepted program and did not find any mistake.
But, May be, there is no such input that contain blank lines. Because, I got accepted without considering this.
1 2 3
1 3 3  A equals B
This answer is wrong. This answer will be B is a proper subset of A.
I thought a set should not have any duplicates...
496 WA!!
I'm getting WA 4 this prob. I can't figure out the cause. Can somebody hlp me plz.
Shihab
Code: Select all
#include<stdio.h>
#include<set>
#include<stdlib.h>
using namespace std;
void main(){
int sizea,sizeb,common;
set<int> A,B;
char seta[2000],setb[2000],*p;
bool asubset,bsubset,disjoint,equal;
while(gets(seta)!=NULL){
gets(setb);
A.clear();B.clear();
asubset=bsubset=disjoint=equal=false;
common=0;
p=strtok(seta," ");
A.insert(atoi(p));
while((p=strtok(NULL," "))!=NULL) A.insert(atoi(p));
p=strtok(setb," ");
B.insert(atoi(p));
while((p=strtok(NULL," "))!=NULL) B.insert(atoi(p));
sizea=A.size();sizeb=B.size();
set<int> ::iterator pa,pb;
if(sizea==sizeb){
for(pa=A.begin();pa!=A.end();pa++) if(B.find(*pa)!=B.end()) common++;
if(common==sizea){equal=true;disjoint=asubset=bsubset=false;}
else if(!common){equal=asubset=bsubset=false;disjoint=true;}
}
else if(sizea<sizeb){
for(pa=A.begin();pa!=A.end();pa++) if(B.find(*pa)!=B.end()) common++;
if(common==sizea && common==sizeb1) {asubset=true;bsubset=disjoint=equal=false;}
else if(!common) {disjoint=true;asubset=bsubset=equal=false;}
}
else {
for(pb=B.begin();pb!=B.end();pb++) if(A.find(*pb)!=A.end()) common++;
if(common==sizeb && common==sizea1) {bsubset=true;asubset=disjoint=equal=false;}
else if(!common) {disjoint=true;asubset=bsubset=equal=false;}
}
if(asubset && !bsubset && !equal && !disjoint) puts("A is a proper subset of B");
else if(!asubset && bsubset && !equal && !disjoint) puts("B is a proper subset of A");
else if(!asubset && !bsubset && equal && !disjoint) puts("A equals B");
else if(!asubset && !bsubset && !equal && disjoint) puts("A and B are disjoint");
else if(!asubset && !bsubset && !equal && !disjoint) puts("I'm confused!");
}
}
Shihab
CSE,BUET
CSE,BUET
For this problem, the problem description says "Each line of text (set) will be a list of distinct integers" but that just seems totally invalid. I keep getting WA at first and tried the following:
(1) using long int instead of int  still WA
(2) considering blank line to mean empty set  still WA
(3) considering the possibility that a line may contain duplicate integers  ACCEPTED
So if you keep getting WA, first try tweaking your program to consider duplicates. I think that's the most "tricky' part about this problem.
(1) using long int instead of int  still WA
(2) considering blank line to mean empty set  still WA
(3) considering the possibility that a line may contain duplicate integers  ACCEPTED
So if you keep getting WA, first try tweaking your program to consider duplicates. I think that's the most "tricky' part about this problem.
There seems to be some dispute whether there are duplicates in the input
My AC code did not consider duplicates and got AC. I used gets function to read each set of numbers. You might want to check your subset algorithm.
My approach:
1) For two sets A and B. If A is a subset of B and B is a subset of A then A = B.
2) If A is a subset of B but B is not a subset of A, then A is a proper subset of B.
3) If B is a subset of A but A is not a subset of B, then B is a proper subset of B.
4) Otherwise, the two sets either intersect or are disjoint. Check whether there are common elements between the two sets. If there are none, then the sets A and B are disjoint, else there is a set that contains the elements that lie in the intersection of sets A and B.
My AC code did not consider duplicates and got AC. I used gets function to read each set of numbers. You might want to check your subset algorithm.
My approach:
1) For two sets A and B. If A is a subset of B and B is a subset of A then A = B.
2) If A is a subset of B but B is not a subset of A, then A is a proper subset of B.
3) If B is a subset of A but A is not a subset of B, then B is a proper subset of B.
4) Otherwise, the two sets either intersect or are disjoint. Check whether there are common elements between the two sets. If there are none, then the sets A and B are disjoint, else there is a set that contains the elements that lie in the intersection of sets A and B.

 New poster
 Posts: 7
 Joined: Tue Jul 25, 2006 2:01 pm
 Contact:
496 WA
Hi all,
I am really frustrated, I am always getting WA...... I have tried all the test cases which can be related with a set...... but i m not getting what to do...... please help me......
give me some more test cases so that i can verify my error.....
Please help me.......
thanx
Anupam
I am really frustrated, I am always getting WA...... I have tried all the test cases which can be related with a set...... but i m not getting what to do...... please help me......
Code: Select all
#include<iostream>
#include<set>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
class anupam
{
private:
set<long int> A;
public:
string z;
void initialize()
{
A.clear();
char* b;
char a[z.length()];
for(int i=0;i<z.length();i++)
a[i]=(char)z[i];
b=strtok(a," ");
A.insert(atoi(b));
while((b=strtok(NULL," "))!= NULL)
A.insert(atoi(b));
}
void check(anupam nn)
{
int m=0,n=0;
set<long int>:: iterator anu,pat;
for((anu=(nn.A).begin());anu!=((nn.A).end());anu++)
{
if(A.find(*anu)!=A.end())
n++;
}
for(anu=A.begin();anu!=A.end();anu++)
{
if((nn.A).find(*anu)!=(nn.A).end())
m++;
}
if((n==m)&&(A.size()==((nn.A).size()))&&(A.size()==n))
{
cout<<"A equals B"<<endl;
return;
}
if(((n==A.size())&&(m!=(nn.A).size()))((int)((char)z[0])==0))
{
cout<<"A is a proper subset of B"<<endl;
return;
}
if(((n!=A.size())&&(m==(nn.A).size()))((int)((char)(nn.z[0]))==0))
{
cout<<"B is a proper subset of A"<<endl;
return;
}
if((n==0)&&(m==0))
{
cout<<"A and B are disjoint"<<endl;
return;
}
if((n!=A.size())&&(m!=(nn.A).size()))
{
cout<<"I'm confused!"<<endl;
return;
}
}
};
int main()
{
anupam a,n;
string x;
while(getline(cin,x,'\n'))
{
a.z=x;
getline(cin,x,'\n');
n.z=x;
char f=a.z[0];
char g=n.z[0];
if(((int)f==0)&&((int)g==0))
{
cout<<"A equals B"<<endl;
continue;
}
a.initialize();
n.initialize();
a.check(n);
}
return 0;
}
Please help me.......
thanx
Anupam
Trying to reduce complexity of the World.

 New poster
 Posts: 30
 Joined: Mon Jun 19, 2006 10:37 pm
 Contact:
Code: Select all
for input
9 9
9 9
your output is...
A and B are disjoint
this should be
A is a proper subset of B
win

 New poster
 Posts: 30
 Joined: Mon Jun 19, 2006 10:37 pm
 Contact:
I am certain that judge data for this problem does not have sets that have repetition of elements as my AC code does not take care of that.
Also, I think Theorem is right. Have a look at these two articles:
http://mathworld.wolfram.com/Multiset.html
http://mathworld.wolfram.com/Set.html
Also, I think Theorem is right. Have a look at these two articles:
http://mathworld.wolfram.com/Multiset.html
http://mathworld.wolfram.com/Set.html