496 - Simply Subsets

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

Moderator: Board moderators

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Post by 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
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

Post by aakash_mandhar »

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
Location: Canada

Not Specified

Post by 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
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by 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
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by 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 ???
:evil:

plankton
New poster
Posts: 3
Joined: Sun Sep 11, 2005 11:07 pm

Re: Not Specified

Post by plankton »

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!!

Post by 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
Shihab
CSE,BUET

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by 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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by 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
New poster
Posts: 7
Joined: Tue Jul 25, 2006 2:01 pm
Contact:

496 WA

Post by 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
Trying to reduce complexity of the World.

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

Post by 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...
win

Theorem
New poster
Posts: 2
Joined: Sat Sep 09, 2006 6:39 am

Post by Theorem »

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:

Post by vinit_iiita »

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Can you point to such definition of set?

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by 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

Post Reply

Return to “Volume 4 (400-499)”