Challenge: Cross Matrix
Subdomeniu: Algebra (algebra)
Scor cont: 120.0 / 120
Submission status: Accepted
Submission score: 1.0
Submission ID: 464834972
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/cross-matrix/problem
Cerinta
You are given a *N* * *N* matrix, *U*. You have to choose 2 sub-matrices A and B made of only 1s of *U*, such that, they have at least 1 cell in common, and each matrix is not completely engulfed by the other, i.e.,
If *U* is of the form
and *A* is of the form
and *B* is of the form
then, there exists atleast 1 a<sub>i, j</sub> : a<sub>i, j</sub> ∈ *A* and a<sub>i,j</sub> ∈ *B*
then, there exists atleast 1 a<sub>i1, j1</sub> : a<sub>i1, j1</sub> ∈ *A* and a<sub>i1,j1</sub> ∉ *B*
then, there exists atleast 1 a<sub>i2, j2</sub> : a<sub>i2, j2</sub> ∈ *B* and a<sub>i2,j2</sub> ∉ *A*
a<sub>x,y</sub> = 1 ∀ a<sub>x,y</sub> ∈ *A*
a<sub>x,y</sub> = 1 ∀ a<sub>x,y</sub> ∈ *B*
How many such (*A*, *B*) exist?
**Input Format**
The first line of the input contains a number *N*.
*N* lines follow, each line containing *N* integers (0/1) **NOT** separated by any space.
**Output Format**
Output the total number of such (A, B) pairs. If the answer is greater than or equal to 10<sup>9</sup> + 7,
then print answer modulo (%) 10<sup>9</sup> + 7.
**Constraints**
2 ≤ *N* ≤ 1500
a<sub>i,j</sub> ∈ [0, 1] : 0 ≤ i, j ≤ N - 1
**Sample Input**
4
0010
0001
1010
1110
**Sample Output**
10
**Explanation**
X means the common part of A and B. <br>
We can swap A and B to get another answer.
0010
0001
A010
XB10
0010
0001
A010
XBB0
0010
0001
10A0
1BX0
0010
0001
10A0
BBX0
0010
0001
1010
AXB0
**TimeLimits**
Time limit for this challenge is mentioned [here](http://hr-testcases.s3.amazonaws.com/2492/timelimit.json)Cod sursa
#include <bits/stdc++.h>
using namespace std;
// Cross Matrix - HackerRank
// Count ordered pairs of overlapping all-ones submatrices such that neither contains the other.
static const int MOD = 1000000007;
static inline int addmod(int a,int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
static inline int submod(int a,int b){ a-=b; if(a<0) a+=MOD; return a; }
static vector<int> genUBound(const vector<string>& mat){
int n = (int)mat.size();
vector<int> ub(n*n, 0);
for(int i=0;i<n;i++){
int rowOff = i*n;
int prevOff = (i-1)*n;
for(int j=0;j<n;j++){
if(mat[i][j]=='1'){
ub[rowOff + j] = (i==0 ? 1 : ub[prevOff + j] + 1);
}
}
}
return ub;
}
static void reverseEachRow(vector<int>& a, int n){
for(int i=0;i<n;i++){
auto it = a.begin() + i*n;
reverse(it, it + n);
}
}
static vector<int> genCounter(const vector<int>& ub, int n){
vector<int> counter(n*n, 0);
vector<int> left(n), st(n);
for(int i=0;i<n;i++){
int end = -1;
int base = i*n;
for(int j=0;j<n;j++){
int h = ub[base + j];
left[j] = j;
while(end >= 0 && h <= ub[base + st[end]]){
left[j] = left[st[end]];
end--;
}
if(end==-1 || h != ub[base + st[end]]) st[++end] = j;
long long val = 1LL*(j - left[j] + 1) * h;
if(left[j] > 0) val += counter[base + left[j] - 1];
counter[base + j] = (int)(val % MOD);
}
}
return counter;
}
static vector<int> genSum(vector<int> counter, int n){
for(int i=0;i<n;i++){
int base = i*n;
for(int j=1;j<n;j++){
counter[base + j] = addmod(counter[base + j], counter[base + j - 1]);
}
}
for(int i=1;i<n;i++){
int base = i*n;
int prev = (i-1)*n;
for(int j=0;j<n;j++){
counter[base + j] = addmod(counter[base + j], counter[prev + j]);
}
}
return counter;
}
static long long comb3(long long t){
if(t < 3) return 0;
__int128 v = (__int128)t * (t-1) * (t-2);
v /= 6;
return (long long)(v % MOD);
}
static long long comb4(long long t){
if(t < 4) return 0;
__int128 v = (__int128)t * (t-1) * (t-2) * (t-3);
v /= 24;
return (long long)(v % MOD);
}
static int containPairs(const vector<int>& ub, int n){
int H = n, W = n;
vector<int> diff((H+1)*(W+1), 0); // can be negative
vector<int> left(W+1), st(W+1);
for(int i=0;i<n;i++){
int end = -1;
int base = i*n;
for(int j=0;j<=n;j++){
int cHeight = (j==n ? 0 : ub[base + j]);
left[j] = j;
while(end >= 0 && cHeight < ub[base + st[end]]){
int height = ub[base + st[end]];
left[j] = left[st[end]];
int width = j - left[st[end]];
end--;
int mHeight = (end >= 0) ? max(cHeight, ub[base + st[end]]) : cHeight;
diff[height*(W+1) + width] += 1;
diff[mHeight*(W+1) + width] -= 1;
}
if(end == -1 || cHeight > ub[base + st[end]]){
st[++end] = j;
}
}
}
int maxDim = n + 5;
vector<long long> cm3(maxDim+1, 0), cm4(maxDim+1, 0);
for(int i=0;i<=maxDim;i++){
cm3[i] = comb3(i);
cm4[i] = comb4(i);
}
long long total = 0;
for(int h=1; h<=H; h++){
for(int w=1; w<=W; w++){
int v = diff[h*(W+1) + w];
if(v==0) continue;
long long term = cm3[h+2] * cm4[w+3] % MOD;
total = (total + term * (long long)v) % MOD;
}
}
if(total < 0) total += MOD;
return (int)total;
}
static int solveCrossMatrix(vector<string> mat){
int n = (int)mat.size();
const int inv2 = (MOD + 1) / 2;
// original
vector<int> ub = genUBound(mat);
vector<int> counter = genCounter(ub, n);
int contain = containPairs(ub, n);
// mirrored (to count bottom-left)
reverseEachRow(ub, n);
vector<int> counterRev = genCounter(ub, n);
// vertical flip for top-corner related counting
reverse(mat.begin(), mat.end());
vector<int> ubRev = genUBound(mat);
vector<int> sumRev = genSum(genCounter(ubRev, n), n);
// also horizontal flip => rotation 180 => top-left related
reverseEachRow(ubRev, n);
vector<int> sum = genSum(genCounter(ubRev, n), n);
int total = sum[n*n - 1]; // total #submatrices of ones (mod)
contain = submod(contain, total); // remove (R,R)
long long deviation = 0;
// count disjoint unordered pairs (with diagonal double-count)
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int down = (n - i - 2 >= 0) ? sum[(n - i - 2)*n + (n - 1)] : 0;
int right = (n - j - 2 >= 0) ? sum[(n - 1)*n + (n - j - 2)] : 0;
int rightDown = (n - i - 2 >= 0 && n - j - 2 >= 0) ? sum[(n - i - 2)*n + (n - j - 2)] : 0;
int other = right;
other = addmod(other, down);
other = submod(other, rightDown);
deviation = (deviation + 1LL * counter[i*n + j] * other) % MOD;
}
}
// subtract diagonal cases counted twice
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int c = counterRev[i*n + j];
if(c==0) continue;
if(n - i - 2 < 0 || n - j - 2 < 0) continue;
int leftUp = sumRev[(n - i - 2)*n + (n - j - 2)];
deviation = (deviation - 1LL * c * leftUp) % MOD;
}
}
if(deviation < 0) deviation += MOD;
long long res = 1LL * total * (total - 1) % MOD * inv2 % MOD; // unordered pairs
res = (res - contain - deviation) % MOD;
if(res < 0) res += MOD;
res = res * 2 % MOD; // ordered
return (int)res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> mat(n);
for(int i=0;i<n;i++) cin >> mat[i];
cout << solveCrossMatrix(mat) << "\n";
return 0;
}
HackerRank Algebra – Cross Matrix