HackerRank Best spot Problem Solution Yashwant Parihar, August 24, 2023August 1, 2024 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.NoteThe 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)2Input FormatThe 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”.Constraints1 <= R, C <= 5001 <= H <= R1 <= W <= CNo height will have an absolute value greater than 20.Output FormatIn 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 Input3 3 19 19 -12 5 8 -14 -12 -11 9 2 2 -18 -12 -10 -7 Sample Output937 2 2 ExplanationThe result is computed as follows: (8 – (-18)) 2 + (-14 – (-12)) 2 + (-11 – (-10)) 2 + (9 – (-7)) 2 = 937HackerRank Best spot Problem SolutionBest 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 Solutionusing 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 Solutionimport 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 c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython