531 - Compromise
Moderator: Board moderators
-
- Learning poster
- Posts: 56
- Joined: Tue Jun 13, 2006 5:18 pm
- Location: (CSE, SUST) Sylhet, Bangladesh
- Contact:
Why WA? Help please
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
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
Last edited by Mushfiqur Rahman on Wed Sep 06, 2006 3:13 am, edited 1 time in total.
-
- Learning poster
- Posts: 60
- Joined: Sun Apr 16, 2006 7:59 pm
531 compromise WA
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:
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....
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
pls help.... i'll be highly greatful to u...
thanks....
-
- Learning poster
- Posts: 56
- Joined: Tue Jun 13, 2006 5:18 pm
- Location: (CSE, SUST) Sylhet, Bangladesh
- Contact:
Re: Why WA? Help please
Mushfiqur Rahman wrote: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
-
- New poster
- Posts: 1
- Joined: Fri Sep 08, 2006 1:27 pm
- Location: dhaka
531 compromise WA
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;
}
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;
}
I am getting WA in 531 .. i donno where's the prob
![:cry:](./images/smilies/icon_cry.gif)
![:cry:](./images/smilies/icon_cry.gif)
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;
}
Time that gone is gone forever ...
to SAKHASSAN:
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 ...
regards,
nymo
nymo
To sakhassan, your code contains a lot of excessive things which make it harder to understand...
1. read the descriptionto
2. You can use strlen() since you have included string.h
3.Just pass the length (Pass m and n) and change
to
4. Why are you passing x?
5.Remove this line.
6.Any reason for this function?
7. And finallySo, you will get PE, because after the last word you are printing a space, too.
Hope this help.
1. read the description
so changeEach text is given as a sequence of lower-case words, separated by whitespace, but with no punctuation
Code: Select all
x[i]=tolower(a[0]);
Code: Select all
x[i]=a[0];
3.
Code: Select all
void lcs(char x[MAX], char y[MAX])
Code: Select all
if(x[i-1]==y[j-1] && (strcmp(str1[i-1],str2[j-1])==0) )
Code: Select all
if( (strcmp(str1[i-1],str2[j-1])==0) )
Code: Select all
void print_LCS(int b[MAX][MAX], char x[MAX], int i, int j)
5.
Code: Select all
if(cases)printf("\n");
6.
Code: Select all
char* lower(char s[MAX])
7. And finally
Code: Select all
printf("%s ",str1[i-1]);
Hope this help.
Ami ekhono shopno dekhi...
HomePage
HomePage
531 PE
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;
}
I am getting PE
![:lol:](./images/smilies/icon_lol.gif)
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;
}
shibu
Dont open a new thread if there is one. Post in an existing thread.
Ami ekhono shopno dekhi...
HomePage
HomePage
531 - Compromise - WA
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;
}
Hi,
I tried to test your code on my compiler when I noticed
Does it work on your compiler?
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?
Narek Saribekyan