Moderator: Board moderators

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

### Re: 111 Why WA??

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

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

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

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

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

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

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

MauriWilde
New poster
Posts: 14
Joined: Sun Jan 20, 2013 1:58 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
``````
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

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

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

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

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

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

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

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

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