ICL1702 - Editorial

editorial
, , , ,
1

Problem Link

Practice

Contest

Author: Eklavya Sharma

Tester: Bhuvnesh Jain

Editorialist: Eklavya Shama

Difficulty

Easy-Medium

Prerequisites

Matrix Exponentiation, Modular Arithmetic

Problem

You 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?

Explanation

We need to do w transformations on the matrix where each transformation is of this form:

A(i, j) → A(i-1, j-1) + A(i-1, j) + A(i-1, j+1) + A(i, j-1) + A(i, j) + A(i, j+1) + A(i+1, j-1) + 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:

  • A(i, j) → A(i-1, j) + A(i, j) + A(i+1, j)
  • A(i, j) → A(i, j-1) + A(i, j) + A(i, j+1)

The first transformation is a row transformation can done by pre-multiplying by a matrix of size m by m.
The second transformation is a column transformation can done by post-multiplying by a matrix of size n by n.

Let Mk 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 Mm
and that of the second transformation is Mn.

After w transformations, A will become Mmw A Mnw.

Time complexity

Mkw can be calculated in time O(log(w) * k3) using fast exponentiation.

Therefore total time complexity is O(log(w) * (m3 + n3)).

Solution codes:

Setter’s solution

Tester’s solution

3 Likes
2

@admin

could you explain the above transformation?
for a[i][j],the four corners(a[i-1][j-1],a[i+1][j-1],a[i-1][j+1],a[i+1][j+1]) are missing in the transformation

3

@viralivora,when we do the first transformation,

a(i,j)=a(i,j)+a(i-1,j)+a(i+1,j) --(1)

a(i,j-1)=a(i,j-1)+a(i-1,j-1)+a(i+1,j-1) —(2)

a(i,j+1)=a(i,j+1)+a(i-1,j+1)+a(i+1,j+1) —(3)

So now when we do 2nd transformation,

a(i,j)=a(i,j)+a(i,j-1)+a(i,j+1)

  Substituting (1,2,3) u get ur requirements.
4

Thanks :slight_smile: