Page 4 of 5

Posted: Mon Feb 19, 2007 5:54 pm
by mf
snar wrote: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.

Re: 531 - Compromise - WA

Posted: Sun Apr 27, 2008 9:25 pm
by 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)

Re: 531 PE

Posted: Thu Jun 12, 2008 10:32 am
by $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;
}

Re: 531 - Compromise - WA

Posted: Mon Jun 30, 2008 8:46 pm
by 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;
}

helping PE in 531

Posted: Mon Sep 08, 2008 6:28 pm
by 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.

531 - Compromise - PE

Posted: Tue Sep 09, 2008 6:09 pm
by bishop
can anyone give me some tricky test case of PE of "compromise" :cry:

Re: 531 - Compromise - WA

Posted: Fri Sep 26, 2008 9:07 pm
by 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.

Re: 531 - Compromise - WA

Posted: Mon Oct 25, 2010 8:59 pm
by 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;
}

Re: 531 - Compromise - WA

Posted: Sun Jan 16, 2011 2:02 am
by 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;

}

Re: 531 - Compromise - WA

Posted: Sun Mar 04, 2012 3:57 pm
by 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;
}

Re: 531 - Compromise - WA

Posted: Tue Mar 06, 2012 12:53 am
by brianfry713
Try the input
#
#

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

Re: 531 - Compromise - WA

Posted: Thu Mar 08, 2012 6:11 pm
by 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???????????

531 RE!!

Posted: Wed Jul 25, 2012 9:17 am
by 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

Re: 531 RE!!

Posted: Wed Jul 25, 2012 11:45 pm
by brianfry713
Your output for the sample input is wrong.

Re: 531 - Compromise - WA

Posted: Mon Sep 02, 2013 6:52 am
by 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;
}