531 - Compromise

[mf]

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

I think variable-sized arrays are a feature of C99 standard.
They are supported by gcc/g++, but not by Microsoft's compilers.

[ability]

Hi -zx-,
There is a logical error at line #18 in the code. Its here :
>>else if (emo[i-1][j].size() < emo[j-1].size())

The code counts the total number of characters in emo[i-1][j] and emo[j-1], where it should actually be counting the number of words(and not no. of characters) in these 2 cells and then choose max of these both.
So, consider
x1 y1 z1 aaaaaaaaaaaaaaaaaaaa b1 c1
#
aaaaaaaaaaaaaaaaaaaa x1 y1 z1
#

This will give output as "aaaaaaaaaaaaaaaaaaaa" which is wrong, as we are asked to give the longest subsequence of words. The correct answer should be "x1 y1 z1".
We could use an integer 2-D array to store the no. of words, and a separate array to trace the path(like in the original LCS-DP problem)

[$u!fur]

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <list>
#include <cmath>
#include <cstdlib>
#include <string>


#define re return
#define SZ size()
#define L length()
#define vi vector<int>
#define vs vector<string>
#define REP(i,n) for(int i=0;i<n;i++)
#define KEP(i,a,b) for(int i=a;i<=b;i++)
#define MEP(i,a,b) for(int i=a;i>=b;i--)
#define Sort(a) sort(a.begin(),a.end())
using namespace std;
#define MAX 1000
int c[MAX][MAX];
char b[MAX][MAX];
bool flag;

int m,n;

void printlcs(int i,int j,vs mvp)
{
if(i==0||j==0) return ;
else
{
if(b[j]=='D')
{
printlcs(i-1,j-1,mvp);
if(!flag){ cout<<mvp[i-1]; flag=true;}
else cout<<" "<<mvp[i-1];
}
else if(b[j]=='U')
printlcs(i-1,j,mvp);
else printlcs(i,j-1,mvp);
}
}

int main()
{

string str1,str2;
while(getline(cin,str1))
{
flag=false;
string s1,s2;
if(str1=="#")
while(getline(cin,str2))
{
if(str2=="#") break;
s2+=" "+str2;
}
else
{
s1+=str1;
while(getline(cin,str1))
{
if(str1=="#") break;
s1+=" "+str1;
}
while(getline(cin,str2))
{
if(str2=="#") break;
s2+=" "+str2;
}
}


vs sec1,sec2;
for(int i=0;i<s1.L;i++)
{
string temp;
while(s1==' '&&i<s1.L) i++;
while(s1!=' '&&i<s1.L)
{
temp+=s1;
i++;
}
sec1.push_back(temp);
}
for(int i=0;i<s2.L;i++)
{
string temp;
while(s2==' '&&i<s2.L) i++;
while(s2!=' '&&i<s2.L)
{
temp+=s2;
i++;
}
sec2.push_back(temp);
}


m=sec1.SZ;
n=sec2.SZ;

for(int i=1;i<=m;i++) c[0]=0;
for(int j=0;j<=n;j++) c[0][j]=0;

for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(sec1[i-1]==sec2[j-1])
{
c[j]=c[i-1][j-1]+1;
b[i][j]='D';
}
else if(c[i-1][j]>=c[i][j-1])

{
c[i][j]=c[i-1][j];
b[i][j]='U';
}
else
{
c[i][j]=c[i][j-1];
b[i][j]='L';
}
}
printlcs(m,n,sec1);
cout<<endl;

}
return 0;
}

[Samudra Banerjee]

Always getting WA for this code. I have tried many test cases..Someone please help..

Code: Select all

