## 10635 - Prince and Princess

Moderator: Board moderators

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

### 10635 - Prince and Princess

Why does a simple LCS algorithm gives a TLE? I did not use the whole table for storage, only used two lines.

Is it the wrong algorithm? Is it possible to solve it with a longest ordered subsequence, since the number does not repeat and we can consider the prince path as an "ordered sequence"? giving nlogn (Cormen last exercise in the LCS)

Thanks

Guilherme Silveira

Antoine K. El Daher
New poster
Posts: 1
Joined: Sun Apr 18, 2004 10:53 am
Hi,

The maximal number of elements in each sequence is 250*250 = 62500. If you are using the simple DP version of the LCS, then you should know that it is O(nm), which in the worst case here, corresponds to 62500*62500 operations (hence the TLE).

Because every element appears only once in the sequence, O(n log n) is what you should be aiming at. Yes it can reduce to finding the longest increasing sequence like the last exercise in Cormen 15.4-6. To find the transformation, try writing the elements of the first sequence on the x-axis, and those of the second sequence on the y-axis. Indicate the match points where x = y[j], and try to find the pattern then.

Hope it helps

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

### 10635

Is it n*n always the last step of Prince and Princess? Do they always step into n*n?

Wojciech

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

### 10635

Is it n*n always the last step of Prince and Princess? Do they always step into n*n?

Wojciech

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
In problem description we can read that Prince and Princess always finally reach the square n*n. In 2 sample inputs Prince and Princess ends jumpson the square no. n. Where is the mistake? In the problem description or in the sample inputs?

Wojciech

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
In problem description we can read that Prince and Princess always finally reach the square n*n. In 2 sample inputs Prince and Princess ends jumpson the square no. n. Where is the mistake? In the problem description or in the sample inputs?

Wojciech

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
For each case, the first line contains three integers n, p, q(2 <= n <= 250, 1 <= p, q < n*n)
So lets analyze the sample input:
3 6 7
This means, n = 3.
1 7 5 4 8 3 9
1 4 3 5 6 2 8 9
The last number is 9 for the jumps of princess, and for the jumps of prince.
So what should be wrong in your view?

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Lets analyze second sample:
10 9 9
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
The last jump is 10 = n. According to the problem description it should be n*n = 100! The same in the third sample. Don't You think ? It leads to the question is it - for example - the correct input like this:

3 2 1
1 2 3
1 9
??

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Where did you take these samples from? They are not part of the problem description, or am I blind?

Sorry, now I see what you mean; there are 2 other sample inputs in the pdf file. But I think that the html file is more up to date, so just ignore these test cases of the pdf file.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
I took the second sample from pdf file! But if You look at html file - Your eyes are OK. For some reason html doesn't contains 2 samples which exists in pdf!
The last sample is invented by me because my program doesn't handle such example. I'd like to know if is it possible that something like such input can exists in the real test inputs.

Wojciech

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

### 10635 - TLE

Hello, I used LIS to find LCS of the two sequences, since the numbers can appear only once. Is there any other algorithm that I can use so I can reach the correct solution in time.

Here is my source code:

Code: Select all

``````var
k, i, j, t, n, n1, n2 : integer;
pos1, pos2, l : array[1..62500] of integer;

begin

for k := 1 to t do
begin
fillchar(pos1, sizeof(pos1), 0);

for i := 1 to n1 + 1 do
begin
pos1[j] := i;
end;

n := 0;

for i := 1 to n2 + 1 do
begin

if (pos1[j] <> 0) then
begin
inc(n);
pos2[n] := pos1[j];
end;
end;

for i := 1 to n do
l[i] := 1;

for i := 1 to n - 1 do
for j := i + 1 to n do
if pos2[j] > pos2[i] then
if l[j] < l[i] + 1 then
l[j] := l[i] + 1;

writeln('Case ', t, ': ', l[n]);
end;
end.
``````

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
There is an nlogn algorithm for LIS..

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Thankx 4 ur help Larry, I got AC

