OJ Board

Posted: **Tue May 15, 2012 7:51 pm**

I've checked all I/O and can't find a mistake, but I get WA now.
Can anyone help~

/*111*/
#include<stdio.h>
#include<algorithm>
using namespace std;
int st[30];
int in[30];

int LCS(int len)
{
    int dp1[30],dp2[30];   
    int *A,*B,*temp;
    A=dp1;B=dp2;
    if (st[0]==in[0])A[0]=1;
    else A[0]=0;
    for (int j=1;j<len;j++)
    {
        if (st[0]==in[j])
           A[j]=1;
        else 
             A[j]=0;        
    }
    for (int i=1;i<len;i++)
    {
        if (st[i]==in[0])
           B[0]=1;
        else B[0]=A[0];
        for (int j=1;j<len;j++)
        {
            if (st[i]==in[j])
            {
               B[j]=A[j-1]+1;                  
            }
            else B[j]=max(B[j-1],A[j]);
        }    
        temp=A;A=B;B=A;
    }
    return A[len-1];
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int len;
    int k;
    scanf("%d",&len);
    for (int i=0;i<len;i++)
    {
        scanf("%d",&k);
        st[k-1]=i+1;
    }
    while (scanf("%d",&k)!=EOF)
    {
          in[k-1]=1;
          for (int i=1;i<len;i++)
          {
              scanf("%d",&k);  
              in[k-1]=i+1;  
          }
          printf("%d\n",LCS(len));
    }
    return 0;   
}

Posted: **Tue May 15, 2012 10:38 pm**

Try sample input 1

Posted: **Wed May 16, 2012 2:36 pm**

Sample input

Code: Select all

10
3 1 2 4 9 5 10 6 8 7
1 2 3 4 5 6 7 8 9 10
4 7 2 3 10 6 9 1 5 8
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6

My output:

Code: Select all

I think it's correct

Posted: **Wed May 16, 2012 2:51 pm**

Thanks~
I got AC
the problem is

Code: Select all

for (int j=1;j<len;j++)
    {
        if (st[0]==in[j])
           A[j]=1;
        else
             /*A[j]=0; */  A[j]=A[j-1];      
    }

TKS~

Posted: **Wed May 30, 2012 4:35 pm**

Can someone plzzz explain the o/p of the following sample input....how is it coming to 9...according to me answer should be 5 for last case.
last case LIS - 2 4 9 5 7

Sample Input 2
10
3 1 2 4 9 5 10 6 8 7
1 2 3 4 5 6 7 8 9 10
4 7 2 3 10 6 9 1 5 8
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6

Sample Output 2
6
5
10
9

Posted: **Fri Jun 01, 2012 12:17 am**

http://online-judge.uva.es/board/viewtopic.php?t=7879

Posted: **Fri Jun 01, 2012 10:16 am**

thanks a lot...i got AC

Posted: **Sun Jan 20, 2013 2:03 am**

Hello, I got WA in this problem and I cant figure the reason

. Please help me, I read a lot of topics about the problem but any of them helped me.

Here is my code, it is in cpp.

Code: Select all

ACCEPTED

Posted: **Sun Jan 20, 2013 6:02 am**

I got accepted just making the size of the vectors = n. I really can't understand why that gave me WA

Posted: **Thu Jan 24, 2013 8:30 am**

Perhaps I missed it in another category or subcat, but my boss pointed out there is no way to monitor user activity through the admin interface. Has someone developed a plugin or mod that generates a report including time, userid, username, email address, and action (subscribe, unsubscribe, or modify)? He recently posted a home page article on our website to elicit subscriptions but we have no easy way to identify its effectiveness.

Posted: **Thu Nov 21, 2013 3:58 am**

I see that this is a straight forward LCS problem. Also I get the fact that as the numbers are unique we can use LIS after mapping the first sequence to the sequence 1,2.....n.

Competitive programming book (1st edition) claims that this is a straight forward LIS implementation. Is that so? So most of the times LIS is used to speed up LCS.

Posted: **Thu Nov 21, 2013 11:10 pm**

Yes you can solve it in O(n * n) using LCS, or O(n log n) using LIS.

Posted: **Thu Jun 26, 2014 9:38 pm**

I used longest common subsequence algorithm, and I have right output

, but wrong answer

.

Code: Select all

int arr1[10000],arr2[10000];
int lcs( int *X, int *Y, int m, int n )
{
    int L[m+1][n+1];
    int i, j;
        for (i=0; i<=m; i++)
    {
        for (j=0; j<=n; j++)
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i-1] == Y[j-1])
                L[i][j] = L[i-1][j-1] + 1;
            else
                L[i][j] = max(L[i-1][j], L[i][j-1]);
        }
    }
    return L[m][n];
}


int main()
{
    int n,i,j,k;
    cin>>n;
    
    for (i=0; i<n; i++) {
        cin>>arr1[i];
    }
    for (j=0;j<n-1;j++){  
    for (k=0; k<n; k++) {
        cin>>arr2[k];
    }
        cout<<"\n"<<lcs(arr1,arr2,n,n);  
    }
    
    return 0;
}

Posted: **Tue Jul 08, 2014 1:05 am**

Post your full code.

Posted: **Mon Aug 04, 2014 1:29 am**

Code: Select all

#include <iostream>
using namespace std;
int arr1[10000],arr2[10000];
int lcs( int *X, int *Y, int m, int n )
{
    int L[m+1][n+1];
    int i, j;
    
        for (i=0; i<=m; i++)
    {
        for (j=0; j<=n; j++)
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            
            else if (X[i-1] == Y[j-1])
                L[i][j] = L[i-1][j-1] + 1;
            
            else
                L[i][j] = max(L[i-1][j], L[i][j-1]);
        }
    }
    
    
    return L[m][n];
}


int main()
{
    int n,i,j,k;
    
    cin>>n;
    //int arr1[n],arr2[n];
    for (i=0; i<n; i++) {
        cin>>arr1[i];
    }
    for (j=0;j<n-1;j++){
        
    for (k=0; k<n; k++) {
        cin>>arr2[k];
    }
        
        cout<<"\n"<<lcs(arr1,arr2,n,n);
        
    } 
    return 0;
}

OJ Board

111 - History Grading

Re: 111 Why WA??

Re: 111 Why WA??

Re: 111 Why WA??

Re: 111 Why WA??

111 - History Grading

Re: 111 - History Grading

Re: 111 - History Grading

111 - History Grading WA Please help

Re: 111 - History Grading WA Please help

Re: 111 - History Grading

Re: 111 Why WA??

Re: 111 Why WA??

111 History grading

Re: 111 History grading

Re: 111 History grading