#include<iostream>
#include<string.h>
using namespace std;
void print_LCS(char A[][40],int dir[][40],int a, int b)
{
     if(a==0 || b==0) {}
     else if(dir[a][b]==0)  {print_LCS(A,dir,a-1,b-1);cout<<A[a]<<" ";}
     else if(dir[a][b]==1) print_LCS(A,dir,a-1,b);
     else print_LCS(A,dir,a,b-1);
}
int LCS(char A[][40],char B[][40],int a,int b)
{
    int L[a+1][b+1],dir[105][40],i,j,t;
    for(i=0;i<=a;i++) L[i][0]=0;
    for(i=0;i<=b;i++) L[0][i]=0;
    for(i=1;i<=a;i++) {
                       for(j=1;j<=b;j++) 
                         {
                          L[i][j]=((strcmp(A[i],B[j])==0)?(1+L[i-1][j-1]):((L[i][j-1]>L[i-1][j])?L[i][j-1]:L[i-1][j]));
                          dir[i][j]=((strcmp(A[i],B[j])==0)?0:((L[i][j-1]>L[i-1][j])?2:1));
                         }
    }
    while(dir[a][b]!=0 && a>0 && b>0) if(dir[a][b]==1) a--; else b--;
    t=a;a--;b--;
    print_LCS(A,dir,a,b);
    cout<<A[t]<<endl;
    return L[a][b];
}
int main()
{
    char A[105][40],B[105][40],c,c1;
    int a,b,i,j,k;bool f;
    while(true)
    {
     a=b=1;f=false;c1=' ';i=j=0;
     while((c=getchar())!='#') {A[a][i++]=c; 
                                if((c==' ' || c=='\n') && c1!=' ' && c1!='\n') {A[a][i-1]='\0';a++;i=0;}
                                else if(c==' ' || c=='\n') i--;
                                c1=c;
                                if(c==EOF) {f=true;break;}
     }
     c=getchar();
     if(f || c==EOF) break;
     c1=' ';
     while((c=getchar())!='#') {B[b][j++]=c; 
                                if((c==' ' || c=='\n') && c1!=' ' && c1!='\n') {B[b][j-1]='\0';b++;j=0;}
                                else if(c==' ' || c=='\n') j--;
                                c1=c;
                                }
     LCS(A,B,a-1,b-1);
    } 
    return 0;
}

[bishop]

anyone can help me in BAD pE
1. in printing last word no space print line
2. no output no line
is these right??
if not (i know from judge result)
let me know please.

[bishop]

can anyone give me some tricky test case of PE of "compromise"

[H_Hima]

Hi.
please help me.
this problem storm my mind.
I can't find my mistake.
and can't even predict it.

I Use DP for solving the problem.
this is my code.

all the matters seems correct.
but!!!

Code: Select all

#include<string>
#include<iostream>
#include<fstream>
#include<set>
using namespace std;

string words1[1000],words2[1000],res[1000];

int len[1000][1000][2];

int main() {
	bool sw;
	//ifstream cin("input.txt");
	int i,j,k,n,cnt1,cnt2,cnt;
	string s;
	while(cin>>s) {
		cnt1=cnt2=cnt=0;
		while(s!="#") {
			words1[cnt1++]=s;
			cin>>s;
		}
		while(cin>>s&&s!="#") {
			words2[cnt2++]=s;
		}
		if((cnt1&&cnt2)==false) {
			cout<<endl;
			continue;
		}
		sw=false;
		for(i=0;i<cnt1;i++) {
			if(words1[i]==words2[0]) {
				len[0][i][0]=1;
				len[0][i][1]=0;
				sw=true;
			}
			else if(sw) {
				len[0][i][0]=1;
				len[0][i][1]=1;
			}
			else {
				len[0][i][0]=0;
				len[0][i][1]=1;
			}
		}
		for(i=1;i<cnt2;i++) {
			for(j=0;j<cnt1;j++) {
				if(j==0) {
					if(words2[i]==words1[0]){
						len[i][0][0]=1;
						len[i][0][1]=0;
					}
					else {
						len[i][0][0]=0;
						len[i][0][1]=-1;
					}
				}
				else if(words2[i]==words1[j]) {
					len[i][j][0]=len[i-1][j-1][0]+1;
					len[i][j][1]=0;
				}
				else {
					len[i][j][0]=len[i-1][j][0];
					len[i][j][1]=-1;
					if(len[i][j][0]<len[i][j-1][0]) {
						len[i][j][0]=len[i][j-1][0];
						len[i][j][1]=1;
					}
				}
			}
		}
		sw=false;
		for(i=cnt2-1,j=cnt1-1;i>=0&&j>=0;) {
			if(len[i][j][1]==0) {
				res[cnt++]=words2[i];
				sw=true;
				i--;
				j--;
			}
			else if(len[i][j][1]==1)
				j--;
			else
				i--;
		}
		for(i=cnt-1;i>=0;i--) {
			cout<<res[i];
			if(i)
				cout<<" ";

		}
		cout<<endl;
	}
}

