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

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

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

click xx
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am

Post by 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
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

111: WA

Post by 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 //
Last edited by dawynn on Fri Aug 16, 2002 4:44 pm, edited 1 time in total.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

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

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by dawynn »

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

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

Please give me some test of 111

Post by nghiank »

test
Last edited by nghiank on Sun Apr 22, 2007 3:39 pm, edited 1 time in total.

User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

Post by 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. :wink:

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

Problem 111,

Post by nghiank »

test
Last edited by nghiank on Sun Apr 22, 2007 3:29 pm, edited 1 time in total.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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]
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

epsilon0 wrote: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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 »

i don't see.

please make yourself more clear
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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 :P
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 »

ok just got accepted, sorry for the trouble, but i keep thinking the problem statement is unclear.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

Post by 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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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)
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Post Reply

Return to “Volume 1 (100-199)”