Google Kickstart Round A 2021: Rabbit House

Rabbit House: Problem Statement

Barbara got really good grades in school last year, so her parents decided to gift her with a pet rabbit. She was so excited that she built a house for the rabbit, which can be seen as a 2D grid with RR rows and CC columns.

Rabbits love to jump, so Barbara stacked several boxes on several cells of the grid. Each box is a cube with equal dimensions, which match exactly the dimensions of a cell of the grid.

However, Barbara soon realizes that it may be dangerous for the rabbit to make jumps of height greater than 11 box, so she decides to avoid that by making some adjustments to the house. For every pair of adjacent cells, Barbara would like that their absolute difference in height be at most 11 box. Two cells are considered adjacent if they share a common side.

As all the boxes are superglued, Barbara cannot remove any boxes that are there initially, however she can add boxes on top of them. She can add as many boxes as she wants, to as many cells as she wants (which may be zero). Help her determine what is the minimum total number of boxes to be added so that the rabbit’s house is safe.

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case begins with a line containing two integers R and C.

Then, RR lines follow, each with C integers. The j-th integer on i-th line, Gi,j, represents how many boxes are there initially on the cell located at the i-th row and j-th column of the grid.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of boxes to be added so that the rabbit’s house is safe.

For all the limits and test cases you can check the official problem page for Rabbit House here.

Solution:

To minimize the total number of boxes to be added so that the rabbit house is safe, we need to first look at the boxes having the maximum height. This becomes our starting point and we can go from there iterating over all the boxes in non increasing order of heights. So we will be certainly using max-heap to solve this problem.

At each step, for the current box with maximum height, we can get all of its adjacent boxes having heights with a difference of more than 1 when compared to the current box’s height and thus expand our heap. For each such adjacent box, the new height will be 1 less than the current maximum and hence the difference between this new height and the older one will be the number of boxes needed to ensure that the house is safe.

This algorithm will be a flavor of Dijkstra’s algorithm using max-heap. Have a look at the complete code below:-

rr = input
rri = lambda: int(rr())
rra = lambda: list(map(int, rr().split()))
import heapq

def solve(r,c,arr):

  hp=[]
  dirs=[[1,0],[0,1],[-1,0],[0,-1]] #Direction array for finding the adjacent boxes
  for i in range(r):
    for j in range(c):
      heapq.heappush(hp,[-arr[i][j],i,j]) #Max-heap of heights of boxes

  res=0
  visited=[[0]*c for _ in range(r)]  
  count=0 # To keep track of 

  while len(hp) and count1: #Only the adjacent boxes that don't satisfy safety criteria will be considered
          heapq.heappush(hp,[-height+1,x,y]) # adjacent boxes height will be 1 less than maximum

  return res

T = rri()
for t in range(1, T + 1):
  r,c = rra() #multiple input - 1 D
  arr = []
  for _ in range(r): #2D
    arr.append(rra())
  print('Case #{}: {}'.format(t, solve(r,c, arr)))

Time Complexity- O(R*C*log(R*C))

It will take O(R*C) time to traverse the max-heap and O(log(R*C)) to pop the current highest box from the heap. So in all, it will cost O(R*C*log(R*C)) time.

Space Complexity- O(R*C)

It will cost O(R*C) space to store the heap of R*C cells.

If you have any questions or thoughts, do let me know in the comments below.