531 - Compromise

[taskin]

thanks, but i still not found any error.

[Mushfiqur Rahman]

I yet not found any problem with my code, but it still getting WA.
I used here normal LCS with DP. It's gives me correct answer.
I have a question about the problem.
-> Would there be any character other than lower case (a...z).?

I am giving my code, please check it and let me know where's the trouble

Code: Select all

Removed. I found my fault

[ayeshapakhi]

i got several WA in the prob 531...donno why..
what should i do when there isn't any lcs???
and what to do abt the blank test cases?
here's my code:

Code: Select all

#include <stdio.h>
#include <string.h>
removed after AC

it would be very helpful if someone who got ac in this problem send me some critical i/o....
pls help.... i'll be highly greatful to u...
thanks....

[Mushfiqur Rahman]

I yet not found any problem with my code, but it still getting WA.
I used here normal LCS with DP. It's gives me correct answer.
I have a question about the problem.
-> Would there be any character other than lower case (a...z).?

I am giving my code, please check it and let me know where's the trouble

[M. A. Bashar]

i got several WA in the prob 531...donno why..
what should i do when there isn't any lcs???
and what to do abt the blank test cases?
here's my code:

#include <stdio.h>
#include <string.h>
//#include <conio.h>

typedef struct {
char word[40];

}WType;

WType text1[1000];
WType text2[1000];


char in1[1000],in2[1000];
long count1,count2;

long c[1000][1000];
char b[1000][1000];


void print_lcs(long i,long j)
{
if(i==-1 || j==-1)
return;
if(b[j]=='\\')
{
print_lcs(i-1,j-1);
printf("%s ",text1.word);
}
else if(b[j]=='|')
{
print_lcs(i-1,j);
}
else
{
print_lcs(i,j-1);
}

}


void lcs_length(long m,long n)
{
long i,j;

for(i=0;i<m;i++)
{
c[0] = 0;
}
for(j=0;j<n;j++)
{
c[0][j] = 0;
}

for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(strcmp(text1.word,text2[j].word)==0)
{
c[j] = c[i-1][j-1]+1;
b[j] = '\\';
}
else if(c[i-1][j]>=c[j-1])
{
c[j] = c[i-1][j];
b[j] = '|';
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = '-';
}
}
}
}




void call_init(void)
{
long i,j,k;

while(scanf(" %[^#]# %[^#]#",in1,in2)==2)
{

//printf("%s%s\n",in1,in2);
count1 = 0;
count2 = 0;

for(i=0,j=0,k=0;in1[i]!='\0';i++)
{
if(in1[i]==' ' || in1[i]=='\n')
{
text1[j].word[k] = '\0';
j++;
k=0;
}
else
{
text1[j].word[k] = in1[i];
k++;
}
}

count1=j;

for(i=0,j=0,k=0;in2[i]!='\0';i++)
{
if(in2[i]==' ' || in2[i]=='\n')
{
text2[j].word[k] = '\0';
j++;
k=0;
}
else
{
text2[j].word[k] = in2[i];
k++;
}
}

count2=j;

/*for(i=0;i<count1;i++)
{
printf("%s\n",text1[i].word);
}
printf("\n");
for(i=0;i<count2;i++)
{
printf("%s\n",text2[i].word);
}
printf("\n");*/
lcs_length(count1,count2);
print_lcs(count1-1,count2-1);
printf("\n");
}

}



int main(void)
{
//freopen("F:\\input\\531.txt","rt",stdin);

call_init();

return 0;
}

[sakhassan]

I am getting WA in 531 .. i donno where's the prob

Code: Select all

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

#define MAX 100

char str1[MAX][MAX];
char str2[MAX][MAX];


char* lower(char s[MAX])
{

	char temp[MAX];
	int i;

	for(i=0;s[i];i++)
	{
		temp[i]=tolower(s[i]);
	}
	temp[i]='\0';

	return temp;

}

