PROBLEM LINK:
Setter: Vipul sharma
Tester: Lewin Gan and Istvan Nagy
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium
PREREQUISITES:
Implementation
PROBLEM:
Given the initial and final state of a 3*3 matrix, we are told that N operations are applied to the initial matrix to reach the final matrix. Out of these, N-1 operations are given in the statement. We are to find the number of ways we can insert N operation at any position in the sequence of operations so that after applying all operations on the initial matrix, we obtain the final matrix.
An operation can be either a row operation or column operation, left shift or right shift (top or bottom shift in case of column operation), with one or two steps, to be applied on any of the three rows (or columns).
QUICK EXPLANATION
- Try each valid position for the Nth operation: Before the first operation, between any two operations or after the last operation. The final number of operations is just the sum of the number of ways for each position.
- To try for position say between the xth and (x+1)th position, we can apply first x operations on the initial matrix and remove the effect of last to (x+1)th operation on the final matrix in reverse. (By reversing the direction of shift). Then try applying all possible operations on the first matrix to see if it yields the second matrix. If yes, we have found another way to choose Nth operation.
EXPLANATION
This problem is all about implementation. I’ll explain its idea by using another problem.
Suppose we have two integers A and B. We are to apply N operations on A to obtain B, one of which is missing. Operations are Add a number x or subtract a number x. We are to find out the number of ways to place that operation in the sequence of operations such that after applying all N operations on A, we obtain B.
If X_i denote ith operation (positive for addition, negative for subtraction), and if we have all operations, B = (B-X_N)+X_N. So, B-X_N is the value before applying the nth operation. Again, B-X_N - X_{N-1} is the value before applying the last two operations. Idea is, to reverse the effect of addition using subtraction.
Similarly, in our problem, we are going to use reverse the effect of operations from the final matrix. Suppose we are checking if the missing operation is the first operation. So, for that, we need to remove the effect of all N-1 operations in reverse order from the final matrix, to obtain matrix just after the missing operation. Operations here can be reversed by reversing the direction, or by noticing that shifting by three values in any row (or column) doesn’t make a change at all.
After obtaining the before and after matrix for the missing operation, we try to apply all possible operations on both rows and columns one by one and check which ones when applied on before matrix, results in after matrix. We just need to take the sum of that for all possible positions of missing operation.
The important point about implementation would be to make a separate function to apply any possible operation, as we have to apply and remove the effect of operation a number of times in this problem.
Rest is all implementation and can be referred from the following codes.
Time Complexity
Time complexity is of the order O(N*3*3*C), C is the constant factor due to applying operations.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 