496 - Simply Subsets

[sjn]

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]

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]

Hasn't no body solved it? Please help me. I am not sure whether my set definition is ok.

[supermin]

Though this article is too old, maybe it will help somebody.

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]

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]

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]

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;

if (ad == 0)
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;

if (!ad || !bd)
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]

[Partha]

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]

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?

[Hisoka]

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]

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

[Riyad]

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
Riyad

[aakash_mandhar]

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]

[shamim]

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]

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