10635 - Prince and Princess

[I LIKE GN]

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

[kane116]

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[255], b[255];
int c[255][255];

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]

p and q can be as large as 62499.
But your code assumes they are at most 254.

[emotional blind]

May be, I did not understand the problem
it seems to me LCS,
where it is related to LIS?

[emotional blind]

May be, I did not understand the problem
it seems to me LCS,
where it is related to LIS?

[mf]

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]

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]

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]

sorry LCS should {1,7,6,5,9}.
and LIS should {1,7,9}.

sorry i dont understand pascal

[mf]

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:

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]

Thanks mf(Guru)
thats make clear to me
now i think i can try it
thanks again

[emotional blind]

Thanks mf I got accepted..

[seraph]

why my code is always RE ?

this is my code :

Code: Select all

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int arr1[100000],arr2[100000];
    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]

#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]=0;
for(i=0;i<a;i++)
c[0]=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]

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.