Dynamic programming question

Question

A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.

EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

Someone suggested me the following: It can be done as follows:

1. Sort the input in decreasing order of weight and find the longest decreasing sequence of hight.
2. Sort the input in decreasing order of hight and find the longest decreasing sequence of weight.

Take max of 1 and 2.

I dont understand why we need to do both steps 1 and 2. Cant we just do 1 and find the answer. IF not , please give example in which doing only step 1 does not give answer?

Answer 1

Result of 1 and 2 has to be same. It's not possible that one of them is shorter, because in a solution elements are descending both in height and weight so if it satisfies 1 or 2 it will satisfy the other as well, If it would be shorter it wouldn't be the longest.

Answer 2

You might need to say something about the weights & heights all being unique. Otherwise, if

A is (10, 10) // (w, h)
B is ( 9, 10)
C is ( 9,  8)

Then neither method gets the correct answer! C obviously can stand on A's shoulders.

---

Edit:

Neither method is good enough!

Example with all weights & heights unique:

A : (12, 12)
B : (11,  8)
C : (10,  9)
D : ( 9, 10)
E : ( 8, 11)
F : ( 7,  7)

Both methods give an answer of 2, however the tower can be at least of height 3 with several combinations:

• A on the bottom,
• then any of B, C, D, or E,
• then F on top.

I think stricter rules on the input data are needed to make this problem solvable by the given methods.

Answer 3

You're absolutely correct. Doing just one direction is enough.

A proof is easy by using the maximum property of the subsequence. We assume one side (say the left) of values is ordered, and take the longest descending subsequence of the right. We now perform the other operation, order the right and take the subsequence from the left.

If we arrive at a list that is either shorter or longer than the first one we found we have reached a contradiction, since that subsequence was ordered in the very same relative order in the first operation, and thus we could have found a longer descending subsequence, in contradiction to the assumption that the one we took was maximal. Similarly if it's shorter then the argument is symmetrical.

We conclude that finding the maximum on just one side will be the same as the maximum of the reverse ordered operation.

Worth noting that I haven't proven that this is a solution to the problem, just that the one-sided algorithm is equivalent to the two-sided version. Although the proof that this is correct is almost identical, assume that there exists a longer solution and it contradicts the maximalness of the subsequence. That proves that there is nothing longer, and it's trivial to see that every solution the algorithm produces is a valid solution. Which means the algorithm's result is both >= the solution and <= the solution, therefore it is the solution.