## 496 - Simply Subsets

Moderator: Board moderators

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg
I have AC on this problem and if you want I can help you:
give me some inputs and I will give you right outputs.
aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore
Thx everyone for the help but i got ac...

Aakash
...I was born to code...
Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am

### 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.
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
Contact:
What is going on ???
Each line of text (set) will be a list of distinct integers.
No set will contain the same integer twice...

Now, is there anybody to supply me some valid I/O..
That's all
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:
Thousands of thinkings are just moving on ???
Nobody knows the actual solution...???
Is the description wrong or the judge or we ???
any body who got AC, plz....
describe the the problem, what does it want ???
plankton
New poster
Posts: 3
Joined: Sun Sep 11, 2005 11:07 pm

### Re: Not Specified

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.
are you sure??

I thought a set should not have any duplicates...
shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

### 496 WA!!

I'm getting WA 4 this prob. I can't figure out the cause. Can somebody hlp me plz.

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==sizeb-1) {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==sizea-1) {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
Shihab
CSE,BUET
stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:
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.
chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
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.
Anupam Pathak
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......

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

``````
give me some more test cases so that i can verify my error.....

thanx
Anupam
Trying to reduce complexity of the World.
vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

Code: Select all

``````for input
-9 -9
9 -9

A and B are disjoint

this should be

A is a proper subset of B
``````
win
Theorem
New poster
Posts: 2
Joined: Sat Sep 09, 2006 6:39 am
vinit_iiita wrote: for input
-9 -9
9 -9
A set contains unique elements. It cannot have (by definition) -9 listed twice. So I guess this case can't be tested.
vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:
definition of set does not prohibit repeatition of elements...
win
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am