CareerCup

step 1: sort the people by their weights (in ascending order) --- O(nlogn)
step 2: compute the longest increasing subsequence in height --- O(nlogn)

Looks like an LCS to me:
1. assign an identifier (say a letter, A, B, C, D) to each person
2. create two lists: one sort weight in ascending order, the other sort height in ascending order; in both lists, each person is represented by the letter assigned in step 1
3. find the LCS of the two lists

I think this is solvable by using greedy strategy.

Keep two sorted lists according to height and weight, respectively. Then, for each element, el, in the sorted list, say height, check its weight in the other sorted list. If el weights more than one persons who are supposed to stand below of him, then remove el. If there is just one person, pl, below el weights less than el, then check how many persons pl overweights below him.

This algorithm is supposed to be nlogn.

sort the ht and wt such that
ht[i]/wt[i] > ht[i+1]/wt[i+1]
i think this will give the ans..

SN, your algo doesn't work. You can't sort based on Height/Weight proprtion/ratio. For e.g. the ratio of 65/100 is > than 68/110 but 65/100 person will be above 68/110 Person.

this problem can be solved using graphs...

let say the people be (h1, w1), (h2,w2), (h3,w3), (h4,w4),.......
When (h1, w1) comes becomes node for the graph then (h2,w2) comes and satisfies to be on the top or bottom of former then added to the same node of the graph else it will start the new graph... so on the (hN,wN) comes will be added between the links according to there hieght and wieght, else they will start the new graph, or may be added to the same graph. Then the longest tower will be decided by finding the two farthest points in the graph and then comparing among various graph which line is longest

1) get the ratio of weight and height
2) order the ratio
3) order all the pairs by weight
4) check if all the height become ordered by doing 3)
5) if 4) is true return
6) if 4) is false discard the pair whose ratio is furthest from a median ratio value of 2) <no matter the biggest or the mallest>
7) start from the 3) again

I don't think greedy algorithm would work. Here's my solution:
sort the people by their weight, then we can get a list of height with their correspoding weight increasing. Assume the list of height is h1,h2,h3...,hn. for i from 1 to n-1, compare h_i with h_(i+1), if h_i > h_(i+1), remove h_i from the list. The final size of list is the largest possible number.

This is a classic Knapsack problem. Can be solved using dynamic programming with branch and bound. I believe the algorithm is given in Cormen-Rivest Algorithm book.

can we use radix sort here ? sorting first by weight and then by height ?

create a DAG from this, for each indegree equal to 0, start the BFS. Compare the result and get the deepth path.

Assuming that we have enough personal for the tower (make some checks count > 1).
We have this structure:
struct Aero
{
int height;
int weight;
};
Aero personal[N];

Sort by height.
(The following pic represent the sorting regardless the weights. The wide of the rectangles represents the weight of the player:

|.|
|.|

|..|
|..|
|..|

|...| <- Current
|...|
|...|
|...|

|..| <- Taller but with less weight
|..| <- Is should be not here
|..| <- (*)
|..|
|..|

|....|
|....|
|....|
|....|
|....|
|....|

We can use linked list to represent all the player. Using merge sort we going to sort the list according to their heights. (Merge sort gives O(nlogn) in the worst case). After the sorting we run again thru the list and if the element->next has less weight then current delete next element. In our case delete (*). The complexity is something like O(n + n.log(n)).

the tricky inputs may be like this:
70 100
60 110
50 120
in this case only one person can stand ;o)

//algorithm
(1) sort by weight and find longest increasing subseuence in height data O(n^2, n^2)..i mean O(time, space)
(2) sort by height and find longest increasing subseuence in weight data O(n^2, n^2)
(3) take that longest amongst the above 2

@Anon

pls let me know how longest increasing subsequence can be done in O(n log n)

It is a problem to find the longest path of a DAG.
For any two person A(H1, W1) and B(H2, W2), if (H1<H2 && W1<W2), we have A->B, if (H1>H2 && W1>W2), we have B->A.
If we add (min height, min weight), and (max height, max weight), we will have a start point and end point. After we create this DAG, we find the longest path from start point to end point.

Why not to use BST
Add 1st node as root node...
Compare next node with root-node value..
if(its ht < htroot && wt < wtroot)
insert as left-child
else if (its ht > htroot && wt > wtroot)
insert as right-child

Print tree inorder traversal for answer

Kindly Review :)

First sort according to weights. Then find the noncontinuous longest increasing sequence for heights.

How about this: build a min heap using a less operator defined like this:

