CODEWITHSUNDEEP
algorithm
Programmer
Programmer

Reputation: 6753

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

Upvotes: 9

Views: 3524

Answers (5)

delmet
delmet

Reputation: 1013

As far as I can see, this is the same question as Box stacking problem:

Also: http://people.csail.mit.edu/bdean/6.046/dp/

Upvotes: 0

Stomp
Stomp

Reputation: 920

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.

Upvotes: 2

QuentinUK
QuentinUK

Reputation: 3077

It doesn't make any difference. And it is unnecessary to pre-sort as you end up with the same graph to search.

Upvotes: 0

davin
davin

Reputation: 45565

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.

Upvotes: 1

Karoly Horvath
Karoly Horvath

Reputation: 96326

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.

Upvotes: 4

Related Questions