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

Post Reply
Rinoaheartilly
New poster
Posts: 9
Joined: Thu Oct 14, 2004 6:37 am
Location: North Carolina

111!!! Run time error!!! Help please

Post by 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
New poster
Posts: 9
Joined: Thu Oct 14, 2004 6:37 am
Location: North Carolina

Post by Rinoaheartilly »

Never mind. I got AC
Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

111 plz Xplain da out put

Post by 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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

search first..

Post by helloneo »

Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

Thanx

Post by Tanu »

Thanx it will helpme...
sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:

111 - History Grading

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Your code doesn't even pass the samples. Check it again. And dont open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage
sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage
sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:

Post by sumantbhardvaj »

Thanx a lot..i got accepted finally :D :D

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 :wink:
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage
joebin
New poster
Posts: 12
Joined: Fri Dec 29, 2006 7:18 am
Location: Taiwan
Contact:

Post by joebin »

neno_uci wrote: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. 8)
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage
joebin
New poster
Posts: 12
Joined: Fri Dec 29, 2006 7:18 am
Location: Taiwan
Contact:

Post by joebin »

thanx a lot !!
dttri
New poster
Posts: 3
Joined: Thu Apr 05, 2007 7:13 pm
Location: Vietnam

Post by dttri »

Jan wrote: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]
Post Reply

Return to “Volume 1 (100-199)”