496 - Simply Subsets

[pavelph]

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]

Thx everyone for the help but i got ac...

Aakash

[Mahmud776]

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.

[Nazmul Quader Zinnuree]

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

[Nazmul Quader Zinnuree]

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]

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]

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

[stcheung]

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]

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]

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.....
Please help me.......

thanx
Anupam

[vinit_iiita]

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

hope it will help you...

[Theorem]

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]

definition of set does not prohibit repeatition of elements...

[Darko]

Can you point to such definition of set?

[chunyi81]

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