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)

Post by owokko » Sat Apr 28, 2007 7:21 am

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.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Apr 28, 2007 10:42 am

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

Post by owokko » Sat Apr 28, 2007 2:44 pm

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

Post by helloneo » Sat Apr 28, 2007 3:19 pm


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

Post by owokko » Sat Apr 28, 2007 4:03 pm

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

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Mon Jul 23, 2007 12:28 pm

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.
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:

Post by andysoft » Mon Aug 13, 2007 11:18 am

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!!!
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:

Post by andysoft » Mon Aug 27, 2007 1:27 pm

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? :) :o
Now I lay me down to sleep...
my profile

Farnak
New poster
Posts: 4
Joined: Wed May 24, 2006 9:15 pm
Location: Windsor, Canada

Post by Farnak » Thu Jan 17, 2008 12:37 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jan 17, 2008 3:16 pm

The first one is correct.

Farnak
New poster
Posts: 4
Joined: Wed May 24, 2006 9:15 pm
Location: Windsor, Canada

Post by Farnak » Sat Jan 19, 2008 11:28 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jan 20, 2008 2:04 pm


Farnak
New poster
Posts: 4
Joined: Wed May 24, 2006 9:15 pm
Location: Windsor, Canada

Post by Farnak » Mon Jan 21, 2008 9:30 pm

Ah, thanks Jan! :D
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??

Post by vinocit » Wed Nov 12, 2008 2:19 pm

Gr8 understanding Jan thanks :D

cfbbq
New poster
Posts: 1
Joined: Sun Dec 21, 2008 3:15 pm

Post by cfbbq » Sun Dec 21, 2008 3:26 pm

hi,please help me!
I understand all above,but I still get "WA"....
My code:

Code: Select all

remove after AC

Post Reply

Return to “Volume 1 (100-199)”