CODEWITHSUNDEEP
algorithm
user1781626
user1781626

Reputation:

The number of increasing subsequences using "The longest increasing subsequence algorithm (nlgn)"

For reference: I'm solving the nested dolls problem: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2353

I have written the portion to find the longest increasing subsequence (the nlgn version). For example if the sequence is the following: 1 2 3 1 2 1

  1. I find the largest subsequence: "1 2 3" and I remove it from the original sequence. The sequence becomes 1 2 1.

  2. I find the largest subsequence: "1 2" and I remove it again. The sequence becomes 1.

  3. I find the largest subsequence: "1" and I remove it. The sequence becomes empty.

So the answer is 3, 3 total increasing subsequences

My problem is that I'm getting TLE (time limit) and I need a better way of counting the subsequences. There is a hint about using "Dilworth's theorem" but I'm not sure how to apply it.

Upvotes: 1

Views: 1098

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Algorithm

If I understand the question correctly, you are trying to find the minimum number of nested dolls that can pack every doll, and your algorithm is to greedily make the biggest doll at each stage (biggest in the sense that it contains the most pieces) and repeat until all dolls are packed.

In other words, you are constructing chains from your partially ordered set.

Dilworth's theorem says:

the maximum number of elements in any antichain equals the minimum number of chains in any partition of the set into chains

and so you can compute the number of chains by counting the elements inside a single antichain.

You can construct the antichain in a very similar way to you are doing at the moment, by ordering the dolls by width in decreasing order and then finding the longest increasing subsequence within the heights.

Note, that with this method you get the answer by measuring the length of the anti-chain and you only need to run the longest increasing subsequence algorithm once so it should be a lot faster.

Example

In your example of (1, 1), (1, 1), (2, 2), (3, 3), (1, 1), (2, 2), (1, 1) we first sort by width in decreasing order:

(3, 3), 
(2, 2), 
(2, 2), 
(1, 1), 
(1, 1), 
(1, 1), 
(1, 1)

and then extract the heights:

3,2,2,1,1,1,1

then find the longest increasing subsequence (note that each element must be the same or higher than the previous so strictly speaking you find the longest non-decreasing subsequence):

1,1,1,1

this is of length 4, so the answer is 4.

Upvotes: 2

Related Questions