In this post, we will solve HackerRank Best spot Problem Solution.
In Chile, land are partitioned into a one large grid, where each element represents a land of size 1×1.
Shaka is a newcomer in Chile and is trying to start his own business. He is planning to build a store. He has his own ideas for the “perfect store” which can be represented by a HxW grid. Element at position (i, j) represents height of land at index (i, j) in the grid.
Shaka has purchased a land area which can be represented RxC grid (H <= R, W <= C). Shaka is interested in finding best HxW sub-grid in the acquired land. In order to compare the possible sub-grids, Shaka will be using the sum of squared difference between each cell of his “perfect store” and it’s corresponding cell in the subgrid. Amongst all possible sub-grids, he will choose the one with smallest such sum.
Note
- The grids are 1-indexed and rows increase from top to bottom and columns increase from left to right.
- If x is the height of a cell in the “perfect store” and y is the height of the corresponding cell in a sub-grid of the acquired land, then the squared difference is defined as (x-y)2
Input Format
The first line of the input consists of two integers, R C, separated by single space.
Then R lines follow, each one containing C space separated integers, which describe the height of each land spot of the purchased land.
The next line contains two integers, H W, separated by a single space, followed by H lines with W space separated integers, which describes the “perfect store”.
Constraints
1 <= R, C <= 500
1 <= H <= R
1 <= W <= C
No height will have an absolute value greater than 20.
Output Format
In the first line, output the smallest possible sum (as defined above) Shaka can find on exploring all the sub-grids (of size HxW) in the purchased land.
In second line, output two space separated integers, i j, which represents the index of top left corner of sub-grid (on the acquired land) with the minimal such sum. If there are multiple sub-grids with minimal sum, output the one with the smaller row index. If there are still multiple sub-grids with minimal sum, output the one with smaller column index.
Sample Input
3 3
19 19 -12
5 8 -14
-12 -11 9
2 2
-18 -12
-10 -7
Sample Output
937
2 2
Explanation
The result is computed as follows: (8 – (-18)) 2 + (-14 – (-12)) 2 + (-11 – (-10)) 2 + (9 – (-7)) 2 = 937
Best spot C Solution
#include <stdio.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
typedef long long LL;
inline int pow(long long n,int k,int m){
unsigned i;
int a;
for(a=i=1;i<=k;i*=2,n=(n*n)%m)
if(k&i)a=(a*n)%m;
return a;
}
int rr[512];
inline int rev(int n,int k){
int i=0;
while(k--)i=(i<<1)|(n&1),n/=2;
return i;
}
const long long p=1107296257,r=10;
LL ww[513][2];
void ntt(int f,int n,int s[]){
int i,j,k=10;
long long x,w;
for(i=0;i<n;i++)
if(i<rr[i]){
int tmp=s[i];
s[i]=s[rr[i]];
s[rr[i]]=tmp;
}
for(i=2;i<=n;i<<=1){
w=ww[i][f];
for(j=0;j<n;j+=i)
for(k=0,x=1;k<i/2;k++){
int a=s[j+k],b=s[j+k+i/2];
LL tmp=b*x;
b=(a-tmp)%p;
if(b<0)b+=p;
a=(a+tmp)%p;
s[j+k]=a;
s[j+k+i/2]=b;
x=x*w%p;
}
}
x=pow(n,p-2,p);
if(f)for(j=0;j<n;j++)
s[j]=(s[j]*x)%p;
}
void mul(int n,int cc[],int a[],int b[]){
for(int i=0;i<n;i++)
cc[i]=(1ll*a[i]*b[i])%p;
}
int A[501][512],B[501][512],an[501][501],tmp[512];
int main(){
REP(i,512)rr[i]=rev(i,9);
for(int i=2;i<=512;i<<=1)
for(int f=0;f<2;f++)ww[i][f]=pow(pow(r,(p-1)/512,p),f?p-1-512/i:512/i,p);
DRII(R,C);
REP(i,R)REP(j,C){
RI(A[i][j]);
A[i][j]+=20;
}
DRII(H,W);
int base=0;
REP(i,H)REP(j,W){
RI(B[i][j]);
B[i][j]+=20;
base+=B[i][j]*B[i][j];
}
for(int i=0;i+H<=R;i++)
for(int j=0;j+W<=C;j++)an[i][j]+=base;
REP(i,R){
base=0;
for(int j=0;j<C;j++){
base+=A[i][j]*A[i][j];
if(j>=W-1){
for(int k=0;k<H&&k<=i;k++)an[i-k][j-W+1]+=base;
base-=A[i][j-W+1]*A[i][j-W+1];
}
}
}
REP(i,R){
for(int j=0;j<C-1-j;j++){
int tmp=A[i][j];
A[i][j]=A[i][C-1-j];
A[i][C-1-j]=tmp;
}
ntt(0,512,A[i]);
}
REP(i,W)ntt(0,512,B[i]);
REP(i,H){
for(int j=0;j+H<=R;j++){
mul(512,tmp,A[i+j],B[i]);
ntt(1,512,tmp);
//mul(500,B[i],A[j+i],tmp);
for(int k=0;k+W<=C;k++){
an[j][k]-=2*tmp[W-1+(C-W-k)];
}
}
}
int mi=2e9,xx,yy;
for(int i=0;i+H<=R;i++)
for(int j=0;j+W<=C;j++){
if(an[i][j]<mi){
mi=an[i][j];
xx=i+1;yy=j+1;
}
}
printf("%d\n%d %d\n",mi,xx,yy);
return 0;
}Best spot C++ Solution
#include <stdio.h>
#include <algorithm>
#include <stdio.h>
#include <ctime>
#include <math.h>
using namespace std;
#define N 510
#define M 1000000000
#define L 600100
int m[N][N], g[N][N], s[N][N];
int na, nb, a[L], b[L];
double PI=2*acos(0.0);
struct C
{
double r, i;
C(double r=0, double i=0): r(r), i(i) {}
};
inline C add(const C &a, const C &b) { return C(a.r+b.r, a.i+b.i); }
inline C sub(const C &a, const C &b) { return C(a.r-b.r, a.i-b.i); }
inline C mul(const C &a, const C &b) { return C(a.r*b.r-a.i*b.i, a.r*b.i+a.i*b.r); }
int z[L];
C v[L], u[L];
void fft(int n)
{
int i, j, k;
C t, a, b;
for(i=0; i<n; u[i]=v[z[i]], i++);
for(i=1; i<n; i*=2)
for(a=C(cos(PI/i), sin(PI/i)), j=0; j<n; j+=2*i)
for(b=C(1, 0), k=j; k<j+i; t=mul(u[k+i], b), u[k+i]=sub(u[k], t), u[k]=add(u[k], t), b=mul(b, a), k++);
}
long long fl(double x) { return x>0?x+0.5:x-0.5; }
void mul(int *a, int na, int *b, int nb, int *c, int &nc)
{
int i, j, n;
for(nc=na+nb-1, n=1; n<nc; n*=2);
for(z[0]=0, j=1; j<n; j*=2)
for(i=0; i<j; z[i]+=z[i], z[i+j]=z[i]+1, i++);
for(i=0; i<n; v[i]=C(a[i], b[i]), i++);
for(fft(n), u[n]=u[0], i=0; i<n; v[i]=mul(C((u[i].r+u[n-i].r)/2, (u[i].i-u[n-i].i)/2), C((u[i].i+u[n-i].i)/2, (u[n-i].r-u[i].r)/2)), i++);
for(fft(n), u[n]=u[0], i=0; i<n; c[i]=fl(u[n-i].r/n), i++);
}
int main()
{
int i, j, r, c, w, h, k, l, bi, bj;
scanf("%d%d", &h, &w);
for(na=h*w, i=0; i<h; i++)
for(j=0; j<w; scanf("%d", &m[i][j]), a[i*w+j]=m[i][j], j++);
scanf("%d%d", &r, &c);
for(i=0; i<r; i++)
for(j=0; j<c; scanf("%d", &g[i][j]), j++);
for(nb=0, i=r-1; i>=0; i--)
{
for(j=c-1; j>=0; b[nb++]=g[i][j], j--);
if(i>0)
for(j=0; j<w-c; b[nb++]=0, j++);
}
mul(a, na, b, nb, a, na);
for(i=0; i<h; i++)
for(j=0; j<w; s[i+1][j+1]=s[i][j+1]+s[i+1][j]-s[i][j]+m[i][j]*m[i][j], j++);
for(k=M, i=0; i+r<=h; i++)
for(j=0; j+c<=w; j++)
{
l=s[i+r][j+c]-s[i][j+c]-s[i+r][j]+s[i][j];
l-=2*a[(i+r-1)*w+j+c-1];
if(l<k) { bi=i; bj=j; k=l; }
}
for(i=0; i<r; i++)
for(j=0; j<c; k+=g[i][j]*g[i][j], j++);
printf("%d\n%d %d\n", k, bi+1, bj+1);
return 0;
}Best spot C Sharp Solution
using System;
using System.IO;
using System.Collections.Generic;
namespace CSharpParser
{
public class Solution : SolutionBase
{
const int mod = 469762049;
int[] rev;
int LG;
int[] f,e,o;
void Fft(int[] a, int[] g)
{
for (var i = 0; i < a.Length; i++)
f[i] = a[rev[i]];
var n2 = a.Length / 2;
for (var i = LG - 1; i >= 0; i--)
{
for (var j = 0; j < n2; j++)
{
e[j] = f[j << 1];
o[j] = f[(j << 1) + 1];
}
for (var j = 0; j < n2; j++)
{
f[j] = (int)((e[j] + (long)o[j] * g[j >> i << i]) % mod);
f[n2 + j] = ((e[j] << 1) - f[j] + mod) % mod;
}
}
for (var i = 0; i < a.Length; i++)
a[i] = f[i];
}
protected override void Solve()
{
int n, m;
int w, h;
Next(out n);
Next(out m);
var a = NextArray<int>(n, m);
Next(out w);
Next(out h);
var b = NextArray<int>(w, h);
/*n = m = w = h = 500;
var a = new int[500, 500];
var b = new int[500, 500];
var rnd = new Random();
for (var i = 0; i < n; i++)
for (var j = 0; j < m; j++)
{
a[i, j] = rnd.Next(41) - 20;
b[i, j] = rnd.Next(41) - 20;
}*/
var l = 1;
LG = 0;
while (l < 2 * n * m)
{
l *= 2;
LG++;
}
rev = new int[l];
for (var i = 1; i < l; i++)
rev[i] = rev[i / 2] / 2 + i % 2 * (1 << LG - 1);
var root = 2187;
for (var i = l; i < 1 << 26; i *= 2)
root = (int)((long)root * root % mod);
var g = new int[l];
var _g = new int[l];
g[0] = _g[0] = 1;
for (var i = 1; i < g.Length; i++)
g[i] = (int)((long)g[i - 1] * root % mod);
for (var i = 1; i < g.Length; i++)
_g[i] = g[g.Length - i];
var ans = new long[n, m];
f = new int[l];
e = new int[l];
o = new int[l];
var c = new int[l];
var d = new int[l];
for (var i = 0; i < n; i++)
for (var j = 0; j < m; j++)
d[i * m + j] = (a[i, j] + mod) % mod;
for (var i = 0; i < w; i++)
for (var j = 0; j < h; j++)
c[n * m - i * m - 1 - j] = (b[i, j] + mod) % mod;
Fft(c, g);
Fft(d, g);
for (var i = 0; i < l; i++)
c[i] = (int)((long)c[i] * d[i] % mod);
Fft(c, _g);
for (var i = 0; i <= n - w; i++)
for (var j = 0; j <= m - h; j++)
{
ans[i, j] = ((long)(mod - mod / l) * c[n * m - 1 + m * i + j] % mod);
if (ans[i, j] > mod / 2)
ans[i, j] -= mod;
ans[i, j] *= -2;
}
for (var i = 0; i < n; i++)
for (var j = 0; j < m; j++)
{
a[i, j] *= a[i, j];
if (i > 0) a[i, j] += a[i - 1, j];
if (j > 0) a[i, j] += a[i, j - 1];
if (i > 0 && j > 0) a[i, j] -= a[i - 1, j - 1];
}
for (var i = 0; i <= n - w; i++)
for (var j = 0; j <= m - h; j++)
{
ans[i, j] += a[i + w - 1, j + h - 1];
if (i > 0)
ans[i, j] -= a[i - 1, j + h - 1];
if (j > 0)
ans[i, j] -= a[i + w - 1, j - 1];
if (i > 0 && j > 0)
ans[i, j] += a[i - 1, j - 1];
}
var sum = 0;
for (var i = 0; i < w; i++)
for (var j = 0; j < h; j++)
sum += b[i, j] * b[i, j];
var ii = 0;
var jj = 0;
for (var i = 0; i <= n - w; i++)
for (var j = 0; j <= m - h; j++)
if (ans[ii, jj] > ans[i, j])
{
ii = i;
jj = j;
}
PrintLine(ans[ii, jj] + sum);
ii++; jj++;
PrintLine(ii + " " + jj);
}
}
public static class Algorithm
{
public static void Swap<T>(ref T a, ref T b)
{
var temp = a;
a = b;
b = temp;
}
public static T Max<T>(params T[] a)
{
var ans = a[0];
var comp = Comparer<T>.Default;
for (var i = 1; i < a.Length; i++) ans = comp.Compare(ans, a[i]) >= 0 ? ans : a[i];
return ans;
}
public static T Min<T>(params T[] a)
{
var ans = a[0];
var comp = Comparer<T>.Default;
for (var i = 1; i < a.Length; i++) ans = comp.Compare(ans, a[i]) <= 0 ? ans : a[i];
return ans;
}
public static void RandomShuffle<T>(T[] a, int index, int length)
{
if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
var last = index + length;
if (last > a.Length) throw new ArgumentException();
var rnd = new Random(DateTime.Now.Millisecond);
for (var i = index + 1; i < last; i++) Swap(ref a[i], ref a[rnd.Next(index, i + 1)]);
}
public static void RandomShuffle<T>(T[] a)
{
RandomShuffle(a, 0, a.Length);
}
public static bool NextPermutation<T>(T[] a, int index, int length, Comparison<T> compare = null)
{
compare = compare ?? Comparer<T>.Default.Compare;
if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
var last = index + length;
if (last > a.Length) throw new ArgumentException();
for (var i = last - 1; i > index; i--)
if (compare(a[i], a[i - 1]) > 0)
{
var j = i + 1;
for (; j < last; j++) if (compare(a[j], a[i - 1]) <= 0) break;
Swap(ref a[i - 1], ref a[j - 1]);
Array.Reverse(a, i, last - i);
return true;
}
Array.Reverse(a, index, length);
return false;
}
public static bool NextPermutation<T>(T[] a, Comparison<T> compare = null)
{
return NextPermutation(a, 0, a.Length, compare);
}
public static bool PrevPermutation<T>(T[] a, int index, int length, Comparison<T> compare = null)
{
compare = compare ?? Comparer<T>.Default.Compare;
if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
var last = index + length;
if (last > a.Length) throw new ArgumentException();
for (var i = last - 1; i > index; i--)
if (compare(a[i], a[i - 1]) < 0)
{
var j = i + 1;
for (; j < last; j++) if (compare(a[j], a[i - 1]) >= 0) break;
Swap(ref a[i - 1], ref a[j - 1]);
Array.Reverse(a, i, last - i);
return true;
}
Array.Reverse(a, index, length);
return false;
}
public static bool PrevPermutation<T>(T[] a, Comparison<T> compare = null)
{
return PrevPermutation(a, 0, a.Length, compare);
}
public static int LowerBound<T>(IList<T> a, int index, int length, T value, Comparison<T> compare = null)
{
compare = compare ?? Comparer<T>.Default.Compare;
if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
if (index + length > a.Count) throw new ArgumentException();
var ans = index;
var last = index + length;
var p2 = 1;
while (p2 <= length) p2 *= 2;
for (p2 /= 2; p2 > 0; p2 /= 2) if (ans + p2 <= last && compare(a[ans + p2 - 1], value) < 0) ans += p2;
return ans;
}
public static int LowerBound<T>(IList<T> a, T value, Comparison<T> compare = null)
{
return LowerBound(a, 0, a.Count, value, compare);
}
public static int UpperBound<T>(IList<T> a, int index, int length, T value, Comparison<T> compare = null)
{
compare = compare ?? Comparer<T>.Default.Compare;
if (index < 0 || length < 0) throw new ArgumentOutOfRangeException();
if (index + length > a.Count) throw new ArgumentException();
var ans = index;
var last = index + length;
var p2 = 1;
while (p2 <= length) p2 *= 2;
for (p2 /= 2; p2 > 0; p2 /= 2) if (ans + p2 <= last && compare(a[ans + p2 - 1], value) <= 0) ans += p2;
return ans;
}
public static int UpperBound<T>(IList<T> a, T value, Comparison<T> compare = null)
{
return UpperBound(a, 0, a.Count, value, compare);
}
}
public class InStream : IDisposable
{
protected readonly TextReader InputStream;
private string[] _tokens;
private int _pointer;
private InStream(TextReader inputStream)
{
InputStream = inputStream;
}
public static InStream FromString(string str)
{
return new InStream(new StringReader(str));
}
public static InStream FromFile(string str)
{
return new InStream(new StreamReader(str));
}
public static InStream FromConsole()
{
return new InStream(Console.In);
}
public string NextLine()
{
try
{
return InputStream.ReadLine();
}
catch (Exception)
{
return null;
}
}
private string NextString()
{
try
{
while (_tokens == null || _pointer >= _tokens.Length)
{
_tokens = NextLine().Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
_pointer = 0;
}
return _tokens[_pointer++];
}
catch (Exception)
{
return null;
}
}
public bool Next<T>(out T ans)
{
var str = NextString();
if (str == null)
{
ans = default(T);
return false;
}
ans = (T)Convert.ChangeType(str, typeof(T));
return true;
}
public T[] NextArray<T>(int length)
{
var array = new T[length];
for (var i = 0; i < length; i++)
if (!Next(out array[i]))
return null;
return array;
}
public T[,] NextArray<T>(int length, int width)
{
var array = new T[length, width];
for (var i = 0; i < length; i++)
for (var j = 0; j < width; j++)
if (!Next(out array[i, j]))
return null;
return array;
}
public void Dispose()
{
InputStream.Close();
}
}
public class OutStream : IDisposable
{
protected readonly TextWriter OutputStream;
private OutStream(TextWriter outputStream)
{
OutputStream = outputStream;
}
public static OutStream FromString(System.Text.StringBuilder strB)
{
return new OutStream(new StringWriter(strB));
}
public static OutStream FromFile(string str)
{
return new OutStream(new StreamWriter(str));
}
public static OutStream FromConsole()
{
return new OutStream(Console.Out);
}
public void Print(string format, params object[] args)
{
OutputStream.Write(format, args);
}
public void PrintLine(string format, params object[] args)
{
Print(format, args);
OutputStream.WriteLine();
}
public void PrintLine()
{
OutputStream.WriteLine();
}
public void Print<T>(T o)
{
OutputStream.Write(o);
}
public void PrintLine<T>(T o)
{
OutputStream.WriteLine(o);
}
public void PrintArray<T>(IList<T> a, string between = " ", string after = "\n", bool printCount = false)
{
if (printCount)
PrintLine(a.Count);
for (var i = 0; i < a.Count; i++)
Print("{0}{1}", a[i], i == a.Count - 1 ? after : between);
}
public void Dispose()
{
OutputStream.Close();
}
}
public abstract class SolutionBase : IDisposable
{
private readonly InStream _in;
private readonly OutStream _out;
protected SolutionBase()
{
//System.Threading.Thread.CurrentThread.CurrentCulture = System.Globalization.CultureInfo.InvariantCulture;
_in = InStream.FromConsole();
_out = OutStream.FromConsole();
}
protected string NextLine()
{
return _in.NextLine();
}
protected bool Next<T>(out T ans)
{
return _in.Next(out ans);
}
protected T[] NextArray<T>(int length)
{
return _in.NextArray<T>(length);
}
protected T[,] NextArray<T>(int length, int width)
{
return _in.NextArray<T>(length, width);
}
protected void PrintArray<T>(IList<T> a, string between = " ", string after = "\n", bool printCount = false)
{
_out.PrintArray(a, between, after, printCount);
}
public void Print(string format, params object[] args)
{
_out.Print(format, args);
}
public void PrintLine(string format, params object[] args)
{
_out.PrintLine(format, args);
}
public void PrintLine()
{
_out.PrintLine();
}
public void Print<T>(T o)
{
_out.Print(o);
}
public void PrintLine<T>(T o)
{
_out.PrintLine(o);
}
public void Dispose()
{
_out.Dispose();
}
protected abstract void Solve();
public static void Main()
{
using (var p = new Solution()) p.Solve();
}
}
}Best spot Java Solution
import java.io.*;
import java.util.*;
public class Solution {
static void bestSpot(int[][] land, int[][] store, int r, int c, int h, int w) {
long sumDiff = 0;
int m = r - h;
int n = c - w;
long minSum = Integer.MAX_VALUE;
int minCol = n;
int minRow = m;
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
sumDiff = 0;
for (int k = 0; k < h; k++) {
for (int l = 0; l < w; l++) {
int z = land[i + k][j + l] - store[k][l];
sumDiff += z * z;
}
}
if (sumDiff == 0) {
minSum = sumDiff;
minRow = i;
minCol = j;
}
if (sumDiff < minSum) {
minSum = sumDiff;
minRow = i;
minCol = j;
} else if (sumDiff == minSum) {
if (minRow > i) {
minRow = i;
minCol = j;
} else if (minRow == i && minCol > j) {
minCol = j;
}
}
}
}
System.out.println(minSum);
System.out.println((minRow + 1) + " " + (minCol + 1));
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int[][] land = new int[r][c];
for (int i = 0; i < r; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < c; j++) {
int item = Integer.parseInt(st.nextToken());
land[i][j] = item;
}
}
st = new StringTokenizer(br.readLine());
int h = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int[][] store = new int[h][w];
for (int iwItr = 0; iwItr < h; iwItr++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < w; j++) {
int item = Integer.parseInt(st.nextToken());
store[iwItr][j] = item;
}
}
bestSpot(land, store, r, c, h, w);
br.close();
}
}Best spot JavaScript Solution
'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'bestSpot' function below.
*
* The function accepts following parameters:
* 1. 2D_INTEGER_ARRAY heights
* 2. 2D_INTEGER_ARRAY store
*/
function bestSpot(heights, store) {
const R = heights.length;
const C = heights[0].length;
const H = store.length;
const W = store[0].length;
let minSum = Infinity;
let minSumAdress = [0, 0];
for (let i = 0; i <= (R-H); i++) {
for (let j = 0; j <= (C-W); j++) {
let sum = 0;
for (let y = 0; y < H; y++) {
for (let x = 0; x < W; x++) {
const diff = heights[i + y][j + x] - store[y][x];
sum += diff * diff;
}
}
if (minSum > sum) {
minSum = sum;
minSumAdress = [i + 1, j + 1];
}
}
}
console.log(minSum);
console.log(minSumAdress.join(' '));
}
function main() {
const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');
const r = parseInt(firstMultipleInput[0], 10);
const c = parseInt(firstMultipleInput[1], 10);
let heights = Array(r);
for (let i = 0; i < r; i++) {
heights[i] = readLine().replace(/\s+$/g, '').split(' ').map(heightsTemp => parseInt(heightsTemp, 10));
}
const secondMultipleInput = readLine().replace(/\s+$/g, '').split(' ');
const h = parseInt(secondMultipleInput[0], 10);
const w = parseInt(secondMultipleInput[1], 10);
let store = Array(h);
for (let i = 0; i < h; i++) {
store[i] = readLine().replace(/\s+$/g, '').split(' ').map(storeTemp => parseInt(storeTemp, 10));
}
bestSpot(heights, store);
}Best spot Python Solution
#!/bin/python
input = '''
3 3
19 19 -12
5 8 -14
-12 -11 9
2 2
-18 -12
-10 -7
'''
output = '''
937
2 2
'''
import sys
from cmath import exp, pi
from itertools import izip
exp_table = []
N_exp_table = 0
def fft(x):
N = len(x)
N_mul = N_exp_table / N
if N <= 1: return x
even = fft(x[0::2])
odd = fft(x[1::2])
T = [exp_table[(k * N_mul) % N_exp_table] * odd[k] for k in xrange(N / 2)]
return [even[k] + T[k] for k in xrange(N / 2)] + \
[even[k] - T[k] for k in xrange(N / 2)]
def conj2(x):
for rows in x:
rows[:] = [a.conjugate() for a in rows]
return x
def ifft2(x):
for rows in x:
rows[:] = [a.conjugate() for a in rows]
x = fft2(x)
scale = len(x) * len(x[0])
for rows in x:
rows[:] = [a.conjugate() / scale for a in rows]
return x
def fft2(x):
if N2 > 1:
xfft1 = map(fft, x)
else:
xfft1 = x
if N1 > 1:
return map(fft, zip(*xfft1))
else:
return xfft1
def mul(a, b):
n1 = len(a)
n2 = len(a[0])
c = [[a[i][j] * b[i][j] for j in range(n2)] for i in range(n1)]
return c
def pow2(n):
n2 = 1
while n > 0:
n >>= 1
n2 <<= 1
return n2
def build_exp_table(N):
return [exp(-2j * pi * k / N) for k in range(N)]
R, C = (int(s) for s in raw_input().split())
N1 = pow2(R - 1)
N2 = pow2(C - 1)
exp_table = build_exp_table(max(N1, N2))
N_exp_table = max(N1, N2)
a1 = [[0] * N2 for _ in range(N1)]
a2 = [[0] * N2 for _ in range(N1)]
for i in range(R):
a1[i][:C] = [int(s) for s in raw_input().split()]
H, W = (int(s) for s in raw_input().split())
for i in range(H):
a2[i][:W] = [int(s) for s in raw_input().split()]
a1_sq = [[i ** 2 for i in rows] for rows in a1]
for i in xrange(1, R):
a1_sq[i][0] += a1_sq[i - 1][0]
for j in xrange(1, C):
a1_sq[0][j] += a1_sq[0][j - 1]
for i in xrange(1, R):
for j in xrange(1, C):
a1_sq[i][j] += a1_sq[i][j - 1] + a1_sq[i - 1][j] - a1_sq[i - 1][j - 1]
for i in xrange(R - 1, H - 1, -1):
for j in xrange(C - 1, W - 1, -1):
a1_sq[i][j] -= a1_sq[i - H][j] + a1_sq[i][j - W] - a1_sq[i - H][j - W]
for i in xrange(R - 1, H - 1, -1):
a1_sq[i][W - 1] -= a1_sq[i - H][W - 1]
for j in xrange(C - 1, W - 1, -1):
a1_sq[H - 1][j] -= a1_sq[H - 1][j - W]
for i in xrange(0, R - H + 1):
for j in xrange(0, C - W + 1):
a1_sq[i][j] = a1_sq[i + H - 1][j + W - 1]
a2_sq = sum((sum(el * el for el in rows) for rows in a2))
a1 = [map(float, row) for row in a1]
a2 = [map(float, row) for row in a2]
a1 = fft2(a1)
a2 = conj2(fft2(a2))
a12 = ifft2(mul(a1, a2))
res = [[int(round(a1_sq[i][j] - 2 * a12[i][j].real + a2_sq)) for j in range(C - W + 1)] for i in range(R - H + 1)]
min_res = res[0][0]
imin = 0
for irow, row in enumerate(res):
min_row = min(row)
imin = irow if min_row < min_res else imin
min_res = min(min_res, min(row))
jmin = res[imin].index(min_res)
print min_res
print imin + 1, jmin + 1
