Problem Link
Author: Ivan Fekete
Tester: Misha Chorniy
Editorialist: Bhuvnesh Jain
Difficulty
EASY-MEDIUM
Prerequisites
Looping Techniques, Observations
Problem
You are given a matrix A of size (N, M) consisting of 0 and 1. We apply forces on the matrix according to a given string S. On applying the force on left, right, up or down direction, the cells with 1 move in the required direction till they either reach the end of the matrix or find another 1 lying directly adjacent to them.
Find the final configuration of the matrix.
Explanation
For the first subtask, just applying the operations as mentioned in the statement will be enough. For applying force to right or left, we just need to find how many 1 are present in a row and then shift them all right or left respectively. Similarly, for applying the force to up or down, we just need to find how many 1 are present in a column and then shift them all up or down respectively.
The time complexity of this approach will be O(N * M * |S|) per test case. For proceeding towards the final solution, let us make some observations.
Let us apply the first operation, i.e. S[0]. After this, all the cells shift to one side/corner of the matrix. It is clear that up and down operations affect cells in the column direction while left and right operations affect cells in the row direction. Thus, we can take a look at their properties together.
Now, let us consider sequences of operations consisting of up(U) and down(D) operations only. (The similar result applies to left and right moves as well).
- UUUU… or DDDD…: It is sufficient to apply the operation only once as the future operations have no effect on the configuration of the matrix.
- UDUD… or DUDU…: It is sufficient to apply the last operation only as it will affect the final configuration, the previous one has no effect as it will be overridden by future operations.
Now, let us consider what happens when we apply both operations together. The first thing to note that the first operation is applied always. This is because now 2 adjacent cells in the row will move together and 2 adjacent cells in the column will move together. This is not the case if the first operation is not applied as the cell with 1 can move arbitrary steps in either direction due to the presence of 0 in adjacent cells.
When we apply a left or right operation after up or down operation, the number of cells in row shift towards columns. To understand this, consider the movement of cells in below matrix on applying down operation:
 We can consider the above operation as transpose operation where for each row add 1 to all column from 1 to row[i] where row[i] denotes number of 1 in it. Thus, instead of explicitly setting the cells to 0 and 1 as in brute force solution, we can just maintain the number of 1 in each row and column.
Once, you get an idea of the above logic you can see editorialist solution below for more details. The complexity is now O(|S| * (N + M)). This is better than the previous solution but still not sufficient to pass full solution. (Note that in the solution the transpose_row or transpose_col does the addition in a range and calculating the final array.)
Now, once you see the solution above, you can clearly see that we apply transpose operations only one by one. Using this, we get the idea that again only the last operations for left/right and up/down matter as the transpose operation done 2 times leads us to the same state.
So, the final solution is just to apply the first operation and then apply the last left/right operation and up/down operation in order. Thus, the length of the string S can be effectively reduced to atmost 3. Now we just apply the brute operations.
The complexity of the above algorithm is O(|S| + N * M). The first one is for traversing the string |S| for determining the 3 important operations and the last one is for applying the operations.
Once, you are clear with the above idea, you can see the author implementation below for help.
Feel free to share your approach, if it was somewhat different.
Time Complexity
O(N * M + |S|) per test case.
Space Complexity
O(N * M + |S|)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here. (Will give TLE for subtask 2)
