INSQ15_H - Editorial

general
, ,
1

PROBLEM LINK:

Collect the Blocks

Author: Priyanshu Srivastava
Editorialist: Priyanshu Srivastava

DIFFICULTY:

MEDIUM

PREREQUISITES:

Dynamic Programming, Binary Search

PROBLEM:

Iron Blocks are present at various positions on an infinite field. In each query, from a given position on the field, you are to find the minimum distance M such that at least K blocks are at a distance <= M from you.

&nbsp&nbsp&nbsp distance((x1,y1),(x2,y2)) = max(abs(x1-x2),abs(y1-y2))

QUICK EXPLANATION:

A matrix is created with the x and y coordinates of the given blocks and filled using dynamic programming, so that the number of 1’s in any particular rectangle can be found in O(1).

Now for the given x,y coordinates, binary search is used to find the smallest k’ such that number of ones in square from [x-k’,y-k’] to [x+k’,y+k’] is greater than k.

EXPLANATION:

A 2-D matrix is created to represent the field.
All the x-coordinates of the iron blocks are mapped to the rows of the matrix and the y-coordinates of the iron blocks to the columns of the matrix. The matrix is filled using Dynamic Programming such that each cell (x,y) contains the number of iron blocks in the rectangle from (0,0) to (x,y).

To handle queries of the form (xx,yy,k) where there is no block such that x-coordinate of block = xx or y-coordinate of block = yy, we insert intermediary rows and columns between each row and column of matrix that represents the range between the surrounding rows or columns.

dp[0][i] = 0

dp[i][0] = 0

dp[i][j] = 1, for each (i,j) such that there is an iron block at point represented by (i,j).

dp[i][j] = dp[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

Now for the query (xx,yy,k), we use binary search to find the smallest m such that number of blocks in square from (xx-m,yy-m) to (xx+m,yy+m) contains greater than or equal to k blocks.

Number of blocks in rectangle from (x’,y’) to (x’’,y’’) = dp[x’’][y’’]-dp[x’’][y’-1] - dp[x’-1][y’’] + dp[x’-1][y’-1].

beg = 0 , end = n
ans = -1
while beg ≤ end:
	mid = ( beg + end ) / 2
	// Find the number of 1's in square from [x-mid,y-mid] to [x+mid,y+mid]
	// Find which row of dp – matrix represents x – mid, y – mid , x + mid , y + mid
	// Let they be called x',y',x'',y''
	num1s = dp[x''][y''] – dp[x'-mid-1][y''] – dp[x''][y'–mid–1] + dp[x'–mid–1][y'– mid–1]
	if num1s ≥ k :
		ans = mid
		end = mid – 1
	else :
		ans = mid + 1

Extra Case : if k > n output -1

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

RELATED PROBLEMS:

1 Like