Page 7 of 10
111 (History Grading)
Posted: Sat Apr 28, 2007 7:21 am
by owokko
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;
}
Posted: Sat Apr 28, 2007 10:42 am
by shamim
add the following line:
the function max is defined there, although your compiler might have it declared as default.
Posted: Sat Apr 28, 2007 2:44 pm
by owokko
shamim wrote:add the following line:
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?
Posted: Sat Apr 28, 2007 3:19 pm
by helloneo
Posted: Sat Apr 28, 2007 4:03 pm
by owokko
Thx for reply.
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
Posted: Mon Jul 23, 2007 12:28 pm
by andysoft
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
readln (n);
for i:=1 to n do
begin
read (l);
a[l] := i
end;
while not eof do
begin
for i:=1 to n do
begin
read (l);
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.
Posted: Mon Aug 13, 2007 11:18 am
by andysoft
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)??
Thanx in advance!!!
Posted: Mon Aug 27, 2007 1:27 pm
by andysoft
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?
Posted: Thu Jan 17, 2008 12:37 am
by Farnak
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???
Posted: Thu Jan 17, 2008 3:16 pm
by Jan
The first one is correct.
Posted: Sat Jan 19, 2008 11:28 pm
by Farnak
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?
Posted: Sun Jan 20, 2008 2:04 pm
by Jan
Posted: Mon Jan 21, 2008 9:30 pm
by Farnak
Ah, thanks Jan!
I read the link and I got AC, I'll be more thorough with searching the forum next time.
Re: 111 Why WA??
Posted: Wed Nov 12, 2008 2:19 pm
by vinocit
Gr8 understanding Jan thanks
Posted: Sun Dec 21, 2008 3:26 pm
by cfbbq
hi,please help me!
I understand all above,but I still get "WA"....
My code: