111 - History Grading

[Rinoaheartilly]

I got run time error for this problem even though I got all the right answer. Help please
Here is my code:

Code: Select all

using namespace std;
int longest[20];
int number[20];
int key[20];
int answer[20];
int subscript[20];
void FixOrder(int n, int x[]);
int LCS(int n);
void Clean(int n);
   
int main(){
   int n,k,m, ans, top;
   top = 0;
   m = 1;//start at position 1
   cin>>n;
   while(m<=n){
      cin>>number[m];
      subscript[m] = m;
      m++;
   }
   FixOrder(n,key);
   while(cin>>ans){
      Clean(n);
      for(int i=1; i<=n; i++){
         number[i] = ans;
         subscript[i] = i;
         if(i<n)
            cin>>ans;
      }
      FixOrder(n,answer);
      int f = LCS(n);
      longest[top++] = f;
      cout<<f<<endl;
   }

}
void Clean(int n){
   for(int i=0; i<=n; i++){
      subscript[i] = 0;
   }

}
void FixOrder(int n, int x[]){
   for(int i=1; i<=n; i++){
      x[number[i]] = subscript[i];
   }
}
int LCS(int n){
   int count[20][20];
   int largest = -1;
   for(int i=0; i<=n;i++){
      count[i][0] = 0;
      count[0][i] = 0; 

   }
   for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
         if(answer[i]==key[j]){
            count[i][j] = count[i-1][j-1] + 1;
         }else if(count[i][j-1]>count[i-1][j]){
            count[i][j] = count[i][j-1];
         }else{
            count[i][j] = count[i-1][j];
         }
         if(count[i][j]>largest)
            largest = count[i][j];
      }
   }
   return largest;

}

[Rinoaheartilly]

Never mind. I got AC

[Tanu]

I'm in problen with 111 problem "History Grading"...
plz explain the last out put...
http://acm.uva.es/p/v1/111.html





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 <- Why it is 9

plz help[/url]

[helloneo]

http://online-judge.uva.es/board/viewtopic.php?t=7879

[Tanu]

Thanx it will helpme...

[sumantbhardvaj]

i just do not understand why my code is giving wrong answer.

I have applied LCS ( i think its more convinient to apply than LIS here)..

But recieving Wrong answer continously ..I have also taken care of the fact that the input gives the ranking of the events not the actual ordering..??

Can anyone explain where my code is lacking or provide some fresh test data??

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
class sumant
{
public :
       int a[25];
       int b[25];
       int n,x;
       
       int c[25][25];
       
       void input()
       {
            cin>>n;
                        
            for(int i=1;i<=n;i++)
            {
                     cin>>x;
                     a[x]=i;
            }
            while(cin)
            {
                      for(int i=1;i<=n;i++)
                      {
                              cin>>x;
                              b[x]=i;
                      }
                      int z=doit();
                      cout<<z<<endl;
            }
       }      
       int doit()
       {
            for(int i=0;i<=n;i++)
            {
                    c[i][0]=0;
            }
            for(int i=0;i<=n;i++)
            {
                    c[0][i]=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()
{
    sumant s;
    s.input();
    return 0;
}

[Jan]

Your code doesn't even pass the samples. Check it again. And dont open a new thread if there is one already.

[sumantbhardvaj]

are u talking abt these test cases ( given in the question itself )

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

then my program gives following output

Code: Select all

6
5
10
9

which matches with the one given .

can u be little more precise abt the error ??

[Jan]

My compiler is Ms-Vcc 6. I made an input file and ran your code. In my compiler your code returned

Code: Select all

6
5
10
9
9

For the above input.

[sumantbhardvaj]

Thanx a lot..i got accepted finally

The problem was somewhere here ...

Code: Select all

while(cin)
            {
                      for(int i=1;i<=n;i++)
                      {
                              cin>>x;
                              b[x]=i;
                      }
                      int z=doit();
                      cout<<z<<endl;
            }  

i changed it a bit..

while(cin>>x) // for the first input and then the rest...

and it worked.... but i still could not understand that why my previous code printed the last value twice ...

Could u plz explain that...considering i m a novice coder at UVA

[Jan]

Ok let me explain the following part...

Code: Select all

            while(cin) 
            { 
                      for(int i=1;i<=n;i++) 
                      { 
                              cin>>x; 
                              b[x]=i; 
                      } 
                      int z=doit(); 
                      cout<<z<<endl; 
            }

After the last input, when 'while(cin)' line is executed it returns true. So execution continues. While 'cin>>x;' is executed it uses the last value which is 6. So, your code takes' 6 6 6 ... n times' and then the output becomes 9.
Hope you understand.

[joebin]

Please note that what is given in the input is the position of the i-th event in the chronological order, for example, in your input:

10
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6

that means that in the correct order, event 1 is in the 3rd position, event 2 is in the first position..., like this:

2 3 1 4 6 8 10 9 5 7

Yandry.

sorry,i don't understand it,either.
why 2 10 1 3 8 4 9 5 7 6 -> 2 3 1 4 6 8 10 9 5 7 ??
could u explain it in detail ?

[Jan]

Check carefully...

You are given

Code: Select all

10 
3 1 2 4 9 5 10 6 8 7

Code: Select all

 1  2  3  4  5  6  7  8  9 10
 |  |  |  |  |  |  |  |  |  |
 3  1  2  4  9  5 10  6  8  7

 1 should be placed in 3rd position
 2 should be placed in 1st position
 3 should be placed in 2nd position
 4 should be placed in 4th position
 ...
So, the ordering becomes
 2  3  1  4  6  8 10  9  5  7

Hope it helps.

[joebin]

thanx a lot !!

[dttri]

Check carefully...

You are given

Code: Select all

10 
3 1 2 4 9 5 10 6 8 7

Code: Select all

 1  2  3  4  5  6  7  8  9 10
 |  |  |  |  |  |  |  |  |  |
 3  1  2  4  9  5 10  6  8  7

 1 should be placed in 3rd position
 2 should be placed in 1st position
 3 should be placed in 2nd position
 4 should be placed in 4th position
 ...
So, the ordering becomes
 2  3  1  4  6  8 10  9  5  7

Hope it helps.

Sorry for this post, because I don't understand clearly.
If the events is ordered as in your diagram, can you tell me why the test:

3 1 2 4 9 5 10 6 8 7 (with exactly the second line)

has a result 10? Because I can see that the first number (3) is in wrong order (3 must be at position 2, is it right?)

Thank you

[edit]
I already understand. Must apply the above rule for students' submission also. Thanks.
[/edit]