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

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

p496

Post by sjn » Thu May 23, 2002 4:19 pm

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 :cry:

help pls~

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

496 - Simply Subsets

Post by yahoo » Thu Jun 06, 2002 5:11 pm

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

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

Post by yahoo » Mon Jun 17, 2002 4:43 pm

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:

Post by supermin » Fri Jan 10, 2003 8:57 pm

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

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

Post by yahoo » Mon Jan 13, 2003 10:47 pm

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. :oops: :oops: :oops: 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. :cry: :cry:

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

Post by supermin » Tue Jan 14, 2003 2:41 am

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)

Post by eXon » Sat Apr 05, 2003 7:00 pm

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]
Who am I? Just eXon...

Partha
New poster
Posts: 5
Joined: Fri Mar 28, 2003 8:51 pm
Location: Bangladesh
Contact:

Post by Partha » Tue Apr 08, 2003 4:44 pm

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

Post by eXon » Tue Apr 08, 2003 4:58 pm

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

Post by Hisoka » Tue Apr 08, 2003 5:36 pm

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

jaywinyeah
New poster
Posts: 19
Joined: Sun Aug 17, 2003 10:40 pm

Post by jaywinyeah » Sat Nov 08, 2003 10:10 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

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

hey

Post by Riyad » Mon Nov 10, 2003 4:25 am

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

Post by aakash_mandhar » Sat Jan 24, 2004 6:59 pm

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Jan 25, 2004 5:55 am

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

Post by CDiMa » Mon Jan 26, 2004 11:36 am

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

Post Reply

Return to “Volume 4 (400-499)”