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

owokko
New poster
Posts: 7
Joined: Sat Apr 28, 2007 7:11 am

### 111 (History Grading)

I get a problem with 111. http://acm.uva.es/p/v1/111.html

It an application with LCS, I have 2 method for LCS (LCS1 and LCS2 in code)

My code can run in my computer but get "compiler ERROR" in online-judge,and I do not know WHY!!

Please get me some hints, thanks.

here are my code (c++):

Code: Select all

``````//Question http://acm.uva.es/p/v1/111.html
//CPU: , Memory:
//state:

#include <iostream>
#include <cmath>

using namespace std;

int LCS1(int *A, int i, int*B, int j)
{
if(i==0 | j==0)
return 0;
else if( A[i]==B[j] )
return LCS1(A, i-1, B, j-1)+1;
else
return max( LCS1(A, i, B, j-1), LCS1(A, i-1, B, j) );
}

int LCS2(int *A, int*B, int n)
{
int c[n+1][n+1];

for(int i=0; i<=n; i++)
c[i][0] = 0;
for(int j=0; j<=n; j++)
c[0][j] = 0;

for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if( A[i]==B[j] )
c[i][j] = c[i-1][j-1]+1;
else if(c[i-1][j] >= c[i][j-1])
c[i][j] = c[i-1][j];
else
c[i][j] = c[i][j-1];
}
}
return c[n][n];
}

int main()
{
int n;
cin >> n;

if(cin.fail() || n<2 || n>20)
return 0;

int *A = new int[n+1];
for(int i=1; i<=n; i++)
{
int temp;
cin >> temp;
A[temp] = i;
}

int *B = new int[n+1];
while(true){
for(int i=1; i<=n; i++)
{
int temp;
cin >> temp;
B[temp] = i;
}
cout << LCS1(A, n+1, B, n+1) << "\n";
cout << LCS2(A, B, n) << "\n";
if(cin.eof())
break;
}

delete A;
A=NULL;
delete B;
B=NULL;

//system("PAUSE");
return 0;
}``````
Last edited by owokko on Wed May 09, 2007 6:17 am, edited 1 time in total.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
add the following line:

Code: Select all

``#include<algorithm>``
the function max is defined there, although your compiler might have it declared as default.

owokko
New poster
Posts: 7
Joined: Sat Apr 28, 2007 7:11 am
shamim wrote:add the following line:

Code: Select all

``#include<algorithm>``
the function max is defined there, although your compiler might have it declared as default.

Thx a lot.

online-judge will not get "Compiler ERROR"

but I get "Wrong answer"?!

woulu you get me some example of Input , the input from http://acm.uva.es/p/v1/111.html for my code are all rirgt, all my testing are right.

or the output of are not match the request of problem 111?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

owokko
New poster
Posts: 7
Joined: Sat Apr 28, 2007 7:11 am

But I still get WA.
What wrong with my code??

If the bug of my code is input or output, will you get me some hints or example, I am a new one to ACM, and usually get problem with input and output.

Regards

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Well, I had this mistake with double printing last answer too, but I fixed it and still get WA.

Code: Select all

``````program Project2;

{\$R-}{\$S-}{\$Q-}
{\$APPTYPE CONSOLE}
type
integer = longint;

var
i,j,l,m,n: integer;
a,b: array [1..30] of integer;
c: array [0..30,0..30] of integer;
begin

for i:=1 to n do
begin
a[l] := i
end;

while not eof do
begin
for i:=1 to n do
begin
if (i<n) and eof then exit;
b[l] := i;
end;
m := 0;
for i:=0 to n+1 do
for j:=0 to n+1 do
c[i][j] := 0;

for i:=2 to n+1 do
for j:=2 to n+1 do
begin
if a[i-1]=b[j-1] then
c[i][j] := c[i-1][j-1]+1
else if (c[i-1][j]>=c[i][j-1]) then
c[i][j] := c[i-1][j]
else
c[i][j] := c[i][j-1];
if c[i][j] > m then
m := c[i][j]
end;

writeln (m);

end;

end.
``````
Last edited by andysoft on Mon Aug 13, 2007 12:58 pm, edited 1 time in total.
Now I lay me down to sleep...
my profile

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Hi again!
As you, see I understood everything about the problem, but this WA is very-very annoying. Can anyone provide me test cases (probably tricky, but not connected with rank/order difference)??

Now I lay me down to sleep...
my profile

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Another hello to everyone!
I have finally got AC for this problem, but do you know how? You'll never guess. I have copied my pascal code to C++ editor, and command-by-command, operator-by-operator, variable-by-variable and so on I have translated my PAS code to PURE C code. When I have submitted, the first Judge verdict was ACCEPTED!!!
Unbeleivable!!!
And more shocking thing is that I had the same situation with 10038 task today!! : WA in PAS, but after translating to C/C++ it gave AC from the first time!!!!

HOW can it be?
Now I lay me down to sleep...
my profile

Farnak
New poster
Posts: 4
Joined: Wed May 24, 2006 9:15 pm
Hi everyone,

I'm using the site http://icpcres.ecs.baylor.edu/onlinejudge/index.php, and when I browse the problem on their site I get:

Sample Output 2

6
5
10
9

But when I open the problem on pdf I get the following:

Sample Output 2

6
4
10
5

Which one is the correct output???

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
The first one is correct.

Farnak
New poster
Posts: 4
Joined: Wed May 24, 2006 9:15 pm
Okay, I don't think I understand what the problem is really asking for then.

Sample Input:
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

I thought they wanted to know the length of the longest common subsequence between the first sequence and the following sequences, however in their sample output they give the answer "9" for the sequence "2 10 1 3 8 4 9 5 7 6" but there is definitely no subsequence of length 9 shared by that sequence and "3 1 2 4 9 5 10 6 8 7".

Could someone please clarify the problem statement for me?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Farnak
New poster
Posts: 4
Joined: Wed May 24, 2006 9:15 pm
Ah, thanks Jan!
I read the link and I got AC, I'll be more thorough with searching the forum next time.

vinocit
New poster
Posts: 10
Joined: Mon Oct 13, 2008 10:11 am

### Re: 111 Why WA??

Gr8 understanding Jan thanks

cfbbq
New poster
Posts: 1
Joined: Sun Dec 21, 2008 3:15 pm
``remove after AC``