Out of Pod Experience

Correct.

Strangely enough, EVERYONE I know who did this problem did it the way you did. They start by picking a bunch of high numbers until they stumble upon an answer which looks right - so they take a guess (my friend calls it "chasing your dreams") and prove that it is the correct answer.

I don't like doing it this way because:
1) It only finds the answer for THIS matrix. if you have a different matrix, you might never find an answer which "looks" correct.
2) If you don't find the correct answer by chance, it will have the same time complexity as a brute force algorithm.

I solved the problem by applying a decrease-and-conquer algorithm.

First of all, the number 1 is the worst possible choice, so you can safely eliminate that as a choice. We denote this by removing it from the matrix.

Next, now that the number 1 has been eliminated, we can safely eliminate the number 2, so we remove that from the matrix also.

We repeat the process, removing the number 3 through 14. After removing 14 from the matrix, column #3 only has one element left in it: 25. Also, row #3 only has one element left in it: 18

We therefore can conclude that we MUST choose 25 and 18. If we don't choose these numbers, then we must choose a number which we have already eliminated as being a "worst case". After choosing 25 and 18, we remove both the columns and the rows which containing 25 and 18.


After removing these columns/rows we are left with a 3x3 matrix In this 3x3 matrix, we notice that the 2nd row only has a single element in it: 23. By the same reasoning above, we know that we must also choose 23. We repeat the process of removing the column/row containing the number 23, giving us a 2x2 matrix.

The problem now becomes trivial to solve, but just for the sake of completeness we go back to removing "smallest numbers" from the 2x2 matrix. In a 2x2 matrix, we can only remove one element before we are forced to make our final two choices. We remove 15, which leaves only 1 element left in row #1 and column #2 - forcing us to choose 17 and 21 respectively.

Therefore our solution is:

25, 18, 23, 17, 21.


The run-time of this decrease-and-conquer algorithm is O(n^2). We can improve this to O(n*log n) if we presort the matrix in such a way that we can find the smallest number in the matrix in O(1) time. It would require some extra work to keep track of the original positions of each matrix element after you 'sort' them, though.

I take issue with your statement that the units are irrelevant to the answer for the first problem for two reasons.

First, if you use a logarithmic unit of speed measurement, that would change things entirely. Let's say those numbers are stated in units of dB(m/s).

30dB(m/s) = 10^3 m/s
60dB(m/s) = 10^6 m/s

If you travel 10^3 m/s one direction and 10^6 m/s the other direction, the average speed is clearly not 40dB(m/s), which would be 10^4 m/s.


Second, if your speeds were relativistic, that would change the answer as well. Let's say your speeds were 30% of c and 60% of c. In the frame of reference of an outside observer, your average speed would be 0.4*c. However for Bob, the distance traveled during the 0.6*c portion would appear to be shorter, due to length contraction. This would decrease his observed average speed, making it less than 0.4*c.

My overall point was that you can't say units are meaningless, at least not in this context. If you allow me to pick the units, I can pick units that change the nature of the problem.