496 - Simply Subsets

[anne0604]

The problem discription does not specified the input very clear, so I assumed that use an EOF as end of verification...

My code do terminate successfully, but the result always turns out to be TLE...

Is it becasuse my algorithm is too slow or because my code could not end??

thx.

[ayeshapakhi]

take input simply as..

Code: Select all

while( gets(tempA) )
{
       gets(tempB);
}

though after resolving tle u'll get wa...
ur program doesn't produce right ans for the test i/o..

[anne0604]

Thank you very much. I've remodified my code as you suggested and now I can get correct answers with test I/O.

But still I get TLE......

I really don't understand which part of my code leads to this result

Here is my new code.

Code: Select all

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

int A[10000];
int B[10000];
char *tempA;
char *tempB;
int **LCS_Table;

void Parse_Input(char *temp, int *target, int *length);
void Quicksort(int *A, int p, int r);
int Partition(int *A, int p, int r);
int Find_LCS(int i, int j);
int MAX(int a, int b);

int main()
{
    int lengthA;
    int lengthB;

    tempA = (char *)calloc(sizeof(char), 100);
    tempB = (char *)calloc(sizeof(char), 100);
    while(gets(tempA))
    {
        gets((tempB));
        
        lengthA = 1;
        lengthB = 1;
        Parse_Input(tempA, A, &lengthA);
        Parse_Input(tempB, B, &lengthB);
        lengthA--;
        lengthB--;

        free(tempA);
        free(tempB);
        tempA = (char *)malloc(100 * sizeof(char));
        tempB = (char *)malloc(100 * sizeof(char));

        Quicksort(A, 1, lengthA);
        Quicksort(B, 1, lengthB);
        LCS_Table = (int **)malloc((lengthA + 1) * sizeof(int *));

        int i;
        for(i=0; i<=lengthA; i++)
            LCS_Table[i] = (int *)malloc((lengthB + 1) * sizeof(int));
            
        int j;
        for(i=0; i<=lengthA; i++)
            for(j=0; j<=lengthB; j++)
                LCS_Table[i][j] = -1;

        int a = Find_LCS(lengthA, lengthB);
        
        if(!a)
            printf("A and B are disjoint\n");
        else if(a == lengthA)
        {
            if(a == lengthB)
                printf("A equals B\n");
            else if(a > lengthB)
                printf("B is a proper subset of A\n");
            else
                printf("A is a proper subset of B \n");
        }
        else if(a == lengthB)
        {
            if(a == lengthA)
                printf("A equals B\n");
            else if(a > lengthA)
                printf("A is a proper subset of B \n");
            else
                printf("B is a proper subset of A\n");
        }
        else
            printf("I'm confused!\n");
        

    }

    return 0;
}

void Parse_Input(char *temp, int *target, int *length)
{
    //printf("strlen(temp) = %d\n", strlen(temp));
    temp[strlen(temp)+1] = ' ';
    temp[strlen(temp)+2] = '\0';
    char *pch;
    pch = strtok (temp, " ");
    while (pch != NULL)
    {
        target[*length] = atoi(pch);
        (*length)++;
        //printf ("%s\n",pch);
        pch = strtok(NULL, " ");
    }

}

void Quicksort(int *A, int p, int r)
{
    if(p < r)
    {
        int q = Partition(A, p, r);
        Quicksort(A, p, q);
        Quicksort(A, q+1, r);
    }
}

int Partition(int *A, int p, int r)
{
    int x = *(A+p);
    int i = p - 1;
    int j = r + 1;
    int temp;
    while(1)
    {
        while(1)
        {
            j--;
            if(*(A+j) <= x)
                break;
        }
        while(1)
        {
            i++;
            if(*(A+i) >= x)
                break;
        }
        if(i < j)
        {
            temp = *(A+i);
            *(A+i) = *(A+j);
            *(A+j) = temp;
        }
        else
        {
            return j;
        }
    }
}




int Find_LCS(int i, int j)
{
    if(LCS_Table[i][j] > 0)
        return LCS_Table[i][j];
    else
    {
        if(!i || !j)
            LCS_Table[i][j] = 0;
        else if(A[i] == B[j])
        {
            LCS_Table[i][j] = Find_LCS(i-1, j-1) + 1;
        }
        else
        {
            LCS_Table[i][j] = MAX(Find_LCS(i-1, j), Find_LCS(i, j-1));
        }
            
        return LCS_Table[i][j];
    }
}

int MAX(int a, int b)
{
    if(a > b)
        return a;
    else
        return b;
}

Thanks for your help again.

[little joey]

Just some remarks:

- Why do you use calloc/malloc instead of proper (static) arrays? Although some people strongly disagree with me on this point, I advise against using these if you are a beginning programmer. Looking at your code, I see several mallocs that aren't matched with frees, which is very bad programming.

