Problem LinkAuthor: Eklavya Sharma Tester: Bhuvnesh Jain Editorialist: Eklavya Shama DifficultyEasyMedium PrerequisitesMatrix Exponentiation, Modular Arithmetic ProblemYou are given a matrix of size m by n. You have to perform w operations on it. In each operation, add to each cell the sum of its neighbors. What will be the final matrix? ExplanationWe need to do w transformations on the matrix where each transformation is of this form: A(i, j) → A(i1, j1) + A(i1, j) + A(i1, j+1) + A(i, j1) + A(i, j) + A(i, j+1) + A(i+1, j1) + A(i+1, j) + A(i+1, j+1) Here addition has to be done modulo p. In cells where i is 1 or m or where j is 1 or n, the above transformation is invalid. However, it's not difficult to find out the transformation in those cases, so we're not writing them here. We can express the above transformation as a sequence of these 2 transformations:
The first transformation is a row transformation can done by premultiplying by a matrix of size m by m. The second transformation is a column transformation can done by postmultiplying by a matrix of size n by n. Let M_{k} be a matrix of size k where M(i, j) is 1 if absolute difference between i and j is ≤ 1 and 0 otherwise. The matrix corresponding to the first transformation is M_{m} and that of the second transformation is M_{n}. After w transformations, A will become M_{m}^{w} A M_{n}^{w}. Time complexityM_{k}^{w} can be calculated in time O(log(w) * k^{3}) using fast exponentiation. Therefore total time complexity is O(log(w) * (m^{3} + n^{3})). Solution codes:asked 27 Mar '17, 00:09

@viralivora,when we do the first transformation, a(i,j)=a(i,j)+a(i1,j)+a(i+1,j) (1) a(i,j1)=a(i,j1)+a(i1,j1)+a(i+1,j1) (2) a(i,j+1)=a(i,j+1)+a(i1,j+1)+a(i+1,j+1) (3) So now when we do 2nd transformation, a(i,j)=a(i,j)+a(i,j1)+a(i,j+1)
answered 28 Feb '18, 17:12
