## 496 - Simply Subsets

Moderator: Board moderators

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

### p496

I got WA for this problem, i don't know why ...
My source code should be OK, it works perfectly ...

we all know A^B=B^A
but my friend told i was wrong
so who can help me

help pls~

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

### 496 - Simply Subsets

I have solved the problem496 and submit it more than 10 times.But i always get wrong answers. I can't understand my problem.Can anybody help me.I get frustated.Is there any data that does not match?Please help me.Here is my code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

main()
{
char *st;
char a[500],b[500];
int i,j,k,l,l1,l2,cnt,c[500],d[500],n,o,p,flag;
while(1)
{
flag=0;
for (i=0;i<500;i++)
a=b=c=d=0;
if (gets(a)==NULL) break;
gets(b);
l=0;

if((a!="") && (b=="")) printf("B is a proper subset of A\n");
else if((a=="") && (b!="")) printf("A is a proper subset of B\n");
else
{
st=strtok(a," \n");
c[l++]=atoi(st);
while(1)
{
st=strtok(NULL," \n");
if(st==NULL) break;
c[l++]=atoi(st);
}

k=0;
st=strtok(b," \n");
d[k++]=atoi(st);
while(1)
{
st=strtok(NULL," \n");
if(st==NULL) break;
d[k++]=atoi(st);
}

cnt=0;
if(l>=k)
{
for (i=0;i<k;i++)
for (j=0;j<l;j++)
{
if(d==c[j])
{
cnt++;
for (n=j;n<l;n++)
if (c[n]==d) c[n]='a';
for (p=i+1;p<k;p++)
if (d[p]==d)
{
cnt++;
flag=1;
d[p]='b';
}

}
}

if(cnt==l && cnt ==k) printf("A equals B\n");
else if(cnt==k ) printf("B is a proper subset of A\n");
else if(cnt==1 || flag==1) printf("I'm confused!\n");
else printf("A and B are disjoint\n");

}

if(l<k)
{
for (i=0;i<l;i++)
for (j=0;j<k;j++)
{
if(c==d[j])
{
cnt++;
for (n=j;n<k;n++)
if (d[n]==c) d[n]='a';

for (p=i+1;p<l;p++)
if (c[p]==c)
{
cnt++;
flag=1;
c[p]='b';
}

}
}

if(cnt==l && cnt ==k) printf("A equals B\n");
else if(cnt==l ) printf("A is a proper subset of B\n");
else if(cnt==1 || flag==1) printf("I'm confused!\n");
else printf("A and B are disjoint\n");

}
}
}
return 0;
}
/* @END_OF_SOURCE_CODE */

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Hasn't no body solved it? Please help me. I am not sure whether my set definition is ok.

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

You should consider this case:

input:
1 1 2 3
1 2 3

output:
A equals B

I think the problem dosen't explain very clearly.
So,it may have some "set" knowledge.

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Thank you very much supermin for your kind reply. I was almost gave up any hope of getting any reply of this topic. I have checked your sample input and corrected my program but it gives me still wrong answer. Can you or anybody give me some more test cases to check my code. I think i do not have to wait so much long getting next reply.

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:
input:
(1)
1
1 1
(2)
1 1
1
(3)
1 1
1 1
(4)

(5)
1

(6)

1
(7)
1 3 2
1 2 3
(8)
1 3 2 1
1 2 3

output:
(5) B is a proper subset of A
(6) A is a proper subset of B
(1),(2),(3),(4),(7),(8)=> equal

ps. I am not sure if the judge will have the tests as the (4),(5),(6).

If you want to check with my source code,you can send me an E-mail.
And I will give you my code. Maybe it will help.

Good luck!

eXon
New poster
Posts: 17
Joined: Sun Mar 23, 2003 2:04 pm
Location: Russia
Contact:

### 496 SOS (Tested many times)

I tested following soluition on such tests:
1
1 1 - A equals B

1
(an empty line) - B is a proper subset of

(an empty line)
(an empty line) A equals B

1 2 2 2 3 3
2 1 1 3 - A equals B

1 2 3
1 3 3 - B is a proper subset of A

1 2
3 4 - A and B are disjoint

1 1 1 2 2
2 2 3 - I'm confused!

Can anybody give me some critical test and/or check my code:
[cpp]
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <fstream.h>
#include <string.h>

