CodeChef March Challenge 2021 — Consecutive Addition

“You are given two matrices A and B, each with R rows (numbered 1 through R) and C columns (numbered 1 through C). Let’s denote an element of A or B in row i and column j by A(i,j) or B(i,j) respectively…..”

You can read the whole problem here.

Problem description in short

Given two matrices, A and B. Task is to transform A to B using special some addition-based criteria. The criteria for transformation is as follows

• we are given a number K
• 2 ≤ K ≤ min(R, C), where R is row size and C is column size
• we have to take any submatrix of size Kx1 (i.e. along the column) or 1xK (i.e. along the row), in A, and to all the numbers that fall under that submatrix have, add some integer v, this can be chosen by us.
• This has to be done in such a way that finally A transforms to B.

The actual problem is to check if this kind of transformation is possible, given A and B.

Ideation….

Before I begin I wanna say that it is an observation based problem, can have many solutions and my solution is not perfect in any sense, it just that it came to me that way. Your solutions are welcomed in the comment box and will be certainly appreciated if are really cool by the audience.

Let’s Begin….

Hmm… the transformation is based on the addition of a value to every individual element of the matrix A, this hints that we don’t care about what A and B are, rather compute D = B-A and try to make all the elements of D = 0.
When D = 0, matrix A will be equal to matrix B.

Now to check if it is possible to make all elements of D equal to 0 using the given transformation criteria we have the following observations

• Every element of sub-row or sub-column of size K is dependent on one another. As if we subtract some value from an element then that value has to be subtracted from all the elements under that sub-matrix.
• If we say that D = 0 is the last stage, then at the stage just previous to that, only a K size sub-column or sub-row must have the same value, and the rest elements must be 0.
• Tracking back this way we can say that corner elements must be filled by at most 2 different types of numbers (as only 2 arrays can be overlapped by these elements)
• Every cell value must be the sum of at most p different values if p different arrays pass through it.

Huh.. a lot of observations and a lot of headaches it gave me.

Starting from the problem again, making D = 0.

Suppose obtained D matrix is like this

D Matrix

Let us start with K = 2.
K = 2, means that every adjacent element must have a value in common.

Observe that blue boxes have a in common and green boxes have j in common

Clearly, on comparing the matrices we can say that values of P,Q,R… (matrix D) must be such that a + b = P, a + b + d = Q, … etc.

Since the first cell is made up of 2 values a, b and we have only one equation we can start by assuming a = 1, which makes b = P — 1.

Similarly, in the next cell we have a = 1 already, lets assume c = 2 then D = Q — 3. And for cell D(1, 0), b = P -1 already we have, lets assume g = 1, then h = W — (P — 1) — 1 = W — P.

So in for all cells, by using already set values and assuming values for variables until only one unset value is left in the cell we can find the expression for each of the variables (a, b,c,d….) in form of P,Q,R,S…..(matrix D, cell values).

When we complete this process we will obtain the final expression to be like this.

P - Q + R - S +T - U +V - W + X - Y +Z - F - G + H - I + J = 0

This happens because the total number of variables ≥ total number of equations, so some variable will have values in 2 forms which have to be equated. You can notice this by manually calculating the values of the variables.

On plotting the signs on the matrix we get,

For K = 2 we have a solution now, ie. obtain D = B - A. Then alternatingly make the coefficients of D as 1 and -1.

Observations we make from this solution is

• The conclusion here is we can see that we can check if it is possible to make D = 0, just by multiplying each element of D by a separate coefficient and checking the sum of the values. Let’s call this matrix the coefficient matrix.
• All the coefficients are in a way of balancing the matrix. Balancing in a sense that taking +D(0,0) -D(0,1) actually balances a that was present in both the cells, initially.

Now the problem is how to find this coefficient matrix for any K?

Suppose, we take a K sized row from the matrix.

Every element of this array is made up of 2 kinds of values, common part and uncommon part. By common part, I mean some x that is present in all the elements of this array.

If we add all the elements of this array obtained, the common part in the values of these elements gets added K times. Rather than this, if we add first (K — 1) elements and subtract the last element (K- 1) times, all the common part contained in this part is balanced, i.e. becomes = 0. Let's call this array [1,1,1, …., -(k-1)] as balancing array. We can also say any permutation of this balancing array is also a balancing array.

Balancing array for K = 3

By multiplying respective elements of the taken array to the elements of the balancing array we can eliminate the common part in the array.

This balancing array can be used to find the coefficient matrix we were looking for. For our coefficient matrix, every subarray of size K (along a row or a column) must be a permutation of this balancing array, as permutations of this balancing array are also balancing arrays. A sample such coefficient matrix can be as follows: -

Coefficient Matrix for K = 3

As our full coefficient matrix is actually balancing the values both column-wise and row-wise, the sum of multiplying elements by respective coefficients must give zero. Hence Summation[C(i,j)*D(i,j)] = 0.

This can be used as a sufficient condition to check if it is possible to make all the elements of D = 0. If it’s possible then the answer is yes else no.

That’s it. We have found a solution. You can stop here.

Further, this can be improvised by observing the sample coefficient matrix I used, that the coefficient of elements with the sum of the indices (i + j) equal to (k — 1) is -(k-1); rest of all elements, the coefficient is 1.

Finally, done. After so many observations and investing so much time. I think that’s why it is a Long Challenge. The beauty is that the solution is quite short. Wrong!!!???!!

The twist is the code discussed above seems to work but won't work. But why? It's a simple idea but missing some observation. The problem is with the array we are building the coefficient matrix.

Our Coefficient Matrix approves that the given matrix is also balanced but it is clearly not.

The reason for such misbehaviour is due to some elements being zero and the rest elements being balanced using coefficients. This can be handled easily by shifting the elements by some value such that each value > 0. And finally, count for additional value added to the whole matrix.

Building upon the same coefficient idea, another sample coefficient matrix can be this.

Here (K-1)x(K-1) matrix has a simple property that can be observed if we draw a 4x4 matrix also

But if you notice the sum of the submatrix highlighted is also the same as the corner element. This is true for all corners. Hence this submatrix can balance the corner residue if exists in some cases. 

New Observation! Diagonally no relation should exist in the matrix.

Here is a working solution for the same idea. Have a look at how the coefficient matrix is built. 

Observe that for C(i,j) = (i+1)*(j+1) for (K-1)x(K-1) matrix. The Kth Row and Kth Column have addition balancing.

This follows all the rules that are mentioned in our observation list.

And yes the solution is Done!!