There are n*m matrix (n,m<=1000) each element in the matrix are between 1 and 1e9 Count number of all rectangle in matrix that contain all the same element
how to solve this? I have been thinking for 2 days. Thank you very much.
Example:
Input:
2 3
1 1 2
1 1 2
output : 12
Try to do it like this: fix two horizontal lines and count the number of rectangles, opposite sides of which lie exactly on these lines. It will be O(n^3) but with good constant.
I believe I have a reasonable (in terms of time complexity) solution, but you have to provide the link to problem so everyone is sure that it's not from an ongoing contest.
Good move Bleddest, could be another one of those cheating Indian bastards.
Nice try, dude. OP is neither cheating nor Indian.
This
it’s come from my local practice website (not english language)
I think I have something like $$$O(n^2 \alpha(n))$$$, where $$$\alpha(n)$$$ is the inverse Ackerman function.
First of all, for each element, find the closest element to the right of it that is different from it. It can be done in $$$O(n^2)$$$ as follows: if $$$a[i][j] \ne a[i][j + 1]$$$, then $$$j + 1$$$ is the answer for $$$a[i][j]$$$ (we will have to store the column index for that closest element); otherwise, if $$$a[i][j] = a[i][j + 1]$$$, then the answer for $$$a[i][j]$$$ is the answer for $$$a[i][j + 1]$$$. We will need that information later.
Okay. Now, let's fix the left border of our rectangle (let it be $$$l$$$), iterate on the right border (let it be $$$r$$$), and calculate the number of rectangles meeting our constraints that have left border in $$$l$$$ and right border in $$$r$$$. Let's analyze when some row $$$i$$$ can appear in the subrectangle we are interested in. If the elements from $$$l$$$-th to $$$r$$$-th in that row are not all the same, then this row is clearly bad and cannot be used — otherwise, it can be used. The trick is that, if we look at the next different element for $$$a[i][l]$$$, its column index is equal to the first value of $$$r$$$ when our row becomes bad.
When analyzing the good rows, if there are $$$k$$$ adjacent good rows having the same number in $$$a[i][l]$$$, they add $$$\frac{k(k+1)}{2}$$$ to the answer. We can maintain these "components" of good rows as follows: initialize a DSU and start iterating on $$$r$$$ from the maximum possible value to the minimum possible. For each row, we know the moment when it becomes good — and, using something like sweep line approach, we may shift $$$r$$$ to the left, and if some row becomes good, create a component for it in DSU and try to merge it with the components for adjacent rows (if they are good).
An english version of the problem in Gym. here.