FRCPRT - Editorial

Problem Link

Practice

Contest

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

  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)

2 Likes

Ah good question…I was not applying S[0] :confused:

2 Likes

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.

3 Likes

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.

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

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

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 solution link
gfg link for testing on different test casese


my approach is (similar to editorialis):-

  1. check wheaters contains only L/R,if
    yes whatever is last, according to
    that will be actual answer

  2. check wheaters contains only U/D,if
    yes whatever is last, according to
    that will be actual answer

  3. if S
    contains both L/R AND U/D, find last
    L/R AND last U/D and transform
    solutin according to that

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?

3 Likes

@rashomon, added.

Updated my solution link on ideone to contain this test case and its answer as well for you to see the difference.

What you have done is merely brute force. Please read editorial again.

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

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.

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

@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++.

@adcoder use faster input/output

plz SomeOne Help

thanks, got it now :))

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.

thanks Bro, Got AC

1 Like