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

Post by I LIKE GN » 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 :P :D :D :D
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

Post by kane116 » 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;
}

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

Post by mf » 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.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » 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?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » 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?

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

Post by mf » 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.)

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » 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

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:

Post by mf » 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.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » 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

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

Post by mf » 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.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Apr 29, 2006 1:46 pm

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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Apr 29, 2006 2:22 pm

Thanks mf I got accepted..

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

Re: 10635 - Prince and Princess

Post by seraph » 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...

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

Re: 10635 - Prince and Princess.please help

Post by kumar_utpal » 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;
}

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

Re: 10635 - Prince and Princess

Post by brianfry713 » 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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 106 (10600-10699)”