OJ Board

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~

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 */

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

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.

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.

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!

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]

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.

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?

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.

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

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

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

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