When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ProblemAsker's blog

By ProblemAsker, history, 4 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    Good move Bleddest, could be another one of those cheating Indian bastards.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Nice try, dude. OP is neither cheating nor Indian.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This

    it’s come from my local practice website (not english language)

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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).