111 - History Grading

[bigredteam2000]

Why the longest increasing subsequence algorithm does not work?

//@begin_of_source_code
/* @JUDGE_ID: 15975FF 111 C++ */

//This is the longest increasing subsequence //algorithm.

#include<iostream.h>


int n;
int A[40];
int B[40];
int C[40];

int Find(int x)
{
int i;
for(i =1; i<= n; i++)
{
if(A == x)
return i;
}
}

int LC()
{
int i,j;
int max;
//bool changed;
int bj, bi;


C[1] = 1;
for( i = 2; i <= n; i++)
{
max = 1;
//changed = false;
for(j = i-1; j >= 1; j--)
{
bj = Find(B[j]);
bi = Find(B);
if(bj < bi && C[j] >= max)
{
//changed = true;
max = C[j]+1;
}
}
C = max;
}
max = 1;
for(i =1; i<= n; i++)
if(C > max)
max = C;
return max;

}

int main()
{
int i;
int points;

cin>>n;
for(i = 1; i <= n; i++)
cin >> A;
//for(i = 1; i <= n; i++)
// cout << A << ' ';
//cout << endl;

while(cin >> B[1])
{
for(i = 2; i <=n; i++)
cin >> B;
//for(i = 1; i <= n; i++)
//cout << B <<' ';
//cout << endl;
points = LC();
cout << points << endl;

}

return 0;
}

//@end_of_source_code

[FCS]

Does your program give the correct output for the sample input?

Read the question carefully:

You are given the ranking of event i (ci) in chronological order, which means that
order[ci]=i; ci tells you the position of event i in chronological order. So your maximal increasing subsequence should not be run on the values of ci given directly...

[seolv]

i had same problem before.

if your program work well with test case,

check the handling part of multiple input.

[junjieliang]

Multiple Input? But my program gets AC and it reads in only one test case! Then again, wierd things do happen with the problems now and then...

[FlyDeath]

#include <stdio.h>

int max(int l1x,int l1y,int l2x,int l2y);

int length[20][20];

void main()
{
int len;
int correct[20];
int corder[20];
int aorder[20];
int ans[20];
int i,j;
scanf("%d",&len);
for(i=0;i<len;i++)
scanf("%d",&correct);
for(i=0;i<len;i++)
corder[correct-1]=i;
while(scanf("%d",&ans[0])!=EOF)
{
for(i=1;i<len;i++)
scanf("%d",&ans);
for(i=0;i<len;i++)
aorder[ans-1]=i;
for(i=1;i<20;i++)
for(j=0;j<20;j++)
length[j]=0;
for(i=0;i<len;i++)
{
for(j=0;j<len;j++)
{
if(corder==aorder[j])
{
if(i==0||j==0)
length[j]++;
else
length[j]=length[i-1][j-1]+1;
}
else
{
length[j]=max(i-1,j,i,j-1);
}
}
}
printf("%dn",length[len-1][len-1]);
}
}

int max(int l1x,int l1y,int l2x,int l2y)
{
int result=0;
int len1,len2;
if(l1x<0||l1x<0)
len1=0;
else
len1=length[l1x][l1y];
if(l2x<0||l2y<0)
len2=0;
else
len2=length[l2x][l2y];
if(len1>=len2)
return len1;
else
return len2;
}


it works fine with the test files
but i don't know how it got WA

[cyfra]

Hi!

I don't write in C but i think you could make the same mistake I did.

If you read the task you will see that there is a difference beetween ordering and ranking.

The task is quite similar to problem with SDI defence (i don't remember the number)

My program also solved the test datas.

I made a mistake here...
I hope it will help you ...

Good Luck

[paulhryu]

Really, I don't get this problem. See, we have sample test 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

Well, I see that the correct order is: 3 1 2 4 9 5 10 6 8 7, so look at the second student's sequence: 4 7 2 3 10 6 9 1 5 8. Then, supposing we replace this with the correct order given by 3 1 2 4 9 5 10 6 8 7 and make it so that 3 is replaced by 1 since it is the first event, 1 is replaced by 2 since it's the second, and so on, we get

4 7 2 3 10 6 9 1 5 8 to
4 10 3 1 7 8 5 2 6 9, and the student supposedly gets 5 points for this... but how? I mean do you see a sequence of 5 increasing numbers there? The longest is 1 2 6 9 or originally 3 1 5 8, and I cannot see a longer correctly ranked sequence.

Please, help... am I completely messing this up?

<font size=-1>[ This Message was edited by: paulhryu on 2002-02-05 01:41 ]</font>

[FlyDeath]

Well....
"order" and "rank" is not the same

[idler]

Then, in input 2, how can the student get 9?

[pochmann]

Thanks for posting the header with your passwd. I like free test accounts

Stefan

[idler]

Oh, how silly I am.
I understand the meaning.
But the OJ System is down.

[C8H10N4O2]

Here is my Accepted code. Hope it helps you with your algorithm.

#include <stdio.h>

int N,AnswerKey[20],Answer[20],AnswerTable[20],TranslatedAnswer[20];

int CalculateGrade(int i)
{
int k,m,Sum,Max;
Sum=0;
for(k=i+1;k<N;k++)
{
if(TranslatedAnswer[k]>TranslatedAnswer)
Sum++;
}
if(0==Sum)
{
return 1;
}
else
{
Max=0;
for(k=i+1;k<N;k++)
{
if(TranslatedAnswer[k]>TranslatedAnswer)
{
m=CalculateGrade(k);
if(m>Max)
{
Max=m;
}
}
}
return 1+Max;
}
}

main()
{
int i,k,m;

scanf("%d",&N);

for(i=0;i<N;i++)
{
scanf("%d",&AnswerKey);
}

while(scanf("%d",&Answer[0])!=EOF)
{
for(i=1;i<N;i++)
{
scanf("%d",&Answer);
}

for(i=0;i<N;i++)
{
TranslatedAnswer[Answer-1]=AnswerKey;
}

m=0;
for(i=0;i<N;i++)
{
k=CalculateGrade(i);
if(k>m)m=k;
}
printf("%dn",m);
}
}

[ec3_limz]

Hi.

The 2nd and 4th test case for the second sample input/output in Problem #111 seems to be incorrect. For specifics, here they are:

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

Source: http://acm.uva.es/p/v1/111.html

When the line "4 7 2 3 10 6 9 1 5 8" is input, the output "4" appears (it is 5 in the sample output). Similarly, when "2 10 1 3 8 4 9 5 7 6" is input, the output "5" appears (it is 9 in sample output). I believe that these are mistakes in the sample output.

Can anyone either confirm it, or prove me wrong? If the sample input/output are correct, then can you show me how they are correct (by pointing out the sequence)?

Other than these two sample input/output, my code works for all other sample input/output.

Regards,
ec3_limz

[10153EN]

I can surely said that the sample input and output is of no problem.

Please read the problem description clearer, especially what's specified in the "exclamation mark" symbol.

[ec3_limz]

I have read every single word carefully in the problem description.

In the "exclamation mark", the site says, "18/04/01, Warning: Read carefully the description and consider the difference between 'ordering' and 'ranking'."

Anyone can tell me what part I have missed out? I mean, in my code, I used Dynamic Programming to determine the longest sequence in which all events are in the correct order relative to one another. Is that all to the problem? If not, what have I missed out?

Regards,
ec3_limz