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
bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am

Post by bigredteam2000 » Sun Dec 02, 2001 2:14 pm

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
New poster
Posts: 9
Joined: Mon Oct 15, 2001 2:00 am

Post by FCS » Tue Dec 04, 2001 3:50 am

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
New poster
Posts: 11
Joined: Wed Oct 24, 2001 2:00 am

Post by seolv » Mon Dec 17, 2001 8:19 am

i had same problem before.

if your program work well with test case,

check the handling part of multiple input.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Tue Dec 18, 2001 3:35 am

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

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Wed Jan 02, 2002 5:50 pm

#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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Thu Jan 31, 2002 3:46 pm

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

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by paulhryu » Tue Feb 05, 2002 2:40 am

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
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Tue Feb 05, 2002 7:09 am

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

idler
New poster
Posts: 9
Joined: Thu Feb 21, 2002 2:00 am
Location: China

Post by idler » Sun Feb 24, 2002 8:49 am

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

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by pochmann » Sun Feb 24, 2002 10:37 am

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

Stefan

idler
New poster
Posts: 9
Joined: Thu Feb 21, 2002 2:00 am
Location: China

Post by idler » Sun Feb 24, 2002 3:24 pm

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

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Thu Feb 28, 2002 6:48 am

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
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Need help in Problem #111: History Grading

Post by ec3_limz » Thu May 23, 2002 3:37 pm

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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

HI~

Post by 10153EN » Thu May 23, 2002 4:06 pm

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
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Post by ec3_limz » Fri May 24, 2002 12:48 pm

:(

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

Post Reply

Return to “Volume 1 (100-199)”