#ifndef ONLINE_JUDGE

#include <conio.h>

#endif

int finish;
long caseNo;
#ifdef ONLINE_JUDGE
const long MAX = 200000;
#else
const long MAX = 100;
#endif

typedef long t[MAX];

t a, b;
int ai, bi;

void Input(){
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);

ai = 0;
bi = 0;
int tmp;

finish = cin.eof();
if (finish)
return;
while (cin.peek() != '\n' && !cin.eof()){
cin >> a[ai++];
finish = cin.eof();
if (finish)
return;
}

cin.get();
while (cin.peek() != '\n' && !cin.eof()){
cin >> b[bi++];
if (cin.eof()){
bi--;
return;
}
}
cin.get();
}

int aissubofb(t a, t b, int ad, int bd){
int flag = 1;

return 1;
for (int i = 0; i < ad; i++){
flag = 0;
for (int j = 0; j < bd; j++)
if (a == b[j]) {flag = 1; break;}
if (!flag)
return 0;
}
return 1;
}

int disj(t a, t b, int ad, int bd){
int flag = 1;

return 0;
for (int i = 0; i < ad; i++){
flag = 0;
for (int j = 0; j < bd; j++)
if (a == b[j]) {flag = 1; break;}
if (flag)
return 0;
}
return 1;
}

void Solve(){
if (aissubofb(a, b, ai, bi) && aissubofb(b, a, bi, ai))
cout << "A equals B";else
if (aissubofb(a, b, ai, bi))
cout << "A is a proper subset of B";else
if (aissubofb(b, a, bi, ai))
cout << "B is a proper subset of A";else
if (disj(a, b , ai, bi))
cout << "A and B are disjoint";
else
cout << "I'm confused!";
}

void Output()
{
}

#define DEBUG_
#define MULTIINPUT

int main(){
#ifndef ONLINE_JUDGE
ifstream is = "input.txt";
cin = is;
#ifdef DEBUG
clrscr();
cout << endl;
#else
ofstream os = "output.txt";
cout = os;
#endif
#endif

#ifdef MULTIINPUT
for (caseNo = 0; !finish; caseNo++){
#endif
Input();
#ifdef MULTIINPUT
if (finish)
return 0;
/* if (caseNo)
cout << endl;*/
#endif
Solve();
cout << endl;
Output();
#ifdef MULTIINPUT
}
#endif
return 0;
}
//@END_OF_SOURCE_CODE
[/cpp]
Who am I? Just eXon...

Partha
New poster
Posts: 5
Joined: Fri Mar 28, 2003 8:51 pm
Contact:
I tested my accepted code on those data that u give and found some difference.

1
1 1 - A is a proper subset of B

1 2 2 2 3 3
2 1 1 3 - B is a proper subset of A

1 2 3
1 3 3 - A equals B

Most probably here no blank line is given as a input.

eXon
New poster
Posts: 17
Joined: Sun Mar 23, 2003 2:04 pm
Location: Russia
Contact:

### May be I don't understand

Can anybody explain me from mathematical point of view why 1 3 3 equals to 1 2 3? Set A equals to set B if and only if A is a subset of B and B is a subset of A. May be I don't understand completely a meaning of phrase ``proper subset''. I assume this equals to ``subset''. Can anybody help me?
Who am I? Just eXon...

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
hai, eXon's I/O is true, and I think for this problem the tricky I/O only the blank line. Check your input or your output again, I think (if I'm not wrong, because I don't check your program with specific) your algo is true.

jaywinyeah
New poster
Posts: 19
Joined: Sun Aug 17, 2003 10:40 pm
Doesn't the problem state the the lines are composed of "distinct" integers? Why is everybodies test input contain duplicates?
LL Cool Jay
The Formula Wizard
Jason Winokur
LL Cool Jay
The Formula Wizard
Jason Winokur

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### hey

hey here is some part of my check function . take a look and correct u r mistake . u must also check wither index 1(k in u r code) == index 2(l in u r code).