- You use your own quicksort, which is ok in principle, but it can perform very badly on certain types of input. I would use the built in qsort() instead because it is sure to contain no bugs and is fast in all circumstances.

- Most importantly: why do you actually reconstruct the Longest Common Subsequence? This is really time-consuming and not necessary to solve the problem. If you have the already sorted sequences A:(1,1,1,3,3,5,5,5,5) and B:(1,1,2,3,3,5,5,5,5,5), you can immediately see that sequence A can not be a subsequence of B, because A contains 3 ones and B only 2. Also B can't be a subsequence of A, because it contains 5 fives, and A only 4. Think about it.

This problem is quite underspecified because it doesn't give the input ranges, which makes it a bit difficult to set up the right data types. But a little experimenting should solve that problem.

[mf]

built in qsort() [...] is fast in all circumstances.

Not all qsort()'s implementations, unfortunately. Some easily go quadratic on specially constructed input :(
C++, on the other hand, has std::sort() in its library which guarantees O(n log n) running time in the worst case.

[hamedv]

the value of the numbers is not more than 1,000,000

[anne0604]

Thank's for your help. I've modified my code as you guys suggested
Especially little joey, I really appreciate your suggestions, they made me calm and rethought about my programming skill, instead of just being panic about failing the test....



However.......I STILL GOT TLE................

[little joey]

Either put your new code on the forum, or send it to me via PM, and I'll see what I can do.

[Phocasia]

I try to solve this problem many times but I still got WA.
Can anybody help me what my code is wrong.

Code: Select all

Delete after AC

[lazyboy]

Pls help me....
what should be the right ans of the following input:
1 1
1

1 2 2 3
1 2 3

[blank]
1

[blank]
[blank]

1 2 3
1 3 3

pls help.
i have got WA for several times....

[MRH]

PLZ HELP ME
20 TIMES I GET WA
PLZ SAY ME WHERE IS MY WRONG


//WA.............
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#define max 1000000
using namespace std;
long i,j,k,l,m,n,lod[max+1],lod1[max+1],sum,t,t1,temp[max+1],temp1[max+1],ss,s;
char str[max+1],str1[max+1];
int main()
{
while(gets(str))
{
gets(str1);
t=strlen(str);
t1=strlen(str1);
j=0;
sum=0;
for(i=0;i<t;i++)
{
if(str==' ')
{
lod[j++]=sum;
sum=0;
}
else
{
sum=sum*10+str-48;
}
}
lod[j++]=sum;
sum=0;
k=0;
for(i=0;i<t1;i++)
{
if(str1==' ')
{
lod1[k++]=sum;
sum=0;
}
else
{
sum=sum*10+str1-48;
}
}
lod1[k++]=sum;
sum=0;
sort(lod,lod+j);
sort(lod1,lod1+k);
s=0;
for(i=0;i<j;i++)
{
if(lod!=lod[i+1])
{
temp[s++]=lod;

}
}
ss=0;
for(i=0;i<k;i++)
{
if(lod1!=lod1[i+1])
{
temp1[ss++]=lod1;

}
}
l=s+ss;
vector<long>v(l);
vector<long>::iterator it;
it=set_intersection (temp,temp+s,temp1,temp1+ss,v.begin());
if( (it-v.begin())==0 && (t!=0 && t1!=0))
{
cout<<"A and B are disjoint"<<endl;
}
else if( (it-v.begin())==1 && (t!=0 && t1!=0))
{
cout<<"I'm confused!"<<endl;
}
else if( (it-v.begin())== s && (it-v.begin()==ss) || (t1==0 && t==0))
{
cout<<"A equals B"<<endl;
}
else
{
if(t && j>k)
{
cout<<"B is a proper subset of A"<<endl;
}
if(t1 && j<k)
{
cout<<"A is a proper subset of B"<<endl;
}
}
}

return 0;
}

[sohel]

#1. Search the board first. The 'search' option is on the top right of the screen.
#2. There are other threads related to this problem (496). Don't create a new thread for a problem that already exists. Make your post in an existing thread.
#3. Use Code Tags.
#4. Do not use capital letters throughout your post.

[calicratis19]

Each line of text (set) will be a list of distinct integers.

there is no repeated integers in a line in the input.

to check for correct output u can go to

http://www.uvatoolkit.com/problemssolve.php

[obbY]

Please someone help me!! I'm really frustrated with this problem, I tried all kind of input and it seems to work fine but still I get WA, even considering duplicate numbers in the same set! I post my code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUF 500
#define equal 1
#define conf 2
#define disj 3
#define B_sub_A 4
#define A_sub_B 5

