Number of incremental subsequences using "Largest incremental subsequence algorithm (nlgn)"

Question

For reference: I solve the problem with folded dolls: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2353

I wrote a piece to find the longest ascending subsequence (nlgn version). For example, if the sequence is as follows: 1 2 3 1 2 1

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

• I find the biggest subsequence: "1 2", and I delete it again. The sequence becomes 1.

• I find the biggest subsequence: "1", and I delete it. The sequence becomes empty.

So the answer is 3, 3 complete incremental subsequences

My problem is that I get TLE (time limit), and I need a better way to count subsequences. There is a clue about using the “Dilworth theorem”, but I'm not sure how to apply it.

Answer 1

Algorithm

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

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

Dilworth's theorem states:

the maximum number of elements in any anti-chain is equal to the minimum number of chains in any partition of the set into chains

and therefore, you can calculate the number of chains by counting the elements inside one antitsein.

You can build anticein very similar to what you are doing at the moment, sorting the dolls by width in descending order, and then finding the longest increasing subsequence within the heights.

Please note that with this method you get the answer by measuring the length of the antichain, and you just need to run the algorithm with the largest increase in the subsequence, so that it is much faster.

Example

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

(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 ascending subsequence (note that each element must be the same or higher than the previous one, so strictly speaking, you will find the longest non-decreasing subsequence):

 1,1,1,1 

it is length 4, so the answer is 4.