[c]
void check(){

register int i , j ;
register int flag,nequal=0,equal=0;

if(index1==index2){

for(i=0;i<index1;i++){
flag=0;
for(j=0;j<index2;j++){

if(number_one==number_two[j]){
flag=1;
}

}
if(flag==1){
equal++;
}
else if(flag==0){
nequal++;
}
}

if(nequal==0 && equal==index1){
//removed printf
}

else if((nequal>0 &&nequal<index1) && (equal>0 && equal<index1)){
//removed printf
}

else if(nequal==index1 && equal==0){
//removed printf
}

}

else if(index1<index2){

for(i=0;i<index1;i++){
flag=0;
for(j=0;j<index2;j++){

if(number_one==number_two[j]){
flag=1;
}

}
if(flag==1){
equal++;
}
else if(flag==0){
nequal++;
}
}

if(nequal==0 && equal==index1){
//removed printf
}

else if((nequal>0 &&nequal<index1) && (equal>0 && equal<index1)){
//removed printf
}

else if(nequal==index1 && equal==0){
//removed
}

}

else if(index1>index2){

for(i=0;i<index2;i++){
flag=0;
for(j=0;j<index1;j++){

if(number_one[j]==number_two){
flag=1;
}

}
if(flag==1){
equal++;
}
else if(flag==0){
nequal++;
}
}

if(nequal==0 && equal==index2){
//removed printf
}

else if((nequal>0 &&nequal<index2) && (equal>0 && equal<index2)){
//removed
}

else if(nequal==index2 && equal==0){

//removed
}

}

}[/c]

MoreOver i did not counter the following conditions

1 1 2 3
1 2 3

some one said it must be" A equals B " but
My Output is "B is The proper Sub Set of A" . so there is no test cases where the above things happen. more over no black line is given as input so dont worry about it .

Best Regards
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore
I am having problems with this problem... I have tried out for null inputs also like set 1 = {1,2,3} set2={} then set2 is proper subset of set1..
Please tell me why i am getting WA......

Frustrated
Aakash

[cpp]
# include<stdio.h>
# include<string.h>
# include<math.h>
char a[1000];
long long x[100],y[100];
int ac;

int getline(char *a)
{
char ch;

ch=fgetc(stdin);
if(ch==EOF) return -1;
while(ch!='\n' && ch!='\r')
{
if(ch==EOF) return -1;
a[ac++]=ch;
ch=fgetc(stdin);
}
a[ac]='\0';
return ac;
}

int parse(long long *x,char *a)
{
long long val;
int sign,state,i,l,xc;
l=strlen(a);
state=0;
sign=0;
val=0;
xc=0;
for(i=0;i<l;i++)
{
if(state==0 && (a>='0' && a<='9') || a=='-')
{
if(a=='-') sign=!sign;
else
{
state=1;
val=a-'0';
}
}
else if(state==1 && a>='0' && a<='9')
{
val*=10;
val+=(a-'0');
}
else
{
if(state==1) {x[xc++]=pow(-1,sign)*val;val=0;sign=0;state=0;}
state=0;
}

}
if(state==1) {x[xc++]=pow(-1,sign)*val;val=0;sign=0;state=0;}
return xc;
}

int main()
{
int c1,c2,i,j,match;
long long myval;
while(1)
{
ac=0;
if(getline(a)==-1) return 1;
//printf("%s",a);
c1=parse(x,a);
ac=0;
if(getline(a)==-1) return 1;
c2=parse(y,a);

match=0;
for(i=0;i<c1;i++)
{
for(j=0;j<c2;j++)
{
if(x==y[j]) {match++;break;}
}
}
if(match==c1 && match==c2) printf("A equals B\n");
else if(c1==0 || (match==c1 && c2>match)) printf("A is a proper subset of B\n");
else if(c2==0 || (match==c2 && c1>match)) printf("B is a proper subset of A\n");
else if(match==0) printf("A and B are disjoint\n");
else printf("I'm confused!\n");

//printf("MATCH %d\n",match);
}
}
[/cpp]
...I was born to code...

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
I did not check your algorithm but from what i remember,
the statement
Each line of text (set) will be a list of distinct integers
is misleading as the same line of input actually contains multiple occurance of the same number.

I don't know whether my claim is right, but from the earlier discussion of this thread, this seems to be the case.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
aakash_mandhar wrote:I am having problems with this problem... I have tried out for null inputs also like set 1 = {1,2,3} set2={} then set2 is proper subset of set1..
Please tell me why i am getting WA......
Actually the empty set is defined as improper subset of any set. So probably (I didn't try to solve 496) set2 should be considered disjoint...

Just my 2 cents...

Ciao!!!

Claudio