Problem LinkAuthor: Ivan Fekete Tester: Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyEASYMEDIUM PrerequisitesLooping Techniques, Observations ProblemYou 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. ExplanationFor 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).
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)
This question is marked "community wiki".
asked 28 Jul '18, 21:18

Sample testcase where not applyling the first operation will lead to wrong answer:
The idea was to first make all the cells with $1$ to a corner and then apply the properties as they now move in a constraints manner, which is not the case in the initial matrix. You might miss the transpose operation which I mentioned in the editorial. See how the answer is shifted from row to column as in updated solution link on ideone in the editorial. Hope everything is clear now. answered 29 Jul '18, 01:27

Ah good question...I was not applying S[0] :/ answered 29 Jul '18, 00:49
2
Why is it necessary to apply S[0]? Is there an example of a test case which fails if you only consider the last {L, R} and {U, D} move in order?
(29 Jul '18, 01:16)
@rashomon, added.
(29 Jul '18, 01:27)
Updated my solution link on ideone to contain this test case and its answer as well for you to see the difference.
(29 Jul '18, 01:29)

I need help in optimizing my code for subtask 2. Can you please look at my submission. Please also comment on how can I make my code more readable so that other programmers helping me having minimal of trouble. PS: I know the editorial is there but I am having trouble understanding how optimizing it Thank you. answered 29 Jul '18, 04:05

I got TLE even with O(3NM + 2*S) in java. I suspect the time limit is not suitable for java Has anyone got 100% AC in java for this problem? My solution > https://www.codechef.com/viewsolution/19376907 answered 29 Jul '18, 10:51
@adcoder, Please give link to your code instead of copy pasting it here. Also, you may filter accepted submission based on language. For example, @uwi got this problem accepted in java.
(29 Jul '18, 13:01)
@adcoder maybe try with faster input/output as your code looks completely fine(logic is correct and complexity wise correct too). The input file size is large. I also suggest you to try your logic in C++.
(30 Jul '18, 23:16)
@adcoder use faster input/output
(02 Aug '18, 10:49)

getting WA answer my solution link my approach is (similar to editorialis):
answered 02 Aug '18, 14:15
plz SomeOne Help
(02 Aug '18, 23:40)
Holy Library wtf is that code! Did you make cases for things like What are those 4 $2D$ arrays in map doing? Also, how are you maintaining the order of operations? You know that the result of
(03 Aug '18, 01:45)
1
thanks Bro, Got AC
(06 Aug '18, 23:03)

I don't think that the order of the last left/right and the last up/down operations matters.