StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'll expand Rupert's answer with a practical example (i.e. how to compute what he calls the median row and column).</p> <p>As he said, <strong>you can find the optimal row and the optimal column for the pump separaterly</strong>. How?</p> <p>Let us consider the following instance of the problem:</p> <pre><code>3 2 7 1 8 9 7 2 2 </code></pre> <ul> <li><strong>First, we find the optimal row for the pump</strong></li> </ul> <p>We start adding all the rows of the matrix</p> <pre><code>3 2 7 -> 12 1 8 9 -> 18 7 2 2 -> 11 </code></pre> <p>now if we place the pump in the first row, the <strong>total vertical cost</strong> is</p> <pre><code>11*2 + 18*1 + 12*0 = 30 </code></pre> <p>since the 11 cars in row 3 have to travel for 2 vertical units, the 18 cars in row 2 have to travel for 1 vertical unit, and the cars in row 1 do not have to travel in vertical. We have to compute the total vertical travel cost for all the rows.</p> <pre><code>pump in 1st row -> cost 30 = 11*2 + 18*1 + 12*0 pump in 2nd row -> cost 23 = 11*1 + 18*0 + 12*1 pump in 3rd row -> cost 42 = 11*0 + 18*1 + 12*2 </code></pre> <p>so <strong>the optimal row for the pump is the 2nd</strong>.</p> <p>We computed this in O(n^2), since we did O(n^2) sums when the summed all the <em>n</em> cars in the <em>n</em> rows, and we did O(n^2) sums and multiplication when we computed the total vertical cost for each possible row for the pump.</p> <ul> <li><strong>Now we find the optimal column for the pump</strong></li> </ul> <p>We sum the cars in each column:</p> <pre><code>3 2 7 1 8 9 7 2 2 _______ 11 12 18 </code></pre> <p>now:</p> <pre><code>pump in 1st col -> cost 48 = 11*0 + 12*1 + 18*2 pump in 2nd col -> cost 29 = 11*1 + 12*0 + 18*1 pump in 3rd col -> cost 34 = 11*2 + 12*1 + 18*0 </code></pre> <p>so <strong>the optimal column for the pump is the 2nd</strong>. </p> <p><strong>In O(n^2) steps, we found that we have to place the pump in [2][2]</strong>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload