In this HackerRank Best spot problem solution In Chile, the land is partitioned into 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 storm” which can be represented by a HxW grid. Element at position (i, j) represents the height of land at index (i, j) in the grid.
Shaka has purchased a land area that can be represented RxC grid (H <= R, W <= C). Shaka is interested in finding the best HxW sub-grid in the acquired land. In order to compare the possible sub-grids, Shaka will be using the sum of the squared difference between each cell of his “perfect storm” and it’s the corresponding cell in the subgrid. Amongst all possible sub-grids, he will choose the one with the smallest sum.
Problem solution in Java.
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(); } }
Problem solution in C++.
#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("%dn%d %dn", k, bi+1, bj+1); return 0; }
Problem solution in C.
#include <math.h> #include <stdio.h> #include <stdlib.h> typedef struct { double r; double i; } complex; int mapidx(int i, int j, int C, int H); void complexadd(complex *a, complex *b, complex *c); void complexsub(complex *a, complex *b, complex *c); void complexmul(complex *a, complex *b, complex *c); void auxfft(complex *a, complex *omega, int N, int NN); void fft(complex *a, complex *res, int N); void ifft(complex *a, complex *res, int N); void multiply(long long *a, long long *b, long long *res, int sizea, int sizeb); int RC[500][500], HW[500][500]; long long dp[501][501]; int main() { int R, C, H, W, i, j, idxi, idxj; long long sum = 0, min = -1, *A, *B, *CC, t; scanf("%d%d", &R, &C); for (i = 0; i < R; i++) for (j = 0; j < C; j++) scanf("%d", &RC[i][j]); scanf("%d%d", &H, &W); for (i = 0; i < H; i++) for (j = 0; j < W; j++) { scanf("%d", &HW[i][j]); sum += HW[i][j] * HW[i][j]; } A = (long long *)malloc(R * C * sizeof(long long)); B = (long long *)malloc(H * C * sizeof(long long)); CC = (long long *)malloc((R * C + H * C - 1) * sizeof(long long)); for (i = 0; i <= R; i++) dp[i][0] = 0; for (i = 0; i <= C; i++) dp[0][i] = 0; for (i = 1; i <= R; i++) for (j = 1; j <= C; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + RC[i - 1][j - 1] * RC[i - 1][j - 1]; A[(i - 1) * C + j - 1] = RC[i - 1][j - 1]; } for (i = 0; i < H; i++) for (j = 0; j < C; j++) B[i * C + j] = 0; for (i = 0; i < H; i++) for (j = 0; j < W; j++) B[i * C + j] = HW[i][j]; for (i = 0; i < H * C / 2; i++) { t = B[H * C - i - 1]; B[H * C - i - 1] = B[i]; B[i] = t; } multiply(A, B, CC, R * C, H * C); for (i = 0; i <= R - H; i++) for (j = 0; j <= C - W; j++) { t = sum - 2 * CC[mapidx(i, j, C, H)] + dp[i + H][j + W] - dp[i + H][j] - dp[i][j + W] + dp[i][j]; if (min == -1 || t < min) { min = t; idxi = i + 1; idxj = j + 1; } } printf("%lldn", min); printf("%d %d", idxi, idxj); return 0; } int mapidx(int i, int j, int C, int H) { return i * C + j + H * C - 1; } void complexadd(complex *a, complex *b, complex *c) { c->r = a->r + b->r; c->i = a->i + b->i; return; } void complexsub(complex *a, complex *b, complex *c) { c->r = a->r - b->r; c->i = a->i - b->i; return; } void complexmul(complex *a, complex *b, complex *c) { c->r = a->r * b->r - a->i * b->i; c->i = a->r * b->i + a->i * b->r; return; } void auxfft(complex *a, complex *omega, int N, int NN) { if (N == 1) return; int i, p; complex *odd, *even; odd = (complex *)malloc(N / 2 * sizeof(complex)); even = (complex *)malloc(N / 2 * sizeof(complex)); for (i = 0; i < N / 2; i++) { even[i] = a[2 * i]; odd[i] = a[2 * i + 1]; } auxfft(odd, omega, N / 2, NN); auxfft(even, omega, N / 2, NN); for (i = 0, p = NN / N; i < N / 2; i++) { complex t; complexmul(odd + i, omega + i * p, &t); complexadd(even + i, &t, a + i); complexsub(even + i, &t, a + i + N / 2); } free(odd); free(even); return; } void fft(complex *a, complex *res, int N) { int i; complex *omega = (complex *)malloc(N * sizeof(complex)), temp; double angle = 8 * atan(1) / N; for (i = 0; i < N; i++) { omega[i].r = cos(i * angle); omega[i].i = sin(i * angle); res[i] = a[i]; } auxfft(res, omega, N, N); for (i = 1; i < N / 2; i++) { temp = res[i]; res[i] = res[N - i]; res[N - i] = temp; } free(omega); return; } void ifft(complex *a, complex *res, int N) { int i; complex *omega = (complex *)malloc(N * sizeof(complex)); double angle = 8 * atan(1) / N; for (i = 0; i < N; i++) { omega[i].r = cos(i * angle); omega[i].i = sin(i * angle); res[i] = a[i]; } auxfft(res, omega, N, N); for (i = 0; i < N; i++) { res[i].r /= N; res[i].i /= N; } free(omega); return; } void multiply(long long *a, long long *b, long long *res, int sizea, int sizeb) { int n = 1, size = (sizea > sizeb) ? sizea : sizeb, i; while (n <= 2 * size) n <<= 1; complex *A, *B, *AA, *BB; A = (complex *)malloc(n * sizeof(complex)); B = (complex *)malloc(n * sizeof(complex)); AA = (complex *)malloc(n * sizeof(complex)); BB = (complex *)malloc(n * sizeof(complex)); for (i = 0; i < sizea; i++) { A[i].r = a[i]; A[i].i = 0; } for (i = sizea; i < n; i++) { A[i].r = 0; A[i].i = 0; } for (i = 0; i < sizeb; i++) { B[i].r = b[i]; B[i].i = 0; } for (i = sizeb; i < n; i++) { B[i].r = 0; B[i].i = 0; } fft(A, AA, n); fft(B, BB, n); for (i = 0; i < n; i++) complexmul(AA + i, BB + i, A + i); ifft(A, AA, n); for (i = 0; i < sizea + sizeb - 1; i++) res[i] = (long long)(AA[i].r + 0.5); free(A); free(B); free(AA); free(BB); return; }