Moderator: Board moderators

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

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;
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)
{
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
Does your program give the correct output for the sample input?

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

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

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

int length;

void main()
{
int len;
int correct;
int corder;
int aorder;
int ans;
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)!=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
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.

Good Luck paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
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
Well....
"order" and "rank" is not the same

idler
New poster
Posts: 9
Joined: Thu Feb 21, 2002 2:00 am
Location: China
Then, in input 2, how can the student get 9?

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Thanks for posting the header with your passwd. I like free test accounts Stefan

idler
New poster
Posts: 9
Joined: Thu Feb 21, 2002 2:00 am
Location: China
Oh, how silly I am.
I understand the meaning.
But the OJ System is down. C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Here is my Accepted code. Hope it helps you with your algorithm.

#include <stdio.h>

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

main()
{
int i,k,m;

scanf("%d",&N);

for(i=0;i<N;i++)
{
}

{
for(i=1;i<N;i++)
{
}

for(i=0;i<N;i++)
{
}

m=0;
for(i=0;i<N;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

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~

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