111  History Grading
Moderator: Board moderators
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 !
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 !
111: WA
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 //
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 //
Last edited by dawynn on Fri Aug 16, 2002 4:44 pm, edited 1 time in total.

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
Why not to read this http://acm.uva.es/board/viewtopic.php?t=524 before posting?
Please give me some test of 111
test
Last edited by nghiank on Sun Apr 22, 2007 3:39 pm, edited 1 time in total.
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=n1; 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]
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=n1; 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]
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. Tomasso Toffoli

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
Everything is OK! Just read carefully description, the information under exclamation sign and search this board before posting such things.epsilon0 wrote:give up, the judge is wrong.
just look at the second input test in the problem. it's wrong.
http://acm.uva.es/board/viewtopic.php?t=524
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
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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. Tomasso Toffoli
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:=i1 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]
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:=i1 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]
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)
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)
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. Tomasso Toffoli