4
$\begingroup$

I have a question about my solution to a problem from Hackerrank. The problem is, given $R,C,H,W$ with

  • $1\le R,C\le 100$,
  • $1\le H\le R$,
  • $1\le W\le C$,

an $R\times C$-matrix $L$ and an $H\times W$-matrix $S$, to find $i,j$ with $0\le i\le R-H$ and $0\le j\le C-W$ which minimize the sum $$\sum_{0\le k< H,0\le l< W}(L_{i+k,j+l}-S_{k,l})^2$$ (where I use 0-based indexing).

My first attempt, which performed best, was to try out all $i,j$, store the best result so far in a variable, and stop calculating each sum as soon as it exceeds the best result from the previous runs.

Then I thought of something else (which unfortunately didn't perform that well): I want to run all the sums in parallel and advance those first which look most promising for returning a small result. So I make a list containing $[i,j,c,m,p]$ for all $i,j$, where $c$ stores how many indices I already calculated of the sum, $m$ stores the intermediate value of the sum and $p$ stores the interpolated value of the finished sum (scaled by $HW$), which I set as $m/c$ for $c>0$ and some arbitrary $x$ else. So in the beginning all elements will look like $[i,j,0,0,x]$. I will then advance the first element of the list, which means I increment $c$ by one, $m$ by a new square and then recalculate $p$. Afterwards I move the first element upwards so that the list is always sorted by $p$. I also keep track of the best finished sum so far together with its $i,j$-indices. If the new first element is a finished sum ($c=HW$) then I throw it away (and possibly update the best result). After the list is empty, the indices of the best result get returned.

I guess the resorting process takes too much time for this to perform well. I also tried using for $p$ a different function $f(m,c)$ which puts more emphasis on $c$ so that less resorting takes place. If $f(m,c)=1/c$ and $x>1$, this gives roughly the first algorithm I described, with the good performance.

My question: Is this idea any reasonable? If yes, what values for $f(m,c)$ (and possibly $x$) could yield better performance than $1/c$?

$\endgroup$
  • 4
    $\begingroup$ Using a heap would be faster than maintaining a sorted list, but this approach in general won't improve performance in the worst case: It's always possible that the last few terms spoil an otherwise promising-looking position. I would instead pad the smaller rectangle with $C-W$ columns of zeros on the right-hand side, treat both rectangles (which now both have width $W$) as vectors consisting of all elements of the top row, then all elements of row 2, etc., take FFTs, and multiply these to efficiently compute the convolution. (I'm not sure why this problem is in the DP category.) $\endgroup$ – j_random_hacker Mar 21 at 13:32
  • $\begingroup$ May I ask why you raised this question? Does your first attempt, which performed best, passes all 9 test cases? $\endgroup$ – Apass.Jack Mar 21 at 22:38
  • $\begingroup$ @Apass.Jack no, it doesn't. But on the other hand, there is only one user who achieved a better score in Python3. Still, it catched my interest and I put some thought into it and it surprised me that my second solution didn't perform well. Basically I'm just curious whether my idea is completely off track or not. $\endgroup$ – fweth Mar 22 at 3:12
  • 1
    $\begingroup$ You may note that $(x-y)^2 = x^2 + y^2 - 2xy$. $\sum{S_{k, l}^2}$ is constant, $\sum{L_{i+k, j+l}^2}$ can be computed for every position simply using DP. The most complicated is the product that is basically a convolution and, as j_random_hacker said, may be computed with a FFT. $\endgroup$ – Vince Mar 22 at 10:42
  • $\begingroup$ @Vince I also thought about that after reading j_random_hacker's comment and thinking about how to use convolution for sum of squared differences. Unfortunately, the Hackerscore environment for Python doesn't offer numpy, scipy or any other library I know with FFT implementation. I redesigned my solution with heaps and it seems to perform slightly better than my first solution on random input (but not on Hackerscore), which I consider as a win! $\endgroup$ – fweth Mar 22 at 13:24
0
$\begingroup$

I try to summarize the results of the discussion in the comments:

  • Using a heap instead of a list would be better suited for the proposed idea since all operations to be performed on the list are sorting, returning the smallest element and changing an element followed by resorting the list. These are almost exactly the operations supported by heaps, which will deliver better performance.
  • The sums $\sum_{k,l} (L_{i+k,j+l}-S_{k,l})^2$ can be expressed as $A_{i,j}+B_{i,j}-2C_{i,j}$ where $A_{i,j}:=\sum_{k,l} L^2_{i+k,j+l}$, $B_{i,j}:=\sum_{k,l} S^2_{k,l}$ and $C_{i,j}:=\sum_{k,l}L_{i+k,j+l}S_{k,l}$. Here $B_{i,j}$ does not depend on $i,j$ and $A_{i,j}$ can obtained from its predecessor $A_{i',j'}$ by only updating two rows or columns, if the order in which the $i,j$ are perused is chosen wisely. Most importantly, $C_{i,j}$ describes a convolution, which can be calculated very fast by FFTs, convolution in the frequency domain corresponds to (pointwise) multiplication in the time domain! But even without implementation of FFT, this algorithm scores better than the naive approach, as it only performs one operation (multiplication) instead of two (subtraction and squaring) in the large (size $HW$) sums.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.