111 - History Grading

[kiha]

Er ... and ?
I don't understand it. Every method I use gives me the wrong output! What to do with the RANK sequence? :/
Of course I understand the way you get
2 3 1 4 6 8 10 9 5 7 from
3 1 2 4 9 5 10 6 8 7 , but what to do with this

2 3 1 4 6 8 10 9 5 7 ??
I hope you understand what don't I understand
Please help

[ernest]

The input examples are just fine, I also used LCS and got AC,
I guess you are doing something wrong.

best regards,

[kiha]

Grrrrrrr , me is confused
But I ain't understand what to use LCS on :/
If you get AC, please explain me this

[click xx wrote :
And the last sequence in the input can be changed into:
3 1 4 6 8 10 9 5 7 2
Now you can see clearly why the ouput is 9. ]

If you explained me why the output is 9, it would be a great help
with regards

[Nikolay Grebenshikov]

I had written 111 problem with Free Pascal:

[pascal]
type
elem = record
index:integer;
count:integer;
end;
var
right_seq: array [1..20] of integer;
seq: array [1..20] of elem;
test, num, nn,i: integer;

procedure BuildCounts;
var
i,j:integer;
begin
for i:=1 to nn do begin
seq.count := 1;
for j:=1 to i-1 do
if (seq.index > seq[j].index) and
(seq.count < seq[j].count+1) then
seq.count := seq[j].count+1;
end;
end;

function GetMax:integer;
var
i,j:integer;
begin
j:=seq[1].count;
for i:=2 to nn do
if (j < seq.count) then j := seq.count;
GetMax := j;
end;

begin
read(input, nn);
for i:=1 to nn do
read(input, right_seq);
test := 0;
while not eof(input) do begin
if eoln(input) then begin
readln(input);
continue;
end;

for i:=1 to nn do begin
read(input, num);
seq[num].index := right_seq;
end;

if test=0 then test:=1 else writeln;
BuildCounts;
num:=GetMax;
write(output, num:1);
end;
end.
[/pascal]

But this program got WA and I rewrote this problem with the same algorithm on C++:

[cpp]#include <stdio.h>

#define MAX 21

typedef struct ELEM {
int index;
int count;
};

int nn;
int right_seq[MAX];
ELEM seq[MAX];
FILE *fIn, *fOut;

int ReadStr(void) {
int num;

for (int i=1; i<=nn; i++) {
if (fscanf(fIn, "%d",&num) == EOF) return 0;
seq[num].index = right_seq;
}
fscanf(fIn, "\n");
return 1;
}
void BuildCounts(void) {
for (int i=1; i<=nn; i++) {
seq.count = 1;
for (int j=1; j<=i-1; j++) {
if ((seq[i].index > seq[j].index) && (seq[i].count < seq[j].count+1))
seq[i].count = seq[j].count+1;
}
}
}

int GetMax(void) {
int temp=seq[1].count;
for (int i=2; i<=nn; i++)
if (temp < seq[i].count) temp=seq[i].count;
return temp;
}

int main (void) {
fIn = stdin;
fOut = stdout;

fscanf(fIn, "%d\n", &nn);
for (int i=1; i<=nn; i++) {
fscanf(fIn, "%d",&right_seq[i]);
}
fscanf(fIn, "\n");

while (ReadStr()) {
BuildCounts();
fprintf(fOut, "%d\n", GetMax());
}

}[/cpp]

And it got AC.

What's the different in these programs.

[Kentaro]

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

This is the second sample input.
But the numbers represent the ranking of the events, not the actual order of the events themselves. So the actual correct ordering of the events in this input case is:

2 3 1 4 6 8 10 9 5 7
This is the actual event numbers and the leftmost event is first and the rightmost event is last.

Now, for one of the student orderings. 2 10 1 3 8 4 9 5 7 6 is not the order of the events, just the ranking. So to convert it into an ordering:

3 1 4 6 8 10 9 5 7 2
Once again, the leftmost event is first and the rightmost event is last.

Then it becomes clear why the answer is 9. See, you can't just take the length of the LCS of the correct and student sequences as they appear in the input and expect to get the right answer. Surprised me too.
(I've written this all as carefully as possible but I may have made a mistake)

[kiha]

Sorry for being stupid, but I don't understand it:

You have
3 1 4 6 8 10 9 5 7 2 -- the ranking of events made by a student
and
3 1 2 4 9 5 10 6 8 7 -- the correct ranking of events

And where there is 9 ? :/
To make it clear, I understand everything up to

Then it becomes clear why the answer is 9

Thanks for help, but if you could please answer it too ;]

