Problem Link:
Author:
Vivek Gupta
Difficulty:
Easy
Pre-requisites:
Implementation
Problem Statement:
Virat Kohli is fond of matrices. He has played a total of MN matches so far and has kept record of all the scores in a score matrix of size MN. He also loves to score a perfect hundred and calls a matrix a century matrix if all its elements are 100. He wants to transform his score matrix to a century matrix of same size. To do this, he wants to perform a finite number of operations on his matrix. The single operation involves adding any integer to two adjacent cells in the matrix so as to try to convert it into century matrix. He is going to play in world cup and wants you to figure out if it is possible to transform his score matrix into century matrix.
Two cells are said to be adjacent if they share a common side.
Brief Explanation:
The transformation is possible only if the difference between the sum of even spaces and odd spaces is 0 if mn is even, and 100 if mn is odd.
Solution:
Consider the matrix as a chess board with alternate white and black spaces. Now the single operation involves adding any integer to two adjacent cells. So, with every operation, we are adding the same value of integer to one black and one white cell. So, the difference between the sum of black and sum of white blocks remains constant. Since the final matrix should be a century matrix. The difference between the black and white ones should be 100 if both m and n are odd, and 0 if either of m and n is even. So, the input matrix should also have the same difference.
Here is the C++ code for the above implementation: