Ok,

So I was recently presented with an example coding exercise as stated below:

Every athlete is characterized by his mass ‘m’ (in kg) and strength ‘s’ (in kg).

You are to find the maximum number of athletes that can form a tower standing one upon another.

An athlete can hold a tower of athletes with total mass equal to his strength or less than his strength.

Input contains the number of athletes n and their parameters.

For example:

n

m1 s1

m2 s2

…

mn sn

If mi > mj then si > sj, but athletes with equal masses can be of different strength.

Number of athletes n < 100000. Masses and strengths are positive integers less than 2000000.

For example:

Input #1

4

3 4

2 2

7 6

4 5

Would yield

Output #1

3

## Working through the Solution

Phase one, figure out how to store the data. Easy, store it in a linked list, could be a list of tuples/pairs, but I actually created a class to store the weight/strength, because I want to be able to do a complex sort on the data (see below).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
class Athlete { public: int weight; int strength; Athlete(int w, int s) : weight(w), strength(s) { } // Define comparisons that can be used // for a Athlete. If the weight is greater, // the Athlete is greater (defined by contraints of problem). // If weight is equal, go by strength. bool operator > (Athlete &r) { if (weight > r.weight) return true; if (weight < r.weight) return false; if (strength > r.strength) return true; return false; } bool operator < (Athlete &r) { if (weight < r.weight) return true; else if (weight > r.weight) return false; else if (strength < r.strength) return true; return false; } // We want to sort strongest to weakest, so // create a function to use here. static bool compareGreater( Athlete &l, Athlete &r) { return l > r; } }; typedef std::list<Athlete> People; |

Now, the problem description states that if one athlete weights more than another, it will have greater strength as well. This provides us with one crucial optimization, we know that the strongest athlete will also be the heaviest. This athlete, therefore, should go on the bottom of the tower. We could do a linear search for the strongest, but we can also find the strongest after sorting the list, and we’ll want a sorted list for later. Therefore, using the comparison operators we described above, we can sort the list of athletes, and begin processing as so:

1 2 3 4 5 6 7 8 9 10 11 |
// Sorting should be done with nlog(n) complexity on average, allPeople.sort(Athlete::compareGreater); // At this point, strongest Athlete is at beginning. int count = 1; Athlete &p = allPeople.front(); int weightLeft = p.strength; int tot = 0; count += countTower(allPeople,++allPeople.begin(),weightLeft,1, tot); |

In the above code, we grab the first entry after sorting, which is (by definition) the strongest. Starting with that athlete’s strength as the maximum weight for any tower to be formed. We then pass the array of athletes, the starting point and weight left to our recursive function. The “tot” variable is there for analysis purposes. The function is defined as below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
// Do the magic here. // Best case is O(n) // Average case is O(n)?? // Worst case is O(2^(n-1)). // Which, within the constraints of the number of // athletes, means 2^99999, which would be impossible // to compute (would need a 100,000-bit machine, and // we're currently stuck with 64-bit). // Practical limits with worst-case performance would need // to be under 64 entries, and even then, the amount of // time and memory would probably be beyond most PCs. int countTower(People &peeps, People::iterator first, int weight, int at, int &total) { // Maintain the maximum tower height found from recursive calls. int max = 0; // Maintain an offset from the starting "at" position. int i = 0; // For debug information, increment the // number of times this function has been called. total++; // Keep track of the last athlete we processed. // We do no need to process additional athletes of // the same weight. int lastWeight = -1; // Make sure we can keep moving. if (weight > 0 && (unsigned)at < peeps.size()) { // List members cannot be directly accessed, we must loop through // to skip past entries we do not want. // Keep looping until the end of the list OR // until the max tower size equals the number of athletes // left in the list (thus a complete tower). for (auto x = first ; x != peeps.end() && max < peeps.size()-at; x++, i++) { // NOTE: Because we have sorted this list, we can assume that anyone who // preceeded the current Athlete with the same weight had a greater than or // equal to strength. As such, that Athlete's max would be greater than or // equal to this Athlete's max, so we don't need to search this Athlete. Athlete &p = *x; if (p.weight <= weight && p.weight != lastWeight) { People::iterator next = x; next++; // Grab the max height from either the previous max or the new calculation. // Note, use the minimum supportable weight (which is the current total weight // minus the current Athlete's weight, or the current Athlete's strength). // Add 1 to i or we'll count this Athlete twice. Add one to the return from countTower // to count for this Athlete. max = std::max<int>(max,countTower(peeps,next,std::min<int>(p.strength,weight-p.weight),at+i+1,total)+1); lastWeight = p.weight; } } } return max; } |

The analysis of the algorithm is actually contained in the comments above, but I’ll point out some key points here:

- The maximum size of the tower (within the current iteration) is limited to the number of athletes left in the list. If we find a tower equal to the size of the list, we are done.
- If the current athlete weighs more than the remaining weight limit, they (and any other athletes of the same mass) cannot fit on the tower.
- The first athlete of any weight is also the strongest (thanks to the sorted list). Therefore, we only need to consider ONE of any athlete with a given weight (e.g. ALL athletes of weight 4 will be able to support a tower of a most the size of the strength of the strongest athlete).

The loop in the above function scans the lists of athletes, to determine the maximum size of a tower each athlete could support, standing on top of the tower as it stands before the function is called. Therefore, the first time the function is called, it stands each athlete, in sequence, on top of the shoulders of the strongest athlete, and sees how tall the tower can be built.

If the current athlete can fit on the tower at all (based on remaining weight limit), the recursive call then determines the size of the tower that could then stand on the shoulders of the current athlete. Thanks to item 3 above, we must only perform the recursive call once per athlete weight. This greatly reduces the number of recursive calls. The return value of the recursive call is compared to the current maximum tower height found previously (and stored if greater than). The loops then checks that the maximum tower height does not equal the remaining number of athletes. If it does, we have found the greatest tower height and can return.

The function returns the tallest tower it found that could stand on the shoulders of the previous athlete. When the recursion returns completely, we have solved the problem. Worse case scenario of this algorithm is actual 2^n, which is terrible. But this is because every possible combination of towers must be considered. However, thanks to our end-conditions (the 3 steps above), we can actually reduce actual complexity to a linear (O(n)) complexity. This is because we really only have to search the list once, excluding “duplicate” athletes (athletes that could not have supported a stronger tower are discounted thanks to step 3). With step 1 above, we do not need to continue looping once we have found a maximum tower, and can exit.

Anyway, the full source is in my (poorly misspelled) repository here: http://svn.hellwig.us/repo/VC11/ExcersizeTest.