Hello everyone welcome to www.techinfodiaries.com
L Shaped Plots solution kickstart 2021
Problem
Given a grid of RR rows and CC columns each cell in the grid is either 00 or 11.
A segment is a nonempty sequence of consecutive cells such that all cells are in the same row or the same column. We define the length of a segment as number of cells in the sequence.
A segment is called “good” if all the cells in the segment contain only 11s.
An “L-shape” is defined as an unordered pair of segments, which has all the following properties:
- Each of the segments must be a “good” segment.
- The two segments must be perpendicular to each other.
- The segments must share one cell that is an endpoint of both segments.
- Segments must have length at least 22.
- The length of the longer segment is twice the length of the shorter segment.
We need to count the number of L-shapes in the grid.
Below you can find two examples of correct L-shapes,
and three examples of invalid L-shapes.
Note that in the shape on the left, two segments do not share a common endpoint. The next two shapes do not meet the last requirement, as in the middle shape both segments have the same length, and in the last shape the longer segment is longer than twice the length of the shorter one.
Input
The first line of the input contains the number of test cases, TT. TT test cases follow.
The first line of each testcase contains two integers RR and CC.
Then, RR lines follow, each line with CC integers representing the cells 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 number of L-shapes.
Limits
Time limit: 60 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
Grid consists of 00s and 11s only.
Test Set 1
1≤R≤401≤R≤40.
1≤C≤401≤C≤40.
Test Set 2
1≤R≤10001≤R≤1000 and 1≤C≤10001≤C≤1000 for at most 55 test cases.
For the remaining cases, 1≤R≤401≤R≤40 and 1≤C≤401≤C≤40.
Sample
Sample Inputsave_altcontent_copy
2 4 3 1 0 0 1 0 1 1 0 0 1 1 0 6 4 1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0
Sample Outputsave_altcontent_copy
Case #1: 1 Case #2: 9
In Sample Case #1, there is one L-shape.
- The first one is formed by using cells: (1,1)(1,1), (2,1)(2,1), (3,1)(3,1), (4,1)(4,1), (4,2)(4,2)
In Sample Case #2, there are nine L-shapes.
- The first one is formed by using cells: (1,1)(1,1), (2,1)(2,1), (3,1)(3,1), (4,1)(4,1), (5,1)(5,1), (6,1)(6,1), (6,2)(6,2), (6,3)(6,3)
- The second one is formed by using cells: (3,1)(3,1), (4,1)(4,1), (5,1)(5,1), (6,1)(6,1), (6,2)(6,2)
- The third one is formed by using cells: (6,1)(6,1), (5,1)(5,1), (4,1)(4,1), (3,1)(3,1), (3,2)(3,2)
- The fourth one is formed by using cells: (3,3)(3,3), (4,3)(4,3), (5,3)(5,3), (6,3)(6,3), (6,2)(6,2)
- The fifth one is formed by using cells: (6,3)(6,3), (5,3)(5,3), (4,3)(4,3), (3,3)(3,3), (3,2)(3,2)
- The sixth one is formed by using cells: (3,1)(3,1), (3,2)(3,2), (3,3)(3,3), (3,4)(3,4), (2,4)(2,4)
- The seventh one is formed by using cells: (3,4)(3,4), (3,3)(3,3), (3,2)(3,2), (3,1)(3,1), (2,1)(2,1)
- The eighth one is formed by using cells: (3,4)(3,4), (3,3)(3,3), (3,2)(3,2), (3,1)(3,1), (4,1)(4,1)
- The ninth one is formed by using cells: (6,3)(6,3), (5,3)(5,3), (4,3)(4,3), (3,3)(3,3), (3,4)(3,4)
The first three L-shapes are shown on the picture below.
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;
tensor<int, 2> G({R, C});
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> G[{i,j}];
}
}
int ans = 0;
for (int flip_rows : {0, 1}) {
for (int flip_cols : {0, 1}) {
tensor<int, 2> row_max({R, C}, 0);
tensor<int, 2> col_max({R, C}, 0);
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (!G[{i,j}]) {
row_max[{i,j}] = col_max[{i,j}] = 0;
continue;
}
int a = row_max[{i,j}] = 1 + (j ? row_max[{i,j-1}] : 0);
int b = col_max[{i,j}] = 1 + (i ? col_max[{i-1,j}] : 0);
ans += max(0, min(a/2, b) – 1);
ans += max(0, min(a, b/2) – 1);
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C/2; j++) {
swap(G[{i,j}], G[{i,C-1-j}]);
}
}
}
for (int i = 0; i < R/2; i++) {
for (int j = 0; j < C; j++) {
swap(G[{i,j}], G[{R-i-1,j}]);
}
}
}
cout << “Case #” << case_num << “: ” << ans << ‘\n’;
}
return 0;
}
2 thoughts on “L Shaped Plots solution kickstart 2021”