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

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by 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
kiha

ernest
New poster
Posts: 7
Joined: Fri Feb 13, 2004 5:01 pm

LCS

Post by ernest »

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

best regards,
--ernesto

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by 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
kiha

Nikolay Grebenshikov
New poster
Posts: 1
Joined: Sun Feb 15, 2004 8:29 am

111 - Free Pascal doesn't work

Post by 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. 8)

What's the different in these programs.

Kentaro
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
Location: Canada, eh?

Post by 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)
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by 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 ;]
kiha

Kentaro
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
Location: Canada, eh?

Post by 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.
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by 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
kiha

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka

why wa 111 history grading

Post by 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
New poster
Posts: 1
Joined: Tue Feb 10, 2004 6:53 am

111: when do the inputs end?

Post by 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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

I believe at end of input

Kentaro
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
Location: Canada, eh?

Post by 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.
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

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

vladrac
New poster
Posts: 7
Joined: Mon Sep 20, 2004 4:09 am
Location: Brazil

thankx epsilon for the explanation

Post by vladrac »

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

eleusive
New poster
Posts: 9
Joined: Tue Sep 28, 2004 6:57 am
Location: United States

Post by eleusive »

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

Post Reply

Return to “Volume 1 (100-199)”