Thursday, January 15, 2009
Rapa nui and the mohais
The inhabitants of the remote Rapa Nui island want to build a pyramid of mohais. There are K mohais in the island and each of them has a weight wi and a strength si. The i-th mohai can tolerate a weight no larger than si on his shoulders. What is the maximum height of the pyramid? (PS: there are two options either you subtract the weight of the mohai from his strength, or you don't subtract it).
Subscribe to:
Post Comments (Atom)
I wud really like an answer to this question.... :)
ReplyDeleteThe tricky point is to observe that given a pyramid, if we permute the mohais by increasing value of w_i + s_i starting with the smallest one at the top, the result is still an acceptable pyramid of the same height.
ReplyDeleteIn other words, we can safely assume that the mohais that form the solution are sorted by increasing value of w_i + s_i.
So we first sort all the mohais by increasing value of w_i+s_i. Then, it is not difficult to devise a dynamic programming algorithm to find the longest pyramid in O(n^2) time.
We scan the mohais in sorted order mantaining an array A of size n such that at any time in the scan, for any k <= n, A[k] is the minimum weight of a pyramid of length k formed by k of the previous mohais in the sequence (or +infty if no such pyramid of length k exists)
Initially we set A[0] = 0, and A[k] = +infty for any n >= k >= 1. When we see the next mohais, the value of A[j] for each 1 <= j <= n may change, as now it is possible that a new pyramid of length j can be formed using the new mohais.
Let w and s be the weight and strength of the new mohais. It is easy to see that the minimum weight of a pyramid of length j containing the new mohais is A[j-1] + w, and this pyramid can be formed if and only if A[j-1] <= s. Therefore, in order to update A, we scan its elements and set A[j] = min {A[j], A[j-1] + w} for any j <= n such that A[j-1] <= s.
The total running time of the algorithm is O(n^2). At the end of the scan we return the highest value of j such that A[j] != infty.