Hello everyone welcome to www.techinfodiaries.com
Checksum Solution kickstart 2021
Problem
Grace and Edsger are constructing a N×NN×N boolean matrix AA. The element in ii-th row and jj-th column is represented by Ai,jAi,j. They decide to note down the checksum (defined as bitwise XOR of given list of elements) along each row and column. Checksum of ii-th row is represented as RiRi. Checksum of jj-th column is represented as CjCj.
For example, if N=2N=2, A=[1101]A=[1011], then R=[10]R=[10] and C=[01]C=[01].
Once they finished the matrix, Edsger stores the matrix in his computer. However, due to a virus, some of the elements in matrix AA are replaced with −1−1 in Edsger’s computer. Luckily, Edsger still remembers the checksum values. He would like to restore the matrix, and reaches out to Grace for help. After some investigation, it will take Bi,jBi,j hours for Grace to recover the original value of Ai,jAi,j from the disk. Given the final matrix AA, cost matrix BB, and checksums along each row (RR) and column (CC), can you help Grace decide on the minimum total number of hours needed in order to restore the original matrix AA?
Input
The first line of the input gives the number of test cases, TT. TT test cases follow.
The first line of each test case contains a single integer NN.
The next NN lines each contain NN integers representing the matrix AA. jj-th element on the ii-th line represents Ai,jAi,j.
The next NN lines each contain NN integers representing the matrix BB. jj-th element on the ii-th line represents Bi,jBi,j.
The next line contains NN integers representing the checksum of the rows. ii-th element represents RiRi.
The next line contains NN integers representing the checksum of the columns. jj-th element represents CjCj.
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 hours to restore matrix AA.
Limits
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
−1≤Ai,j≤1−1≤Ai,j≤1, for all i,ji,j.
1≤Bi,j≤10001≤Bi,j≤1000, for i,ji,j where Ai,j=−1Ai,j=−1, otherwise Bi,j=0Bi,j=0.
0≤Ri≤10≤Ri≤1, for all ii.
0≤Cj≤10≤Cj≤1, for all jj.
It is guaranteed that there exist at least one way to replace −1−1 in AA with 00 or 11 such that RR and CC as satisfied.
Test Set 1
Time limit: 20 seconds.
1≤N≤41≤N≤4.
Test Set 2
Time limit: 35 seconds.
1≤N≤401≤N≤40.
Test Set 3
Time limit: 35 seconds.
1≤N≤5001≤N≤500.
Sample
Sample Inputsave_altcontent_copy
3 3 1 -1 0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 1 2 -1 -1 -1 -1 1 10 100 1000 1 0 0 1 3 -1 -1 -1 -1 -1 -1 0 0 0 1 1 3 5 1 4 0 0 0 0 0 0 0 0 0
Sample Outputsave_altcontent_copy
Case #1: 0 Case #2: 1 Case #3: 2
In Sample Case #1, A1,2A1,2 can be restored using the checksum of either 1-st row or 2-nd column. Hence, Grace can restore the matrix without spending any time to recover the data.
In Sample Case #2, Grace spends one hour to recover A1,1A1,1. After that, she can use checksums of 1-st row and 1-st column to restore A1,2A1,2 and A2,1A2,1 respectively. And then she can use checksum of 2-nd row to restore A2,2A2,2. Hence, Grace can restore the matrix by spending one hour.
In Sample Case #3, Grace can spend one hour to recover A1,1A1,1 and another hour to recover A2,2A2,2. After that, she can use checksum to restore the rest of the matrix. Hence, Grace can restore the matrix by spending two hours 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 N; cin >> N;
tensor<int, 2> A({N, N});
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[{i,j}];
}
}
tensor<int, 2> B({N, N});
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> B[{i,j}];
}
}
vector<int> R(N);
for (auto& r : R) cin >> r;
vector<int> C(N);
for (auto& c : C) cin >> c;
vector<vector<array<int, 2>>> vals(1001);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
vals[B[{i,j}]].push_back({i,j});
}
}
const int V = 2 * N;
vector<int> par(V, -1);
auto get_par = [&](int a) -> int {
while (par[a] >= 0) {
if (par[par[a]] >= 0) par[a] = par[par[a]];
a = par[a];
}
return a;
};
auto merge = [&](int a, int b) -> bool {
a = get_par(a);
b = get_par(b);
if (a == b) return false;
if (par[a] > par[b]) swap(a, b);
par[a] += par[b];
par[b] = a;
return true;
};
int64_t ans = 0;
for (int v = 1000; v >= 0; v–) {
for (auto [i, j] : vals[v]) {
if (!merge(i,N+j)) ans += v;
}
}
cout << “Case #” << case_num << “: ” << ans << ‘\n’;
}
return 0;
}
Also Read:
2 thoughts on “Checksum Solution kickstart 2021”