Moderator: Board moderators

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
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
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

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
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
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

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

ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm
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
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

### Problem 111,

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.
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

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
for (i=n-1; i>=0; i--)
{
max = 0;
for (j=i; j<n; j++)
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
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.
i don't see.

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.
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
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.
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:
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;

var i,j:integer;
begin
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
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
END.

[/pascal]

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

where x is the number from input.

in the above example, we then have:

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: