Find the number of rectangles of same color in a matrix

Правка en6, от one_autum_leaf, 2023-10-28 10:11:54

Question:

You have a $$$N * M$$$ matrix. The color of cell in $$$i^{th}$$$ row and $$$j^{th}$$$ column is $$$a_{ij}$$$. Find the number of rectangles that can be formed from this matrix by deleting some rows and columns, that have all cells of same color.

Idea:

Let $$$i_l, j_l$$$ be the coordinates of the top left corner and $$$i_r, j_r$$$ be the coordinates of the bottom right corner. We can see that $$$(i_l, j_l, i_r, j_r)$$$ uniquely define a rectangle.

Let's call a rectangle valid if it has all cells of same color.

Now let $$$dp[i][j]$$$ be the number of valid rectangles with their bottom right corner at $$$(i, j)$$$.

Let $$$h[i][j]$$$ be the "height" of columns at $$$(i, j)$$$. That is

$$$h[i][j]$$$ = max value of $$$len$$$ such that $$$a[i][j] = a[i][t]$$$ , for all $$$t = i - len + 1, i - len + 2, ..., i$$$.

How do we computer $$$dp[i][j]$$$ efficiently ?

Consider how $$$dp[i][j]$$$ depends on $$$dp[i-1][j], dp[i - 2][j], ...$$$.

For some $$$k, k < j$$$, if $$$a[i][k] != a[i][j]$$$, then $$$dp[i][k]$$$ will make no contribution to $$$dp[i][j]$$$. So let's assume that $$$a[i][t] = a[i][j]$$$ for all $$$t = k, k + 1, ..., j$$$.

Now what is the maximum height of rectangle with bottom right corner at $$$(i, j)$$$ and top left corner in the column $$$k$$$ ?

It is $$$height_k = min_{k \le t \le i}(h[i][t])$$$. Then then the number of such rectangles is $$$height_k$$$, since we can have rectangles of height $$$1, 2, 3, ..., height_k$$$.

Also consider that if $$$h[i][k] \le height_k$$$, then for any rectangle with bottom right corner at $$$(i, k)$$$ can be extended so that it has bottom right corner at $$$(i, j)$$$.

Let $$$k$$$ be the first index such that $$$a[i][k] = a[i][j]$$$ and $$$h[i][k] < h[i][j]$$$.

Then every rectangle with bottom right corner at $$$(i, k)$$$ can be extended to $$$(i, j)$$$. Also the height of any rectangle with top-left corner after $$$(i, k)$$$ is at most $$$h[i][j]$$$, since by definition for any $$$t, k < t \le i$$$ we have $$$h[i][t] \ge h[i][j]$$$.

Thus the number of rectangles after k are $$$h[i][j] * (j - k)$$$.

Thus we have, $$$dp[i][j] = dp[i][k] + h[i][j] * (j - k)$$$.

Now the question is how do we efficiently find $$$k$$$ ?

We can do this by maintaining an array of indices $$$col$$$ such that $$$h[i][col] \lt min_{col \le t \le j}(h[i][t])$$$.

Time Complexity : $$$O(N * M)$$$


vector<vector<ll>> get_number_of_rectangles(vector<vector<int>> &a, int n, int m){ vector<vector<ll>> dp(n, vector<ll>(m)); vector<vector<ll>> h(n, vector<ll>(m, 1)); for(int i = 1; i < n; ++i){ for(int j = 0; j < m; ++j){ if(a[i - 1][j] == a[i][j]){ h[i][j] += h[i - 1][j]; } } } for(int i = 0; i < n; ++i){ vector<int> indices; for(int j = 0; j < m; ++j){ int k = -1; while(!indices.empty()){ int col = indices.back(); if((a[i][col] != a[i][j]) || (h[i][col] < h[i][j])){ break; } indices.pop_back(); } if(!indices.empty()){ k = indices.back(); } dp[i][j] += h[i][j] * (j - k); if(k != -1){ if(a[i][k] == a[i][j]){ dp[i][j] += dp[i][k]; } } indices.push_back(j); } } return dp; } void solve() { int n, m; cin >> n >> m; vector<vector<int>> a(n, vector<int>(m)); for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ cin >> a[i][j]; } } vector<vector<ll>> dp = get_number_of_rectangles(a, n, m); ll ans = 0; for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ ans += dp[i][j]; } } cout << ans << '\n'; }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский one_autum_leaf 2023-10-29 19:29:05 61
en6 Английский one_autum_leaf 2023-10-28 10:11:54 57 Tiny change: '$k$ ? \n\nIt is ' -> '$k$ ? \n\n![ ](https://i.imgur.com/1qew4HO.png)\n\nIt is ' (published)
en5 Английский one_autum_leaf 2023-10-28 10:06:24 1625 Tiny change: 'imgur.com/w4jes7x.png)\n\n' -> 'imgur.com/QxCbwLp.png)\n\n'
en4 Английский one_autum_leaf 2023-10-28 09:45:05 846 Tiny change: 'color.\n\nIdea:\' -> 'color.\n\n![ ](https://imgur.com/a/QK6lnrD)\n\nIdea:\'
en3 Английский one_autum_leaf 2023-10-28 09:20:17 1462 Tiny change: ' a[i][t]$ \n\nfor all $t' -> ' a[i][t]$ , for all $t'
en2 Английский one_autum_leaf 2023-10-28 07:37:39 7 Tiny change: 'column is a^ij.' -> 'column is \a^ij.'
en1 Английский one_autum_leaf 2023-10-28 07:35:17 143 Initial revision (saved to drafts)