thanks.

[fkrafi]

Why WA !!!!!!

Code: Select all

#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;

char s1[110][35], s2[110][35], s[35];
int lcs[110][110];
int b[110][110], con;
string str;

void dp(int sz1, int sz2)
{
	int i, j;
	for(i=0; i<=sz1; i++)
	{
		for(j=0; j<=sz2; j++)
		{
			if(i>0 && j>0)
			{
				if(strcmp(s1[i-1], s2[j-1]) == 0){
					lcs[i][j] = lcs[i-1][j-1] + 1;
					b[i][j] = 1;
				}else if(lcs[i-1][j] > lcs[i][j-1]){
					lcs[i][j] = lcs[i-1][j];
					b[i][j] = 2;
				}else{
					lcs[i][j] = lcs[i][j-1];
					b[i][j] = 3;
				}
			}else{lcs[i][j] = 0;}
		}
	}
}

void print_lcs(int i, int j)
{
	if(!i || !j)
		return;
	if(b[i][j] == 1)
	{
		print_lcs(i-1, j-1);
		if(con)
			str += " " + string(s1[i-1]);
		else{
			str += string(s1[i-1]);
			con = 1;
		}
	}else if(b[i][j] == 2)
		print_lcs(i-1, j);
	else
		print_lcs(i, j-1);
}

int main()
{
	freopen("input.txt", "r", stdin);
	while(scanf("%s", s) != EOF){
		int sz1=0, sz2=0;
		if(strcmp(s, "#") !=0)
			{
			strcpy(s1[sz1++], s);
			while(scanf("%s", s))
			{
				if(strcmp(s, "#") == 0)break;
				strcpy(s1[sz1++], s);
			}
		}
		while(scanf("%s", s))
		{
			if(strcmp(s, "#") == 0)break;
			strcpy(s2[sz2++], s);
		}

		dp(sz1, sz2);
		print_lcs(sz1, sz2);

		cout << str << endl;
		str[0] = '\0';
		str.erase();
		con = 0;
	}
	return 0;
}

[sir. manuel]

why TLE????

Code: Select all

#include<stdio.h>

#include<string>

#include<cstring>

#include<iostream>

#include<vector>

#include<algorithm>

#include<sstream>

using namespace std;

vector<string>vec1,vec2;  

int path[5000][5000];

int a,b;



void print(int i,int j)

{

if(i==0 || j==0){return;}

if(path[i][j]==1){ print(i-1,j-1); cout<<vec1[i-1]; if(a!=i && b!=j)printf(" ");}	

else if(path[i][j]==2) print(i-1,j);

     else print(i,j-1);

}





int main()

{

	

string cad1,cad2;  

     while(getline(cin,cad1)){  istringstream flujos1(cad1); string aux;

	       while(flujos1>>aux)vec1.push_back(aux);

	       while(getline(cin,cad1) && cad1[0]!='#'){ istringstream flujos1(cad1);   while(flujos1>>aux)vec1.push_back(aux); }

	   

 	       while(getline(cin,cad2) && cad2[0]!='#'){ istringstream flujos2(cad2);   while(flujos2>>aux)vec2.push_back(aux); }

 	       int n,m;  n=vec1.size();  m=vec2.size();

 	       int DP[n+1][m+1]; memset(path,0,sizeof(path));

 	          for(int i=0;i<=n;i++)DP[i][0]=0;

 	          for(int i=0;i<=m;i++)DP[0][i]=0;

 	            for(int i=1;i<=n;i++)

 	            for(int j=1;j<=m;j++){

		          if(vec1[i-1]==vec2[j-1]){DP[i][j]=1+DP[i-1][j-1]; path[i][j]=1; }

		          else{

				   if(DP[i-1][j]>=DP[i][j-1]){DP[i][j]=DP[i-1][j]; path[i][j]=2; }

				   else{DP[i][j]=DP[i][j-1]; path[i][j]=3; } 	

				}

			  }

		    a=n; b=m;

			print(n,m); printf("\n");

	    vec1.clear(); vec2.clear();

	   }

	return 0;

}

