111 - History Grading

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tzupengwang
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

Re: 111 Why WA??

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 111 Why WA??

Post by brianfry713 »

Try sample input 1
Check input and AC output for thousands of problems on uDebug!

tzupengwang
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

Re: 111 Why WA??

Post by 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
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

Re: 111 Why WA??

Post by 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
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

111 - History Grading

Post by @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
-@ce

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

Re: 111 - History Grading

Post by brianfry713 »

Check input and AC output for thousands of problems on uDebug!

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 111 - History Grading

Post by @ce »

thanks a lot...i got AC :)
-@ce

MauriWilde
New poster
Posts: 14
Joined: Sun Jan 20, 2013 1:58 am

111 - History Grading WA Please help

Post by 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
Last edited by MauriWilde on Sun Jan 20, 2013 6:04 am, edited 1 time in total.

MauriWilde
New poster
Posts: 14
Joined: Sun Jan 20, 2013 1:58 am

Re: 111 - History Grading WA Please help

Post by MauriWilde »

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

Deboraha
New poster
Posts: 1
Joined: Thu Jan 24, 2013 8:07 am

Re: 111 - History Grading

Post by 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
New poster
Posts: 5
Joined: Fri Nov 15, 2013 2:06 pm

Re: 111 Why WA??

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 111 Why WA??

Post by brianfry713 »

Yes you can solve it in O(n * n) using LCS, or O(n log n) using LIS.
Check input and AC output for thousands of problems on uDebug!

xnorax
New poster
Posts: 9
Joined: Thu Jun 26, 2014 9:31 pm

111 History grading

Post by xnorax »

I used longest common subsequence algorithm, and I have right output :D , 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 111 History grading

Post by brianfry713 »

Post your full code.
Check input and AC output for thousands of problems on uDebug!

xnorax
New poster
Posts: 9
Joined: Thu Jun 26, 2014 9:31 pm

Re: 111 History grading

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

Post Reply

Return to “Volume 1 (100-199)”