A DP one.
Q. Consider that you have n 2D pts. Find the largest set of pts such that when sorted (by either axis) produce the same sequence.
Okay, the exact wordings of the original problem -
A circus is designing an act consisting of a tower 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 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?
My thoughts -
Sort the pts by say x axis co-ordinates. Then the problem reduces to finding the longest increasing subsequence ( or longest decreasing subsequence Note: we hae to consider both ) in y axis co-ordinates. this is a std DP problem.
More questions :
1. Will it produce the same answer when first sorted in y axis co-ordinates. Or we have to do the both and then take the one of max-length ?
2. How would you generalize the problem to pts coming from dimension d > 2. Need to think over that.
An aside :
See if you could relate some parts of the above problem to the following problem.
Given any sequence of mn+1 real numbers, some subsequence of (m + 1) numbers is increasing or some subsequence of (n+1) numbers is decreasing.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment