rabbit house

Problem

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 R rows and C 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 1 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 1 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 hew 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, R 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.

Limits

Memory limit: 1 GB.
1<=T<=100.
0<=Gi,j<=2106, for all i, j.

Test Set 1

Time limit: 20 seconds.
1<=R,C<=50.

Test Set 2

Time limit: 40 seconds.
1<=R,C<=300.

In Sample Case #1, the absolute difference in height for every pair of adjacent cells is already at most 1 box, so there is no need to add any extra boxes.

In Sample Case #2, the absolute difference in height of the left-most cell and the middle cell is 3 boxes. To fix that, we can add 2 boxes to the middle cell. But then, the absolute difference of the middle cell and the right-most cell will be 2 boxes, so Barbara can fix that by adding 1 box to the right-most cell. After adding these 3 boxes, the safety condition is satisfied.

In Sample Case #3, the cell in the middle of the grid has an absolute difference in height of 2 boxes with all of its four adjacent cells. One solution is to add exactly 1 box to all of the middle's adjacent cells, so that the absolute difference between any pair of adjacent cells will be at most 1 box. That requires 4 boxes in total.

Sample Input & Output

3
1 3
3 4 3
1 3
3 0 0
3 3
0 0 0
0 2 0
0 0 0
Case #1: 0
Case #2: 3
Case #3: 4

Rust Solution

use rustgym_util::*;
use std::collections::BinaryHeap;
use std::fmt::Write;
use std::io::*;

fn solve(case_no: usize, reader: &mut impl BufRead, writer: &mut impl Write) {
    let args: Vec<usize> = reader.parse_vec();
    let r = args[0];
    let c = args[1];
    let mut queue: BinaryHeap<(i64, usize, usize)> = BinaryHeap::new();
    let a: Vec<Vec<i64>> = reader.parse_mat(r);
    for i in 0..r {
        for j in 0..c {
            queue.push((a[i][j], i, j));
        }
    }
    let mut b: Vec<Vec<i64>> = a.clone();
    let mut res = 0;
    while let Some((h, i, j)) = queue.pop() {
        res += h - a[i][j];
        if i > 0 && h - 1 > b[i - 1][j] {
            b[i - 1][j] = h - 1;
            queue.push((h - 1, i - 1, j));
        }
        if j > 0 && h - 1 > b[i][j - 1] {
            b[i][j - 1] = h - 1;
            queue.push((h - 1, i, j - 1));
        }
        if i + 1 < r && h - 1 > b[i + 1][j] {
            b[i + 1][j] = h - 1;
            queue.push((h - 1, i + 1, j));
        }
        if j + 1 < c && h - 1 > b[i][j + 1] {
            b[i][j + 1] = h - 1;
            queue.push((h - 1, i, j + 1));
        }
    }
    writeln!(writer, "Case #{}: {}", case_no, res).unwrap();
}

google_test_gen!(test, "input.txt", "output.txt");

Analysis

Barbara is given a 2D grid with R rows and C columns. Her goal is to create a grid such that no two adjacent cells have an absolute difference in height greater than 1. Moreover, she is only allowed to increase the height of cells.

We notice that the cell initially with the largest height (H) never requires increasing. Furthermore, Barbara can update its neighbor cells to have a height of H1 (unless they already have a height of H). Afterwards, she can repeat the process for the cell with the next largest height, until she visits all the cells.

One thing to be careful of in this problem is that the final result can be larger than the limits of a 32-bit integer. Using 64-bit integers avoids WAs due to overflow.

Test set 1

For this test set, Barbara sees that 1<=R,C<=50. Therefore, she performs a linear scan over the grid to find the cell with the largest height. Then, she updates the height of its neighbors, and increments the result to account for the increase in height.

Finally, she marks this cell as visited, which can be done via a secondary 2D grid of booleans. She repeats the above process until all cells have been visited, and return the result.

The linear scan can be done in O(RC), and Barbara visits each cell exactly once, so she performs the linear scan O(RC) times. The overall time complexity is therefore O((RC)2). This fits within the limits of the small test set.
The additional space complexity is O(RC) due to the secondary 2D grid of booleans.

Test set 2

For this test set, 1<=R,C<=300. A time complexity of O((RC)2) will not satisfy the time limits.

Barbara still needs to visit the unvisited cell with the largest height in each iteration. However, this can be done in O(log(RC)) using a priority queue. In each iteration, she pops the cell with the largest height, updates the height of its neighbors in the priority queue, and increments the result.

The time complexity of the above solution is O(RClog(RC)). The additional space complexity is still O(RC), since initially the priority queue contains all the cells.

Note that, depending on the implementation, updating a non-top element in the priority queue might not be an O(1) operation. In such cases, one trick would be to insert a new element into the queue with the new height, and update the height in the grid. On processing any element, check whether the height in the queue corresponds to the height in the grid, and ignore the element otherwise. This does not change the worst-case time and space complexity, since the maximum number of times a cell can be added to the queue is 4.

Further Improvements

While not necessary to pass the time limits, the time complexity can be reduced further.

One approach is to replace the priority queue with a list of buckets, each bucket containing a set of cells with a given height. With this approach, Barbara can iterate over the buckets in decreasing order of height in order to visit each cell, then apply the same algorithm as above: update the neighbors (by placing them in their new buckets according to their new height), and remove the visited cells from the list.

By using a hashset for each bucket, insertion and removal becomes an O(1) operation. She can also use a vector. However, the trick from Test Set 2 is needed to maintain an O(1) insertion/removal in that case. Iterating over the buckets is linear in the number of buckets, and she will visit at most O(RC) cells.

Let G=max(Gi,j). Since no cell has an initial height larger than G, and she will never increase the height of the cell with the largest height, she observes that the number of buckets is at most G. This leads to a time complexity of O(RC+G).

Barbara can improve this further. Notice that all cells in the final grid will have a height of at least GRC+2. She achieves this value by decreasing the height by 1 with each step away from the highest cell. The maximum number of steps occurs when the highest cell is in a corner of the grid: the opposite corner is R+C2 steps away.

Now, she can first increase the height of all cells to GRC+2, then apply the same bucketing approach. Except, now the number of buckets is R+C2, leading to a time complexity of O(RC+R+C)=O(RC).

Having problems with this solution? Click here to submit an issue on github.