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.

Moderator: Board moderators
Code: Select all
while( gets(tempA) )
{
gets(tempB);
}
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;
}
Code: Select all
Delete after AC
there is no repeated integers in a line in the input.Each line of text (set) will be a list of distinct integers.
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;
}
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;
}