Hello everyone welcome to www.techinfodiaries.com
Rabbit House Solution kickstart 2021
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 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, TT. TT test cases follow.
Each test case begins with a line containing two integers RR and CC.
Then, RR lines follow, each with CC integers. The jj-th integer on ii-th line, Gi,jGi,j, represents how many boxes are there initially on the cell located at the ii-th row and jj-th column of the grid.
Output
For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the minimum number of boxes to be added so that the rabbit’s house is safe.
Limits
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
0≤Gi,j≤2⋅1060≤Gi,j≤2⋅106, for all ii, jj.
Test Set 1
Time limit: 20 seconds.
1≤R,C≤501≤R,C≤50.
Test Set 2
Time limit: 40 seconds.
1≤R,C≤3001≤R,C≤300.
Sample
Sample Inputsave_altcontent_copy
3 1 3 3 4 3 1 3 3 0 0 3 3 0 0 0 0 2 0 0 0 0
Sample Outputsave_altcontent_copy
Case #1: 0 Case #2: 3 Case #3: 4
In Sample Case #1, the absolute difference in height for every pair of adjacent cells is already at most 11 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 33 boxes. To fix that, we can add 22 boxes to the middle cell. But then, the absolute difference of the middle cell and the right-most cell will be 22 boxes, so Barbara can fix that by adding 11 box to the right-most cell. After adding these 33 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 22 boxes with all of its four adjacent cells. One solution is to add exactly 11 box to all of the middle’s adjacent cells, so that the absolute difference between any pair of adjacent cells will be at most 11 box. That requires 44 boxes in total.
Solution :
#include<bits/stdc++.h>
template <typename T, int NDIMS> struct tensor_view {
static_assert(NDIMS >= 0, “NDIMS must be nonnegative”);
protected:
std::array<int, NDIMS> shape;
std::array<int, NDIMS> strides;
T* data;
tensor_view(std::array<int, NDIMS> shape_, std::array<int, NDIMS> strides_, T* data_) : shape(shape_), strides(strides_), data(data_) {}
public:
tensor_view() : shape{0}, strides{0}, data(nullptr) {}
protected:
int flatten_index(std::array<int, NDIMS> idx) const {
int res = 0;
for (int i = 0; i < NDIMS; i++) { res += idx[i] * strides[i]; }
return res;
}
int flatten_index_checked(std::array<int, NDIMS> idx) const {
int res = 0;
for (int i = 0; i < NDIMS; i++) {
assert(0 <= idx[i] && idx[i] < shape[i]);
res += idx[i] * strides[i];
}
return res;
}
public:
T& operator[] (std::array<int, NDIMS> idx) const {
return data[flatten_index(idx)];
}
T& at(std::array<int, NDIMS> idx) const {
return data[flatten_index_checked(idx)];
}
template <int D = NDIMS>
typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) const {
std::array<int, NDIMS-1> nshape; std::copy(shape.begin()+1, shape.end(), nshape.begin());
std::array<int, NDIMS-1> nstrides; std::copy(strides.begin()+1, strides.end(), nstrides.begin());
T* ndata = data + (strides[0] * idx);
return tensor_view<T, NDIMS-1>(nshape, nstrides, ndata);
}
template <int D = NDIMS>
typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) const {
assert(0 <= idx && idx < shape[0]);
return operator[](idx);
}
template <int D = NDIMS>
typename std::enable_if<(0 == D), T&>::type operator * () const {
return *data;
}
template <typename U, int D> friend struct tensor_view;
template <typename U, int D> friend struct tensor;
};
template <typename T, int NDIMS> struct tensor {
static_assert(NDIMS >= 0, “NDIMS must be nonnegative”);
protected:
std::array<int, NDIMS> shape;
std::array<int, NDIMS> strides;
int len;
T* data;
public:
tensor() : shape{0}, strides{0}, len(0), data(nullptr) {}
explicit tensor(std::array<int, NDIMS> shape_, const T& t = T()) {
shape = shape_;
strides[NDIMS-1] = 1;
for (int i = NDIMS-1; i > 0; i–) {
strides[i-1] = strides[i] * shape[i];
}
len = strides[0] * shape[0];
data = new T[len];
std::fill(data, data + len, t);
}
tensor(const tensor& o) : shape(o.shape), strides(o.strides), len(o.len), data(new T[len]) {
for (int i = 0; i < len; i++) {
data[i] = o.data[i];
}
}
tensor& operator=(tensor&& o) noexcept {
using std::swap;
swap(shape, o.shape);
swap(strides, o.strides);
swap(len, o.len);
swap(data, o.data);
return *this;
}
tensor(tensor&& o) : tensor() {
*this = std::move(o);
}
tensor& operator=(const tensor& o) {
return *this = tensor(o);
}
~tensor() { delete[] data; }
using view_t = tensor_view<T, NDIMS>;
view_t view() {
return tensor_view<T, NDIMS>(shape, strides, data);
}
operator view_t() {
return view();
}
using const_view_t = tensor_view<const T, NDIMS>;
const_view_t view() const {
return tensor_view<const T, NDIMS>(shape, strides, data);
}
operator const_view_t() const {
return view();
}
T& operator[] (std::array<int, NDIMS> idx) { return view()[idx]; }
T& at(std::array<int, NDIMS> idx) { return view().at(idx); }
const T& operator[] (std::array<int, NDIMS> idx) const { return view()[idx]; }
const T& at(std::array<int, NDIMS> idx) const { return view().at(idx); }
template <int D = NDIMS>
typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) {
return view()[idx];
}
template <int D = NDIMS>
typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) {
return view().at(idx);
}
template <int D = NDIMS>
typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type operator[] (int idx) const {
return view()[idx];
}
template <int D = NDIMS>
typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type at(int idx) const {
return view().at(idx);
}
template <int D = NDIMS>
typename std::enable_if<(0 == D), T&>::type operator * () {
return *view();
}
template <int D = NDIMS>
typename std::enable_if<(0 == D), const T&>::type operator * () const {
return *view();
}
};
int main() {
using namespace std;
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int T; cin >> T;
for (int case_num = 1; case_num <= T; case_num ++) {
int R, C; cin >> R >> C;
int64_t ans = 0;
tensor<int, 2> G({R, C});
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> G[{i,j}];
ans -= G[{i,j}];
}
}
for (int i = 0; i < R; i++) {
for (int j = 1; j < C; j++) {
G[{i,j}] = max(G[{i,j}], G[{i,j-1}] – 1);
}
for (int j = C-2; j >= 0; j–) {
G[{i,j}] = max(G[{i,j}], G[{i,j+1}] – 1);
}
}
for (int i = 1; i < R; i++) {
for (int j = 0; j < C; j++) {
G[{i,j}] = max(G[{i,j}], G[{i-1,j}] – 1);
}
}
for (int i = R-2; i >= 0; i–) {
for (int j = 0; j < C; j++) {
G[{i,j}] = max(G[{i,j}], G[{i+1,j}] – 1);
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
ans += G[{i,j}];
}
}
cout << “Case #” << case_num << “: ” << ans << ‘\n’;
}
return 0;
}
Also Read:
2 thoughts on “Rabbit House Solution kickstart 2021”