HackerRank Best spot problem solution

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;
}