Page 3 of 4

496 why TLE??

Posted: Fri Jul 06, 2007 10:58 pm
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:

Posted: Sat Jul 07, 2007 7:46 am
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..

Posted: Sat Jul 07, 2007 10:16 am
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:

Posted: Sat Jul 07, 2007 11:06 am
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.

Posted: Sat Jul 07, 2007 5:27 pm
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.

Posted: Sat Jul 07, 2007 5:41 pm
by hamedv
the value of the numbers is not more than 1,000,000

Posted: Sat Jul 07, 2007 6:37 pm
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:

Posted: Sat Jul 07, 2007 7:20 pm
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.

Re: Help me with 496

Posted: Thu May 15, 2008 7:27 am
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

Re: Help me with 496

Posted: Tue Jul 08, 2008 3:26 am
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....

496 Simply Subsets

Posted: Fri Dec 19, 2008 4:07 pm
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;
}

Re: 496 Simply Subsets

Posted: Fri Dec 19, 2008 6:11 pm
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.

Re: Help me with 496

Posted: Wed May 27, 2009 9:03 am
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

Re: Help me with 496

Posted: Sun May 23, 2010 3:56 am
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 :(

496..getting TLE

Posted: Tue Oct 19, 2010 7:12 am
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;
}