## 10635 - Prince and Princess

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

Moderator: Board moderators

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

### ACCCCCCCCCCCC

hello...
ANOTHER STUPID MISTAKE!!!!!!!!
MINE WOULD ACC before if i maintained THE CORRECT OUTPUT FORMAT(print case number)
these days i amm so careless    thank UUUUUUUUUUUU
keep posting!!!!!!
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

kane116
New poster
Posts: 8
Joined: Sun Aug 07, 2005 5:35 am
I am getting RE,
Would someone told me what's wrong with my code?
Actually, I am using LCS only.

Code: Select all

``````#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int a, b;
int c;

int main() {
int T, idx = 0;
scanf("%d", &T);
while (T--) {
int n, p, q;
scanf("%d%d%d", &n, &p, &q);
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for (int i = 0; i <= p; i++) scanf("%d", &a[i]);
for (int i = 0; i <= q; i++) scanf("%d", &b[i]);
memset(c, 0, sizeof(c));
for (int i = 1; i <= p + 1; i++) {
for (int j = 1; j <= q + 1; j++) {
if (a[i - 1] == b[j - 1]) {
c[i][j] = c[i - 1][j - 1] + 1;
}
else c[i][j] = max(c[i - 1][j], c[i][j - 1]);
}
}
printf("Case %d: %d\n", ++idx, c[p + 1][q + 1]);
}
return 0;
}
``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
p and q can be as large as 62499.
But your code assumes they are at most 254.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
May be, I did not understand the problem
it seems to me LCS,
where it is related to LIS?

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
May be, I did not understand the problem
it seems to me LCS,
where it is related to LIS?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Yes, this problem asks for LCS (longest common subsequence.)
But there's one very important thing: each input sequence consists of distinct elements.

Computing LCS in this case can be reduced to the problem of finding a LIS (longest increasing subsequence.)

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Consider the following input

Code: Select all

``````1
3 4 5
1 7 6 5 9
1 8 7 6 5 9
``````
output of LCS should be

Code: Select all

``4``
but output of LIS should be

Code: Select all

``3``
I am struggling on this point
so please make a bit more clear

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
1. Output of your LCS is wrong. LCS is {1,7,6,5,9}.

2. What sequence's LIS is that?!

My accepted program replaces each number of the 2nd sequence with its index in the 1st sequence, and finds the length of LIS of the resulting sequence. See also neno_uci's code at the top of this page.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
sorry LCS should {1,7,6,5,9}.
and LIS should {1,7,9}.

sorry i dont understand pascal

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Again, you're trying to find LIS of which sequence?

Finding LIS of any of the input sequences is useless. You need to make a transformation:
mf wrote:My accepted program replaces each number of the 2nd sequence with its index in the 1st sequence, and finds the length of LIS of the resulting sequence.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Thanks mf(Guru)
thats make clear to me
now i think i can try it
thanks again

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Thanks mf I got accepted..

seraph
New poster
Posts: 9
Joined: Tue Dec 15, 2009 4:18 pm

### Re: 10635 - Prince and Princess

why my code is always RE ?

this is my code :

Code: Select all

``````#include <iostream>
#include <vector>
using namespace std;
int main()
{
int arr1,arr2;
vector<int> v,v1,v2;
int t;
cin>>t;
for (int i=0;i<t;i++)
{
int n,a,b,temp;
cin>>n>>a>>b;
v.clear();
v1.clear();
v2.clear();
a++;b++;
memset(arr1,0,sizeof(arr1));
memset(arr2,0,sizeof(arr2));

for (int j=1;j<=a;j++)
{
cin>>temp;
arr1[temp]=j;
v2.push_back(temp);
}
int pj=0;
for (int j=1;j<=b;j++)
{
cin>>temp;
if (arr1[temp]!=0)
{
pj++;
arr2[pj]=arr1[temp];
v.push_back(temp);
arr1[temp]=-1;
}
}
for (int j=0;j<v2.size();j++)
if (arr1[v2[j]]==-1)
v1.push_back(v2[j]);

int dp[v.size()+1][v1.size()+1];
memset(dp,0,sizeof(dp));
for (int j=1;j<=v.size();j++)
for (int k=1;k<=v1.size();k++)
{
if (v[j-1]==v1[k-1])
dp[j][k]=dp[j-1][k-1]+1;
else if (dp[j-1][k] > dp[j][k-1])
dp[j][k]=dp[j-1][k];
else
dp[j][k]=dp[j][k-1];
}
cout<<"Case "<<i+1<<": "<<dp[v.size()][v1.size()]<<endl;
}
//system("pause");
return 0;
}
``````
please help...

kumar_utpal
New poster
Posts: 2
Joined: Thu Dec 15, 2011 9:49 am

### Re: 10635 - Prince and Princess.please help

#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>
#include <bitset>

using namespace std;

int LCS(vector <int> v1,vector <int> v2)
{
int a=v1.size(),b=v2.size(),i,j;
if(b<a)
{
swap(v1,v2);
swap(a,b);
}
int c[a];
for(i=0;i<b;i++)
c=0;
for(i=0;i<a;i++)
c=0;
for(i=1;i<a;i++)
{
for(j=1;j<b;j++)
{
if(v1==v2[j])
c[j]=c[i-1][j-1]+1;
else
c[j]=max(c[i-1][j],c[j-1]);
}
}
return c[i-1][j-1];
}

int main()
{
//freopen("Input.txt","r",stdin);
int t,n,a,b,i=1,j;
vector <int> v1,v2;
cin>>t;
while(t--)
{
cin>>n>>a>>b;
v1.push_back(0);
v2.push_back(0);
for(j=0;j<=a;j++)
{
cin>>n;
v1.push_back(n);
}
for(j=0;j<=b;j++)
{
cin>>n;
v2.push_back(n);
}
cout<<"Case "<<i<<": "<<LCS(v1,v2)<<endl;
i++;
v1.clear();
v2.clear();
}
return 0;
}

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

### Re: 10635 - Prince and Princess

You're getting RE because the vectors can be as large as n*n=250*250=62500, and 62500*62500 is too large for an array of ints.
Check input and AC output for thousands of problems on uDebug!