The following link was very useful 2 me:

http://www.winnetmag.com/Files/23/24814/Figure_02.gif

Thanx again...!!!

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:
Larry wrote:There is an nlogn algorithm for LIS..
hello
may be u mean b_search on a sorted array if so i know what to do
but getting WA...
to all of U please give me some I/OOO
thanks
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
I LIKE GN wrote:to all of U please give me some I/OOO
Try this:

Code: Select all

``````15
2 1 1
1 4
1 4
2 3 3
1 2 3 4
1 2 3 4
2 3 3
1 2 3 4
1 3 2 4
4 15 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
4 8 8
1 2 3 4 5 6 7 8 16
1 9 10 11 12 13 14 15 16
10 50 50
1 28 25 81 19 8 9 96 74 64 7 66 48 99 32 3 13 93 31 56 38 79 87 2 92 89 68 40 85 62 78 72 82 44 91 80 90 20 23 52 24 11 71 41 58 45 57 50 16 5 100
1 58 14 15 2 24 93 81 18 64 22 76 10 41 4 32 33 73 5 49 55 53 62 90 7 67 72 13 57 74 70 88 69 91 50 44 83 51 11 86 82 36 96 37 71 56 60 30 28 19 100
10 40 30
1 20 19 97 70 26 41 40 9 91 48 93 72 89 49 54 33 53 29 24 13 90 27 69 71 86 96 22 12 42 11 10 52 61 39 83 98 62 16 51 100
1 50 42 69 73 53 57 22 29 84 16 94 89 23 37 98 74 85 47 33 82 32 80 92 39 30 78 13 31 55 100
10 40 30
1 11 50 83 95 66 32 89 92 21 10 29 20 81 12 64 13 34 4 94 63 27 73 55 3 39 6 68 16 18 37 97 71 86 5 99 96 43 69 90 100
1 4 93 61 59 54 63 51 56 17 72 76 80 27 3 25 5 64 34 68 58 35 47 79 29 8 36 71 85 73 100
10 40 30
1 32 39 48 9 7 98 89 60 15 63 84 16 41 18 4 42 85 61 20 8 93 27 86 12 99 51 30 64 59 34 46 75 88 6 24 10 38 31 54 100
1 31 57 80 15 67 77 30 16 7 93 74 38 52 19 29 25 5 13 70 86 21 8 4 45 9 46 73 62 76 100
5 20 20
1 17 12 6 24 9 15 13 7 20 10 18 4 3 11 19 5 14 23 8 25
1 14 6 10 8 2 12 21 24 23 11 20 4 5 22 7 3 9 19 18 25
5 20 20
1 6 3 20 18 15 19 5 24 23 2 21 12 8 16 4 7 10 13 14 25
1 8 21 20 4 14 3 15 7 9 5 13 6 19 11 10 2 16 24 12 25
5 20 20
1 8 16 23 14 15 12 21 19 6 22 13 9 10 7 17 3 20 24 11 25
1 11 2 8 20 14 13 5 19 24 12 10 23 22 18 9 16 7 17 15 25
100 10 10
1 3483 1890 4675 8780 1587 9499 8207 3467 3744 10000
1 1573 2372 338 4074 4542 4457 5038 2420 4933 10000
100 10 10
1 1572 2454 3724 2073 6826 479 3514 1636 4090 10000
1 9719 4393 6392 32 9457 8282 4706 8237 1451 10000
30 15 15
1 91 95 497 177 556 828 265 543 837 62 586 888 663 815 900
1 598 508 377 889 71 158 466 609 330 47 864 223 380 635 900
``````
My AC's output:

Code: Select all

``````Case 1: 2
Case 2: 4
Case 3: 3
Case 4: 16
Case 5: 2
Case 6: 10
Case 7: 5
Case 8: 8
Case 9: 7
Case 10: 8
Case 11: 7
Case 12: 9
Case 13: 2
Case 14: 2
Case 15: 2
``````
Good luck