[Sawon90]

Why I am getting wrong answer, please someone give me some input and output or some suggestion. My code is....

//Bismillahir Rahmanir Rahim
#include<stdio.h>
#include<string.h>
long i,j,la,lb,mat[1010][1010],fg;
char sta[1010][40],stb[1010][40],ans[1010][40];

void Print(long p,long q)
{
if(p==0 || q==0)
return;
if(ans[p][q]=='C')
{
Print(p-1,q-1);
if(fg==1)
printf(" %s",sta[p]);
else
{
fg=1;
printf("%s",sta[p]);
}
}
else if(ans[p][q]=='U')
Print(p-1,q);
else
Print(p,q-1);
}

int main()
{
i=1;
while(scanf("%s",sta[i++])!=EOF)
{
for(;;i++)
{
scanf("%s",sta);
if(!strcmp(sta,"#"))
break;
}
la=i;
for(i=1;;i++)
{
scanf("%s",stb);
if(!strcmp(stb,"#"))
break;
}
lb=i;
for(i=1;i<la;i++)
{
for(j=1;j<lb;j++)
{
if(!strcmp(sta,stb[j]))
{
mat[j]=mat[i-1][j-1]+1;
ans[j]='C';
}
else
{
if(mat[i-1][j]>=mat[j-1])
{
mat[j]=mat[i-1][j];
ans[j]='U';
}
else
{
mat[i][j]=mat[i][j-1];
ans[i][j]='L';
}
}
}
}
fg=0;
Print(la-1,lb-1);
printf("\n");
i=1;
}
return 0;
}

[brianfry713]

Try the input
#
#

My AC code prints nothing, not even a blank line.

[Sawon90]

I found my mistake,, I just declare wrong size of ans arry. But one thing I don't understand that why I was get Run time error???????????

[cse.mehedi]

My compiler is Code Block-10.0, It can compile my code but why UVA show RE???
Any one help me!!!

Code: Select all

removed

[brianfry713]

Your output for the sample input is wrong.

[hello]

Why Wa.....

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
#define Vec vector<int>
#define Vit vector<int>::iterator
#define pb(a) push_back(a)
using namespace std;
vector<string>v1,v2;
void LCS()
{
    int m=v1.size();
    int n=v2.size();
    if(!(m || n))return ;
    int dp[m+1][n+1];
    int cons[n+1][n+1];

    memset(dp,0,sizeof(dp));
    memset(cons,0,sizeof(cons));

    for(int i=0; i<=m; i++)
    {
        for(int j=0; j<=n; j++)
        {
            //cout<<v1[i-1]<<" "<<v2[j-1]<<endl;
            if(i==0 || j==0)dp[i][j]=0;
            else if(v1[i-1]==v2[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                cons[i][j]=3;
            }
            else if(dp[i-1][j]>=dp[i][j-1])
            {
                dp[i][j]=dp[i-1][j];
                cons[i][j]=2;
            }
            else
            {
                dp[i][j]=dp[i][j-1];
                cons[i][j]=1;
            }
        }
    }
    string s,temp;;
    for(int i=m,j=n; i>0 && j>0;)
    {
        if(cons[i][j]==3)
        {
            temp=v1[i-1]+' ';
            reverse(temp.begin(),temp.end());
            s+=temp;
            i--;
            j--;
        }
        else if(cons[i][j]==2)i--;
        else j--;
    }
    reverse(s.begin(),s.end());
    string::iterator it;
    it=s.end()-1;
    *it='\0';
    cout<<s<<endl;
}

int main()
{

    string s;
    int n=1;


    while(cin>>s)
    {

        if(s=="#")
        {
            if(!(n&1))
            {
                LCS();
                v1.clear();
                v2.clear();
            }
            n++;
        }
        else if(n&1)v1.pb(s);
        else v2.pb(s);
    }


return 0;
}