111 - History Grading

[tzupengwang]

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

Code: Select all

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

[brianfry713]

Try sample input 1

[tzupengwang]

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

6
5
10
9

I think it's correct

[tzupengwang]

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~

[@ce]

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

[brianfry713]

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

[@ce]

thanks a lot...i got AC

[MauriWilde]

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

[MauriWilde]

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

[Deboraha]

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.

[chanderg_12]

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.

[brianfry713]

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

[xnorax]

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

[brianfry713]

Post your full code.

[xnorax]

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