int strlen(char s[MAX])
{
	int len;
	for(len=0;s[len];len++)
		;
	return len;
}
void print_LCS(int b[MAX][MAX], char x[MAX], int i, int j)
{
	if(i==0 || j==0)
	 return;
	if(b[i][j]==3)
	{
		print_LCS(b,x,i-1,j-1);
		printf("%s ",str1[i-1]);
	}
	else if(b[i][j]==2)
	 print_LCS(b,x,i-1,j);
	else
	 print_LCS(b,x,i,j-1);
}

void lcs(char x[MAX], char y[MAX])
{

	int m,n;
	int i,j;
	int c[MAX][MAX];
	int b[MAX][MAX];


	m=strlen(x);
	n=strlen(y);

	for(i=0;i<=m;i++)
	{
		c[i][0]=0;
		b[i][0]=0;
	}
	for(j=0;j<=n;j++)
	{
		c[0][j]=0;
		b[0][j]=0;
	}


	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(x[i-1]==y[j-1] && (strcmp(str1[i-1],str2[j-1])==0) )
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=3;
			}
			else if(c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i][j]=2;
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i][j]=1;
			}
		}
	}

	print_LCS(b,x,m,n);


}



int main()
{

	char x[MAX],y[MAX];
	char a[MAX],b[MAX];
	int len;
	int i;
	int cases;
	cases = 0;

	freopen("5.cpp","r",stdin);
	
	while(1)
	{
		if(scanf("%s",a)!=1)
		 break;
		for(i=0;i<MAX;i++)
		{
		 strcpy(str1[i],"");
		 strcpy(str2[i],"");
		}
		if(cases)printf("\n");
		cases++;
		

		i=0;
		while(strcmp(a,"#")!=0)
		{
		     x[i]=tolower(a[0]);
		     strcpy(str1[i],a);
		     scanf("%s",a);
		     i++;
		}
		x[i]='\0';
		i=0;
		scanf("%s",b);
		while(strcmp(b,"#")!=0)
		{
		     y[i]=tolower(b[0]);
		     strcpy(str2[i],b);
		     scanf("%s",b);
		     i++;
		}
		y[i]='\0';
		//gets(b);
		lcs(x,y);
		printf("\n");

	}
	return 0;
}

[nymo]

You are printing extra blank after the last word and extra newline between test cases. However, that should be P.E. if all other things are okay ...

[Jan]

To sakhassan, your code contains a lot of excessive things which make it harder to understand...

1. read the description

Each text is given as a sequence of lower-case words, separated by whitespace, but with no punctuation

so change

Code: Select all

x[i]=tolower(a[0]);

to

Code: Select all

x[i]=a[0];

2. You can use strlen() since you have included string.h

3.

Code: Select all

void lcs(char x[MAX], char y[MAX])

Just pass the length (Pass m and n) and change

Code: Select all

if(x[i-1]==y[j-1] && (strcmp(str1[i-1],str2[j-1])==0) )

to

Code: Select all

if( (strcmp(str1[i-1],str2[j-1])==0) )

4.

Code: Select all

void print_LCS(int b[MAX][MAX], char x[MAX], int i, int j)

Why are you passing x?

5.

Code: Select all

if(cases)printf("\n");

Remove this line.

6.

Code: Select all

char* lower(char s[MAX])

Any reason for this function?

7. And finally

Code: Select all

printf("%s ",str1[i-1]);

So, you will get PE, because after the last word you are printing a space, too.

Hope this help.

[sakhassan]

Thanks J@N for ur effort...

[shibu]

Please, Help me ,
I am getting PE .


here is my code


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


#define max 3005

char str1[max+1][33],str2[max+1][33];

char ch[max+5];

int m,n,k,p,q;
short b[max+2][max+2],c[max+2][max+2];