int compare(const void *a, const void *b)		
{																
	return (*(int*)a - *(int*)b);	
}		
int* removeDuplicates(int* set, int* len)
{
	int i, j;
	int* arr = malloc(sizeof(int)*BUF);
	
	arr[0] = set[0];
	
	for(i=1, j=1;i<*len;i++) {	
		while(set[i] == set[i-1] && i < *len) i++;
		if(i >= *len) break;
		arr[j] = set[i];
		j++;
	}

	*len = j;
	return arr;		
}
int compare_sets(int set_a[], int len_a, int set_b[], int len_b)
{
	int i, j, count;
	
	set_a = removeDuplicates(set_a, &len_a);
	set_b = removeDuplicates(set_b, &len_b);
	
	if(len_a == len_b) {
		count = 0;
		for(i=0; i<len_a; i++) {
			if(set_a[i] == set_b[i]) count++;	
		}
		if(count == len_a) return equal; /* set A equals B */
		else {
			count = 0;
			for(i=0;i<len_a;i++) {
				for(j=0;j<len_b;j++) {	
					if(set_a[i] == set_b[j]) return conf;
				}
			}
		}		
	}
	else if(len_a > len_b) {
		count = 0;
		for(i=0; i<len_b; i++) {
			if(set_a[i] == set_b[i]) count++;	
		}
		if(count == len_b) return B_sub_A; /* B is a proper subset of A */
		else {
			count = 0;
			for(i=0;i<len_a;i++) {
				for(j=0;j<len_b;j++) {	
					if(set_a[i] == set_b[j]) return conf;
				}
			}
		}		
	}
	else {
		count = 0;
		for(i=0; i<len_a; i++) {
			if(set_a[i] == set_b[i]) count++;	
		}
		if(count == len_a) return A_sub_B; /* A is a proper subset of B */
		else {
			count = 0;
			for(i=0;i<len_a;i++) {
				for(j=0;j<len_b;j++) {	
					if(set_a[i] == set_b[j]) return conf;
				}
			}
		}			
	}
	return disj;	
}
int main()
{
	int set1[BUF];
	int set2[BUF];
	char* val, *p;
	int len1, len2, i, isSubSet;
	
	while(1) {
		val = malloc(BUF);	
		if(fgets(val, BUF, stdin)==NULL) break;
		
		p = strtok(val, " ");	
		i = 0;
		while(p) {
			set1[i] = atoi(p);
			p = strtok(NULL, " ");
			i++;
		}
		len1 = i;
		free(val);		
		val = malloc(BUF);			
		fgets(val, BUF, stdin);
		
		p = strtok(val, " ");	
		i = 0;
		while(p) {
			set2[i] = atoi(p);
			p = strtok(NULL, " ");
			i++;
		}
		len2 = i;
		free(val);
		
		qsort (set1, len1, sizeof(int), compare);	
		qsort (set2, len2, sizeof(int), compare);	
		isSubSet = compare_sets(set1, len1, set2, len2);
		
		switch(isSubSet) {
			case equal: printf("A equals B\n");
			break;
			case conf: printf("I'm confused!\n");
			break;
			case disj: printf("A and B are disjoint\n");
			break;
			case A_sub_B: printf("A is a proper subset of B\n");
			break;
			case B_sub_A: printf("B is a proper subset of A\n");
		}		
	}
	
	return 0;
}	

If anyone has a suggestion please let me know, thanks

[ujjal.ruet]

Hey everyone,I have tried 496 and got TLE.Will you please check my code??And tell me how can I reduce execution time..

Code: Select all

#include<stdio.h>

int main(){
int asb,bsa,i,j,k,a[50],b[50],l,p,q;
char c;
while(1){
    asb=0;bsa=0;

  for(i=0;;i++) {
    scanf("%d%c",&a[i],&c);
     if(c=='\n')
      break;}

  for(j=0;;j++) {
  scanf("%d%c",&b[j],&c);
  if(c=='\n')
     break;}


p=0;
 for(k=0;k<=i;k++)
    for(l=0;l<=j;l++)
    {
        if(a[k]==b[l])
                   p++;

    }
if(p==i+1)
  asb=1;

q=0;
 for(k=0;k<=j;k++)
   for(l=0;l<=i;l++)
    {
        if(b[k]==a[l])
               q++;

    }

if(q==j+1)
  bsa=1;


if(bsa==1&&asb==1)
 printf("A equals B\n");
else if(bsa==1&&asb==0)
printf("B is a proper subset of A\n");
else if(bsa==0&&asb==1)
printf("A is a proper subset of B\n");
else if(p==0&&q==0)
printf("A and B are disjoint\n");


else printf("I'm confused!\n");

}


return 0;
}