×

ICL1702 - Editorial

Practice

Contest

Author: Eklavya Sharma

Tester: Bhuvnesh Jain

Editorialist: Eklavya Shama

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

139238
accept rate: 0%

19.7k350498541

 0 @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 answered 28 Feb '18, 16:41 183●8 accept rate: 14%
 0 @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.  answered 28 Feb '18, 17:12 1.6k●2●9 accept rate: 23% Thanks ^_^ (28 Feb '18, 22:11)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,492
×284
×117
×16
×2

question asked: 27 Mar '17, 00:09

question was seen: 719 times

last updated: 28 Feb '18, 22:11