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

anne0604
New poster
Posts: 4
Joined: Tue Aug 08, 2006 10:36 pm

496 why TLE??

Post by 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... :cry:

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

thx. :wink:
Last edited by anne0604 on Sat Jul 07, 2007 10:12 am, edited 1 time in total.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by 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
New poster
Posts: 4
Joined: Tue Aug 08, 2006 10:36 pm

Post by 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...... :cry:

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

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

little joey wrote: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
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv »

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

anne0604
New poster
Posts: 4
Joined: Tue Aug 08, 2006 10:36 pm

Post by 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................ :cry:

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Phocasia
New poster
Posts: 4
Joined: Fri May 11, 2007 3:50 pm

Re: Help me with 496

Post by 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
New poster
Posts: 17
Joined: Tue Jul 08, 2008 3:19 am

Re: Help me with 496

Post by 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
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

496 Simply Subsets

Post by 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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 496 Simply Subsets

Post by 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
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: Help me with 496

Post by 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
Heal The World

obbY
New poster
Posts: 5
Joined: Sun May 16, 2010 11:41 pm

Re: Help me with 496

Post by 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
New poster
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh
Contact:

496..getting TLE

Post by 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;
}


Post Reply

Return to “Volume 4 (400-499)”