111 - History Grading

[10153EN]

Could you answer me a question 1st, as the exclamation mark asks, what's the difference between "ordering" and "ranking"?

[click xx]

I think you can explain it in this way:
the ith number j in the input means the ith thing appears in the jth position
during the history.Isn't it?
And if you change sequence to another way:
the ith number j in the sequence means thing j happen in the ith position during te history.
So the first sequence in the input can be changed into:
2 3 1 4 6 8 10 9 5 7
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.
I understand the problem in this way and solve the problem.Good luck to you !

[dawynn]

OK, first I'm confused by the sample input/output on 111. Sample 1 looks correct. Sample output 2 does not match the sample input. At least assuming that the problem description can be trusted.

Here's the 2nd sample input:
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

Which would produce the following (corrected!) output:
6
4
10
5

Having said that, I'm still not sure why I would be getting WA. Here's my code:
// this part edited out //

[Ivan Golubev]

Why not to read this http://acm.uva.es/board/viewtopic.php?t=524 before posting?

[dawynn]

Um... Because it didn't show up in the search. Is there something wrong with the search for this forum?

[nghiank]

test

[ezra]

Did your program work well with the sample input given by the judge ?
I think the sample is completely enough to describe the problem.

[nghiank]

test

[epsilon0]

give up, the judge is wrong.

just look at the second input test in the problem. it's wrong.

i solved it this morning and i'm sure my program is correct but it doesn't get accepted.

here is the source code if you still care:

[c]#include <stdio.h>
#include <stdlib.h>

#define MAX 20

char answers[MAX], trans[MAX+1], length[MAX];
int n;

void make_trans_table()
{
int i, tmp;
for (i=0; i<n; i++)
{
scanf("%d",&tmp);
trans[tmp] = (char)i;
}
}

char solve()
{
int i, j, tmp;
char max, master_max = 1;
for (i=0; i<n; i++)
if (scanf("%d",&tmp) != 1)
return 0;
else
answers = trans[tmp];
for (i=n-1; i>=0; i--)
{
max = 0;
for (j=i; j<n; j++)
if (answers[j] > answers && length[j] > max)
max = length[j];
if ((length = max + 1) > master_max)
master_max = length;
}
printf("%d\n",(int)master_max);
}

int main()
{
scanf("%d",&n);
make_trans_table();
while(solve());
return EXIT_SUCCESS;
}
[/c]

[Ivan Golubev]

give up, the judge is wrong.

just look at the second input test in the problem. it's wrong.

Everything is OK! Just read carefully description, the information under exclamation sign and search this board before posting such things.

http://acm.uva.es/board/viewtopic.php?t=524

[epsilon0]

i don't see.

please make yourself more clear

[epsilon0]

nevermind. i got it. but it wasn't clearly explained.

the correct ordering is 2 3 1 4 doesn't mean event 2 is the first in chronological order. but first event in the list in second in chronological order.
so the student would write 2 3 1 4 on his copy but the correct order of the events is 3 1 2 4.

hopefully this enlightenment shall grant me AC after a slight change in my code

[epsilon0]

ok just got accepted, sorry for the trouble, but i keep thinking the problem statement is unclear.

[nghiank]

Hi! Epsilpon
My solution is like your solution.But I still get Wa
Can you help me?
Here is my code :
[pascal]
const
maxn=20;
var
n,result:integer;
l,c,a,b:array[0..maxn] of integer;

function max(a,b:integer):integer;
begin
if a<b then
max:=b
else max:=a;
end;

function check(c1,c2:integer):boolean;
var i:integer;
begin
for i:=1 to n do
if a=c1 then
begin
check:=true;
exit;
end
else
if a=c2 then
begin
check:=false;
exit;
end;
end;

procedure process;
var i,j,ll:integer;
begin
result:=0;
fillchar(l,sizeof(l),0);
for i:=1 to n do
begin
l:=1;
for j:=i-1 downto 1 do
if check(b[j],b) then
if l<l[j]+1 then
l:=l[j]+1;
if result<l then
result:=l;
end;
end;

procedure read_data;
var i,j:integer;
begin
read(input,n);
for i:=1 to n do read(input,b);
for i:=1 to n do a[b]:=i;
while not eof(input) do
begin
if eoln(input) then
begin
readln(input);
continue;
end;
for i:=1 to n do read(input,c[i]);
for i:=1 to n do b[c[i]]:=i;
process;
writeln(output,result);
end;
end;

BEGIN
read_data;
END.

[/pascal]

[epsilon0]

hello nghiank.

sorry, i'm too tired now to read and understand your pascal program.

here is some help:

if the input is:

5
3 1 2 4 5
2 1 4 3 5
3 1 2 4 5

you copy the first line "as is" in a table, let's call it "trans"
trans = { 3 1 2 4 5 } in the example.
then you copy each following line like this:
for i = 1 to n
answers[x] = trans;

where x is the number from input.

in the above example, we then have:
answers[2] = trans[1] = 3
answers[1] = trans[2] = 1
answers[4] = trans[3] = 2
answers[3] = trans[4] = 4
answers[5] = trans[5] = 5

so we have:

answers = { 1 3 4 2 5 }

then you solve the problem of finding the longest increasing subsequence.
here: 1 3 4 5 so the answer is 4

now notice what happes with the last line:
answers[3] = trans[1] = 3
answers[1] = trans[2] = 1
answers[2] = trans[3] = 2
answers[4] = trans[4] = 4
answers[5] = trans[5] = 5

so answers = { 1 2 3 4 5 } which is perfect (score = 5)