OJ Board

Posted: **Fri Sep 02, 2005 12:32 pm**

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

Posted: **Thu Dec 22, 2005 6:03 pm**

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

Posted: **Thu Dec 22, 2005 6:42 pm**

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

Posted: **Fri Apr 28, 2006 8:15 pm**

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

Posted: **Fri Apr 28, 2006 8:16 pm**

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

Posted: **Fri Apr 28, 2006 8:56 pm**

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.)

Posted: **Sat Apr 29, 2006 11:31 am**

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

but output of LIS should be

Code: Select all

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

Posted: **Sat Apr 29, 2006 12:10 pm**

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.

Posted: **Sat Apr 29, 2006 12:25 pm**

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

sorry i dont understand pascal

Posted: **Sat Apr 29, 2006 1:18 pm**

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.

Posted: **Sat Apr 29, 2006 1:46 pm**

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

Posted: **Sat Apr 29, 2006 2:22 pm**

Thanks mf I got accepted..

Posted: **Wed Jan 20, 2010 3:39 pm**

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

Posted: **Thu Dec 22, 2011 8:14 pm**

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

Posted: **Fri Jan 13, 2012 1:01 am**

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.

OJ Board

10635 - Prince and Princess

ACCCCCCCCCCCC

Re: 10635 - Prince and Princess

Re: 10635 - Prince and Princess.please help

Re: 10635 - Prince and Princess