Page 6 of 10
111!!! Run time error!!! Help please
Posted: Mon Sep 26, 2005 5:38 am
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;
}
Posted: Thu Sep 29, 2005 9:10 pm
by Rinoaheartilly
Never mind. I got AC
111 plz Xplain da out put
Posted: Thu Nov 24, 2005 11:31 am
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]
search first..
Posted: Thu Nov 24, 2005 4:17 pm
by helloneo
Thanx
Posted: Thu Nov 24, 2005 4:21 pm
by Tanu
Thanx it will helpme...
111 - History Grading
Posted: Fri Nov 10, 2006 4:22 pm
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;
}
Posted: Sat Nov 11, 2006 4:29 pm
by Jan
Your code doesn't even pass the samples. Check it again. And dont open a new thread if there is one already.
Posted: Sat Nov 11, 2006 8:18 pm
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
which matches with the one given .
can u be little more precise abt the error ??
Posted: Sat Nov 11, 2006 9:12 pm
by Jan
My compiler is Ms-Vcc 6. I made an input file and ran your code. In my compiler your code returned
For the above input.
Posted: Sat Nov 11, 2006 11:19 pm
by 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
Posted: Sun Nov 12, 2006 1:22 pm
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.
Posted: Wed Jan 10, 2007 4:31 pm
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.
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 ?
Posted: Wed Jan 10, 2007 11:15 pm
by Jan
Check carefully...
You are given
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.
Posted: Thu Jan 11, 2007 6:22 am
by joebin
thanx a lot !!
Posted: Thu Apr 05, 2007 7:18 pm
by dttri
Jan wrote:Check carefully...
You are given
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]