111  History Grading
Moderator: Board moderators
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
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
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
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

 New poster
 Posts: 1
 Joined: Sun Feb 15, 2004 8:29 am
111  Free Pascal doesn't work
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 i1 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<=i1; 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.
[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 i1 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<=i1; 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.
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)
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
 E. W. Dijkstra
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
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
Thanks for help, but if you could please answer it too ;]Then it becomes clear why the answer is 9
kiha
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.
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
 E. W. Dijkstra

 New poster
 Posts: 16
 Joined: Sun Mar 07, 2004 12:19 pm
 Location: Dhaka
why wa 111 history grading
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]
[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]
111: when do the inputs end?
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.)
by EOF, null, or single # and so on???
I'm working in Java.
please help me!
(sorry, i'm not good at English.)
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
 E. W. Dijkstra
thankx epsilon for the explanation
iT was quite easy to get AC with this understaning of the inputs!