10635 - Prince and Princess

[technobug]

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]

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]

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

Wojciech

[w k]

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

Wojciech

[w k]

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]

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

[Adrian Kuegel]

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]

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

[Adrian Kuegel]

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]

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]

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
   readln(t);

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

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

         readln;
         n := 0;

         for i := 1 to n2 + 1 do
            begin
               read(j);

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

         readln;

         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.

Help please...!!!

[Larry]

There is an nlogn algorithm for LIS..

[neno_uci]

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]

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

[Martin Macko]

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