We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home
  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Best spot

Best spot

Problem
Submissions
Leaderboard
Discussions
Editorial

In Chile, land are partitioned into a one large grid, where each element represents a land of size 1x1.

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

Author

shaka_shadows

Difficulty

Advanced

Max Score

100

Submitted By

1814

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits

Choose a translation


  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Helpdesk
  • Careers
  • Terms Of Service
  • Privacy Policy

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website