You are not logged in. Please login at www.codechef.com to post your questions!

×

ICL1702 - Editorial

3
4

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

asked 27 Mar '17, 00:09

sharmaeklavya2's gravatar image

5★sharmaeklavya2
139238
accept rate: 0%

edited 28 Mar '17, 16:22

admin's gravatar image

0★admin ♦♦
19.6k349497539


@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

link

answered 28 Feb, 16:41

viralivora's gravatar image

4★viralivora
1838
accept rate: 14%

@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.
link

answered 28 Feb, 17:12

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

Thanks ^_^

(28 Feb, 22:11) viralivora4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,116
×260
×93
×16
×2

question asked: 27 Mar '17, 00:09

question was seen: 692 times

last updated: 28 Feb, 22:11