531 - Compromise

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

taskin
New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
Location: Bangladesh

Post by taskin » Tue Jun 06, 2006 5:54 am

thanks, but i still not found any error.

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Why WA? Help please

Post by Mushfiqur Rahman » Sun Jul 30, 2006 7:35 am

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
Last edited by Mushfiqur Rahman on Wed Sep 06, 2006 3:13 am, edited 1 time in total.

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

531 compromise WA

Post by ayeshapakhi » Sat Sep 02, 2006 9:20 am

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
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Re: Why WA? Help please

Post by Mushfiqur Rahman » Wed Sep 06, 2006 3:12 am

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

M. A. Bashar
New poster
Posts: 1
Joined: Fri Sep 08, 2006 1:27 pm
Location: dhaka
Contact:

531 compromise WA

Post by M. A. Bashar » Fri Sep 08, 2006 1:38 pm

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
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Mon Dec 18, 2006 10:04 am

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

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

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

to SAKHASSAN:

Post by nymo » Mon Dec 18, 2006 8:46 pm

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Dec 19, 2006 12:13 am

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.
Ami ekhono shopno dekhi...
HomePage

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Wed Dec 20, 2006 7:52 am

Thanks J@N for ur effort...
Time that gone is gone forever ...

shibu
New poster
Posts: 1
Joined: Tue Dec 27, 2005 8:13 am
Location: ctg.
Contact:

531 PE

Post by shibu » Wed Dec 20, 2006 9:32 pm

Please, Help me ,
I am getting PE :lol: .


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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Dec 20, 2006 10:12 pm

Dont open a new thread if there is one. Post in an existing thread.
Ami ekhono shopno dekhi...
HomePage

-zx-
New poster
Posts: 3
Joined: Sat Feb 03, 2007 12:36 am

531 - Compromise - WA

Post by -zx- » Sat Feb 03, 2007 12:40 am

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
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

Post by snar » Sun Feb 11, 2007 8:01 pm

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?
Narek Saribekyan

-zx-
New poster
Posts: 3
Joined: Sat Feb 03, 2007 12:36 am

Post by -zx- » Mon Feb 19, 2007 9:13 am

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

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

Post by snar » Mon Feb 19, 2007 2:42 pm

-zx- wrote: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.

:-? ???
Narek Saribekyan

Post Reply

Return to “Volume 5 (500-599)”