//sort by weight first, then by height
bool Person::less_1(const Person& other) const
{
    if (weight < other.weight) return true;
    if (weight > other.weight) return false;
    return height < other.height;
}

max_1 is where the shape of the heap is a perfect triangle.

Then we build another min heap, this time with the operator less_2 sorting by height first, then by weight, and again max_2 is the max number of people for which the heap has a perfect triangle shape (i.e. we discard the last level if it does not have precisely N * 2 leaves).

The final solution is max(max_1, max_2).

I assume that each level of the human tower (going from base to top) has N / 2 people than the previous one, but a circus tower could also be formed with N, N - 1, N - 2... not clear from the problem spec.

Thoughts?

How about this: build a min heap using a less operator defined like this:

//sort by weight first, then by height
bool Person::less_1(const Person& other) const
{
    if (weight < other.weight) return true;
    if (weight > other.weight) return false;
    return height < other.height;
}

max_1 is where the shape of the heap is a perfect triangle.

Then we build another min heap, this time with the operator less_2 sorting by height first, then by weight, and again max_2 is the max number of people for which the heap has a perfect triangle shape (i.e. we discard the last level if it does not have precisely N * 2 leaves).

The final solution is max(max_1, max_2).

I assume that each level of the human tower (going from base to top) has N / 2 people than the previous one, but a circus tower could also be formed with N, N - 1, N - 2... not clear from the problem spec.

Thoughts?

How about this: build a min heap using a less operator defined like this:

//sort by weight first, then by height
bool Person::less_1(const Person& other) const
{
    if (weight < other.weight) return true;
    if (weight > other.weight) return false;
    return height < other.height;
}

max_1 is where the shape of the heap is a perfect triangle.

Then we build another min heap, this time with the operator less_2 sorting by height first, then by weight, and again max_2 is the max number of people for which the heap has a perfect triangle shape (i.e. we discard the last level if it does not have precisely N * 2 leaves).

The final solution is max(max_1, max_2).

I assume that each level of the human tower (going from base to top) has N / 2 people than the previous one, but a circus tower could also be formed with N, N - 1, N - 2... not clear from the problem spec.

The challenge for this problem is the longest sequence might NOT start from min(heigth) or min(weight) elements.

DP solution. O(n^2).

public class LP : List<Person>;

	List<LP> DP(PA, N)
	{
		List<LP> llp = null;
		if(1 == N) 
		{
			llp = new List<LP>(new LP(PA[0]));
		}
		else 
		{
			llp = DP(PA, N-1);
			foreach(LP lp in llp)
			{
				if(lp.End.height < PA[N].height)
					lp.Append(PA[N]);
			}
		}
		
		return llp;
	}

	void Main()
	{
		//....
		
		// Sort person by weight into array PA[N]
		
		// search all possible sequence
		List<LP> llp = DP(PA, N);
		
		// go through the llp and find the max length of list. Might multiple.
		
		//....
	}

1. sort by wt
2. sort by ht
3. find the common longest sub sequence

According to me, create a graph by analyzing each vertex. There will be an edge if two vertex can satisfy given condition (in case of A(56,90) B(60,95), edge from A->B)
Once formed the graph, get the longest path in the graph (by inverse Dijkstra's algorithm, by having each node as a source at a time)
complexity: forming a graph = O(n^2)
Dijkstra's algorithm = O(n * log n)

I've tried applying the tallest tower finding algorithm (9.10), but it doesn't work. Any ideas?

public static ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> people) {
		if (people == null) {
			return null;
		} else if (people.size() == 0) {
			return people;
		} else {
			return getIncreasingSequence(people, null);
		}
	}

	public static ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> people,
			HtWt bottom) {
		ArrayList<HtWt> max_list = new ArrayList<HtWt>();
		for (int i = 0; i < people.size(); i++) {
			if (canBeAbove(people.get(i), bottom)) {
				ArrayList<HtWt> new_list = getIncreasingSequence(people,
						people.get(i));
				if (max_list == null || new_list.size() > max_list.size()) {
					max_list = new_list;
				}
				if (bottom  != null)
					max_list.add(people.get(i));
			}			
		}
		return max_list;
	}

	public static boolean canBeAbove(HtWt compare, HtWt bottom) {
		if (bottom == null) {
			return true;
		}
		return compare.Ht < bottom.Ht && compare.Wt < bottom.Wt;
	}

Why not to use BST
Add 1st node as root node...
Compare next node with root-node value..
if(its ht < htroot && wt < wtroot)
insert as left-child
else if (its ht > htroot && wt > wtroot)

Kindly review :)
insert as right-child

Print tree inorder traversal for answer