[Kentaro]

Each number r in the sequence means that event i has rank r. So let's look at the correct sequence as given in the input.

3 1 2 4 9 5 10 6 8 7

This means:
event 1 has rank 3
event 2 has rank 1
event 3 has rank 2
event 4 has rank 4
event 5 has rank 9
event 6 has rank 5
event 7 has rank 10
event 8 has rank 6
event 9 has rank 9
event 10 has rank 7

So if we order the sequence of events in terms of ranks, this is what we get:
2 3 1 4 6 8 10 9 5 7 (Please verify this yourself)
The leftmost event is first (lowest rank) and the rightmost event is last (highest rank). In other words, 2 is the earliest event and 7 is the latest event.

So now let's see a student sequence from the same input.
2 10 1 3 8 4 9 5 7 6

Doing the same translation:
event 1 has rank 2
event 2 has rank 10
event 3 has rank 1
event 4 has rank 3
event 5 has rank 8
event 6 has rank 4
event 7 has rank 9
event 8 has rank 5
event 9 has rank 7
event 10 has rank 6

So if we order this sequence of events in terms of rank, this is what we get:
3 1 4 6 8 10 9 5 7 2 (Once again please verify this)
Once again, the numbers in this new sequence represent the ordering of the events so 3 is the earliest event and 2 is the latest event.

Now compare:
2 3 1 4 6 8 10 9 5 7 (correct)
3 1 4 6 8 10 9 5 7 2 (student)

The sequence "3 1 4 6 8 10 9 5 7" is the longest contiguous sequence of events that are ordered correctly relative to each other (longest common subsequence). Now do you see why the answer is 9? Again, you can't just take the LCS of the sequences as they appear in the input.

[kiha]

On holy potatoes !

Thanks, I understand everything now, I think.
I'm gonna write it when I had time.
Thanks once more
With kind regards

[Salmin Sultana]

i used lcs for this prigram so why wa?
[cpp]#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int cor[40],stu[40],array[40][40],n;

void work()
{
int i,j;

for(i=0;i<40;i++)
memset(array,0,sizeof(int)*40);

for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(stu==cor[j])
array[i+1][j+1]=array[j]+1;
else if(array[j+1]>=array[i+1][j])
array[i+1][j+1]=array[j+1];
else
array[i+1][j+1]=array[i+1][j];
}

printf("%d\n",array[n][n]);
return;
}
int main()
{
int i,in,len,d;
char str[1000],s[1000],s1[1000];

gets(s);
sscanf(s,"%d",&n);

gets(str);
in=0;
len=strlen(str);

for(i=0;i<len;){

while(str==' ')
i++;
sscanf(&str,"%s",s);
i=i+strlen(s)+1;

cor[in]=atoi(s);
in++;
}
while(gets(s)){

if(s[0]){
if(!strcmp(str,s))
printf("%d\n",n);
else{

len=strlen(s);
in=0;
for(i=0;i<len;){

while(s==' ')
i++;
sscanf(&s,"%s",s1);
i=i+strlen(s1)+1;

stu[in]=atoi(s1);
in++;
}
work();
}
}
}
return 0;
}
[/cpp]

[Hana]

I cannot understand when the inputs end.

by EOF, null, or single # and so on???

I'm working in Java.

please help me!

(sorry, i'm not good at English.)

[junbin]

I believe at end of input

[Kentaro]

If you're using the length of LCS algorithm on the sequences exactly as they appear in the input, you are out of luck. There is a subtlety to this problem that you haven't accounted for. I compiled your code on my own system and run the Sample Input 2 on it and gotten the wrong answer. Sample Input 2 is precisely the input data that clued me in to how the problem should really be solved (I was doing the same as you before). There's another thread about #111 - History Grading on here where I detail exactly how length of LCS can be applied to this problem.

[chunyi81]

Please read the input specifications carefully, the input numbers are the rankings of the events, not the actual order of the events.

[vladrac]

iT was quite easy to get AC with this understaning of the inputs!

[eleusive]

Yes, I think that "ordering" vs "ranking" should have been stated more clearly in the problem statement.