If You Are Homeless... Just Build a House#12866

If You Are Homeless... Just Build a House (Editorial)

For a given region with values b_1\le b_2\le \ldots \le b_{hw}, the answer is the sum of |b_i - b_{med}|, where med = \lfloor \frac{hw}{2} \rfloor. It can also be stated as the following: let's keep the set of smallest numbers S_1, and the set of largest numbers S_2, then the answer is just the sum of numbers from S_2 minus the sum of numbers from S_1.

Now, let's make some kind of sliding window and support these sets S_1, S_2 together with the sums in them in the process. Let's start from the area h\times w in the left upper corner, and move it to the right by every time. We would need to do insertions/deletions per moving it by to the right.

Next, let's move it down by , which takes insertions/deletions, and start moving it to the left, then again down and to the right, and so on.

Overall we will make O(mnh + nw) insertions/deletions while moving this sliding area, which gives runtime O((mnh + nw)\log{hw}). The answer is just the smallest value sum(S_2)-sum(S_1) over all possible positions of the area.