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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Feb 19, 2007 5:54 pm

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.

ability
New poster
Posts: 2
Joined: Sun Apr 27, 2008 8:49 pm

Re: 531 - Compromise - WA

Post by ability » Sun Apr 27, 2008 9:25 pm

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
New poster
Posts: 2
Joined: Thu Jun 12, 2008 10:30 am

Re: 531 PE

Post by $u!fur » Thu Jun 12, 2008 10:32 am

#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
New poster
Posts: 4
Joined: Mon Jun 16, 2008 7:21 am
Location: Kolkata, India
Contact:

Re: 531 - Compromise - WA

Post by Samudra Banerjee » Mon Jun 30, 2008 8:46 pm

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;
}
Jodi Tor Dak Shune Keu Naa Ashey....
Tobey Ekla Cholo Re....

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

helping PE in 531

Post by bishop » Mon Sep 08, 2008 6:28 pm

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
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

531 - Compromise - PE

Post by bishop » Tue Sep 09, 2008 6:09 pm

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

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Re: 531 - Compromise - WA

Post by H_Hima » Fri Sep 26, 2008 9:07 pm

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
New poster
Posts: 13
Joined: Wed Sep 15, 2010 1:36 pm

Re: 531 - Compromise - WA

Post by fkrafi » Mon Oct 25, 2010 8:59 pm

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
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

Re: 531 - Compromise - WA

Post by sir. manuel » Sun Jan 16, 2011 2:02 am

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
New poster
Posts: 11
Joined: Wed Nov 23, 2011 1:28 am

Re: 531 - Compromise - WA

Post by Sawon90 » Sun Mar 04, 2012 3:57 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 531 - Compromise - WA

Post by brianfry713 » Tue Mar 06, 2012 12:53 am

Try the input
#
#

My AC code prints nothing, not even a blank line.
Check input and AC output for thousands of problems on uDebug!

Sawon90
New poster
Posts: 11
Joined: Wed Nov 23, 2011 1:28 am

Re: 531 - Compromise - WA

Post by Sawon90 » Thu Mar 08, 2012 6:11 pm

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
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

531 RE!!

Post by cse.mehedi » Wed Jul 25, 2012 9:17 am

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
Last edited by cse.mehedi on Thu Jul 26, 2012 9:21 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 531 RE!!

Post by brianfry713 » Wed Jul 25, 2012 11:45 pm

Your output for the sample input is wrong.
Check input and AC output for thousands of problems on uDebug!

hello
New poster
Posts: 25
Joined: Sun Mar 10, 2013 7:29 pm

Re: 531 - Compromise - WA

Post by hello » Mon Sep 02, 2013 6:52 am

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;
}


Post Reply

Return to “Volume 5 (500-599)”