void f1()
{
int i,j;
for(i=0,j=0;ch;i++)
{
if(isalpha(ch))
str1[k][j++]=ch;
else
{
str1[k][j]=0;
k++;
j=0;

}
}
str1[k][j]=0;
k++;
m=k;

}

void f2()
{
int i,j;
for(i=0,j=0;ch;i++)
if(isalpha(ch))
str2[k][j++]=ch;
else
{
str2[k][j]=0;
j=0;
k++;
}
str2[k][j]=0;
k++;

n=k;
}

void lcs()
{
int i,j;

for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(!strcmp(str1[i-1],str2[j-1]))
{
c[j]=c[i-1][j-1]+1;
b[j]=1;
}
else
if(c[i-1][j]>c[j-1])
{
c[j]=c[i-1][j];
b[i][j]=2;

}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
///printf("%d\n",c[m][n]);

}

void p_lcs(int i,int j)
{
if(i<=0||j<=0)
return;
if(b[i][j]==1)
{
p_lcs(i-1,j-1);
if(k<c[m][n]-1)
{
k++;
printf("%s ",str1[i-1]);
}
else
{
p=i-1;
}



}
else
if(b[i][j]==2)
p_lcs(i-1,j);
else
p_lcs(i,j-1);

}

int main()
{
//freopen("d:\\in\\531.in","r",stdin);
//freopen("d:\\out\\531.out","w",stdout);
//char f=0;

while(gets(ch)!=NULL)
{
k=0;

f1();
while(1)
{
gets(ch);
if(ch[0]=='#')
break;
//k--;
f1();

}
k=0;
while(1)
{
gets(ch);

if(ch[0]=='#')
break;
f2();

}
lcs();
k=0;
//if(f==1)
// printf("\n");
//else
// f=1;

p_lcs(m,n);

//if(c[m][n]>0)
printf("%s\n",str1[p]);
//printf("\n");


}
return 0;
}

[Jan]

Dont open a new thread if there is one. Post in an existing thread.

[-zx-]

can anyone see the problem ? it works fine for test cases.

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<string> VS;

string LCS(VS a, VS b)
{
    int n = a.size();
    int m = b.size();
    string emo[n+1][m+1];
    
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        if (a[i-1] == b[j-1])
          emo[i][j] = emo[i-1][j-1] + a[i-1] + " ";
        else if (emo[i-1][j].size() < emo[i][j-1].size())
          emo[i][j] = emo[i][j-1];
        else
          emo[i][j] = emo[i-1][j];
          
    /*for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
          cout << emo[i][j] << " | ";
        cout << endl;
    }*/
          
    return emo[n][m];
}

char modd(char x)
{
    if (x >= 'A' && x <= 'Z')
      return x-'A'+'a';
    return x;
}

int main()
{
    VS vv;
    VS cc;
    
    while (1)
    {
        string s;
        while (1)
        {
            cin >> s;
            if (s.empty())
              goto end;
              
            if (s == "#")
              break;
            
            transform(s.begin(), s.end(), s.begin(), modd);
            vv.push_back(s);
        }
        while (1)
        {
            cin >> s;
            if (s.empty())
              goto end;
              
            if (s == "#")
              break;
            
            transform(s.begin(), s.end(), s.begin(), modd);
            cc.push_back(s);
        }
        
        s = LCS(vv, cc);
        
        if (!s.empty())
          cout << s.substr(0, s.size() - 1) << endl;
        
        vv.clear();
        cc.clear();
    }
    
    end:
    return 0;
}

[snar]

Hi,
I tried to test your code on my compiler when I noticed

Code: Select all

int n = a.size(); 
    int m = b.size(); 
    string emo[n+1][m+1]; 

Does it work on your compiler?

[-zx-]

indeed it does. you can compile it as c++.

[snar]

indeed it does. you can compile it as c++.

It doesn't compile on my Microsoft Visual Studio 2005 compiler. You are using non-constant identifiers for declaring arrays.

???