A quick way to model matrix operations

Question

This is from the old problem of the practice of the Olympiad:

Imagine that you have a 1000x1000 grid in which cell (i, j) contains the number i * j. (Rows and columns are numbered starting with 1.)

At each step, we build a new grid from the old one, in which each cell (i, j) contains a "neighborhood average" (i, j) in the last grid. "Average average" is defined as the floor of the average values ​​of the cell and its up to 8 neighbors. So, for example, if the 4 digits in the corner of the grid were 1,2,5,7, in the next step the angle would be calculated as (1 + 2 + 5 + 7) / 4 = 3.

In the end, we will reach the point where all numbers coincide, and the grid no longer changes. The goal is to find out how many steps are required to achieve this goal.

I tried just to simulate it, but it does not work, because it seems that the answer is O (n ^ 2) steps, and each simulation step takes O (n ^ 2) for processing, resulting in O (n ^ 4) which is too small for n = 1000.

Is there a faster way to do this?

Answer 1

The gender step makes me suspect that an analytical solution is unlikely, and that this is actually a micro-optimization exercise. Here is my idea.

Let angles and edges be ignored for a moment. There are a total of 3996, and in any case they need special treatment.

For the inner cell, you need to add 9 elements to get the next state. But turn it around and say: each inner cell should be part of 8 additions.

? A[i], B[i] C[i] :

A'[i] = A[i-1] + A[i] + A[i+1]
B'[i] = B[i-1] + B[i] + B[i+1]
C'[i] = C[i-1] + C[i] + C[i+1]

( , " ", A'[i+1] = A'[i] - A[i-1] + A[i+1]. , .)

, B[j], A'[j] + B'[j] + C'[j].

; .

, B, A' :

D'[i] = D[i-1] + D[i] + D[i+1]

... B' C' C B' C'. ( , B' C', A' B', ... . , .)

, B, , B' 2n, B, 2n, / .

, C' B , .

, . SIMD ...

Answer 2

:

, (x, y), x * y.

, 1- :

V1 = (  xy    +    x(y+1)   +   x(y-1)
    +(x+1)y  + (x+1)(y+1)  + (x+1)(y-1)
    +(x-1)y  + (x-1)(y+1)  + (x-1)(y-1)
     ) / 9
   = xy

( )

v2 = ( xy  + (x-1)y + (x+1)y + x(y+1) + (x-1)(y+1) + (x+1)(y+1) ) / 6
   = xy + x/2.

( )

v3 = ( xy  + (x-1)y + (x+1)y + x(y-1) + (x-1)(y-1) + (x+1)(y-1) ) / 6
   = xy - x/2.

.

, 1- , .

.

, - , N/2 . :, , IMO, .

, , :

, N/2 .

, , , - .

, incremental N/2 , N .

Answer 3

, , symmetric, .. m [i] [j] = m [j ][]. m [i] [j] , m [j] [i], .

This optimization reduces the number of computations per grid from N^2to ((N^2)+N)/2.