×

# FRCPRT - Editorial

Practice

Contest

Author: Ivan Fekete

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

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).

1. 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.
2. 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)

This question is marked "community wiki".

6★likecs
3.7k2380
accept rate: 9%

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

(30 Jul '18, 04:37) 3★

 2 Sample testcase where not applyling the first operation will lead to wrong answer:  4 4 1010 0010 1001 0100 ULRDU   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 6★likecs 3.7k●23●80 accept rate: 9%
 1 Ah good question...I was not applying S[0] :/ answered 29 Jul '18, 00:49 21●3 accept rate: 0% 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) rashomon4★ @rashomon, added. (29 Jul '18, 01:27) likecs6★ 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) likecs6★
 0 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 3★ay2306 232●9 accept rate: 11% What you have done is merely brute force. Please read editorial again. (29 Jul '18, 12:59) likecs6★
 0 Will you please explain this line "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 the number of 1 in it." answered 29 Jul '18, 17:35 78●6 accept rate: 8% In the figure above, before applying the down operation, $row[1]=3, row[2]=1, row[3]=4, row[4]=2$. This means add $1$ to column $1$ to $3$, $1$ to $1$, $1$ to $4$ and $1$ to $2$. (See, this is based on $row[i]$ values). Thus, after the operation, $col[1]=4, col[2]=3, col[3]=2, col[4]=1$. I named it as transpose because we use row to calculate columns, you can use any other name though. (29 Jul '18, 19:48) likecs6★ thanks, got it now :)) (03 Aug '18, 01:26)
 0 getting WA answer all test cases are passed whichever is comming to my mind still getting WA answer please SomeOne help me find test Cases for which my solution is giving WA answer my approach is (similar to editorialis):- check wheaters contains only L/R,if yes whatever is last, according to that will be actual answer check wheaters contains only U/D,if yes whatever is last, according to that will be actual answer if S contains both L/R AND U/D, find last L/R AND last U/D and transform solutin according to that answered 02 Aug '18, 14:15 533●1●12 accept rate: 3% plz SomeOne Help (02 Aug '18, 23:40) Holy Library wtf is that code! Did you make cases for things like RU RD LU and LD ? What are those 4 $2-D$ arrays in map doing? Also, how are you maintaining the order of operations? You know that the result of LD is not same as DL right? Input- 1 4 2 10 01 00 00 DL Your Output 00 00 10 10 Verdict: WA - This state is achieved by LD command not DL. (03 Aug '18, 01:45) 1 thanks Bro, Got AC (06 Aug '18, 23:03)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,684
×1,672
×593
×247
×81
×51

question asked: 28 Jul '18, 21:18

question was seen: 1,635 times

last updated: 03 Aug '18, 01:45