Stones falling

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in companies
MicrosoftAppleGoldman Sachs

Problem statement

This time Ninja has a 'GRID' of size 'N' x 'M' of binary values (0s and 1s) the 1s in a cell represent the stones. A stone will not fall when that satisfies 2 conditions:

1) It is directly connected to the top of the grid

2) At least one of its adjacent (top,bottom,left, right) stones will not fall.

Ninja has 'R' sequence of locations of stones (given in a matrix 'REM' of size 'R' X 2). In each case, he wants to remove the stone placed at (i, j) place but due to this action, some other stones will also fall. So he needs your help to find the number of stones that fall after each removal in sequence.

Return an array of size 'R' denoting the number of stones that fall after each removal of a stone.

Note:

Sometimes a removal may refer to a location with no stone, in that case, no stone fall.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains three space-separated integers, 'N', 'M' and ‘R’, denoting the number of rows and columns in the matrix 'GRID’', respectively and ‘R’, denoting the number of the location he has to remove.

Each of the next 'N' lines contains 'M' space-separated integers(0s or 1s) denoting the matrix ‘GRID' elements.

Next ‘R’ lines contain 2 integers denoting the removal of stone placed at ( i, j ) position in the 'GRID'.
Output Format : 
For each test case, print a single line containing space-separated integers denoting the number of stones that fall after each removal of a stone.

The output for each test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N, M <= 200
1 <= R <= N * M   

Where ‘T’ is the number of test cases, ‘N’ and ‘M’ is the number of rows and columns respectively and ‘R’ is the number of removal operations.

Time limit: 1 sec.

Sample Input 1:

2
3 3 1
1 1 0 
1 0 0
1 1 1
1 0
2 3 2
1 1 1
1 0 1
0 0
1 2

Sample Output 1:

3
1 0

Explanation of Sample Output 1:

Test Case 1 : On removing stone at (1, 0) all the stones below it i.e. (2, 0), (2, 1), (2, 2) will fall.
Hence, the answer is 3 

Test Case 2:  Here we have two locations to remove.
First is (0, 0), on removing this, stone present at (1, 0) will fall so the answer for this location is 1.
In the second location, there is no stone available so we return 0.

Sample Input 2:

1
3 3 2
1 0 1
0 1 1
0 1 0
1 2
1 1

Sample Output 2:

2 0
Hint

Try to think in the reverse direction using DSU(disjoint set union). 

Approaches (1)
DSU

The idea here is to use disjoint set union (DSU) to solve this problem.

DSU is data structure provides the following capabilities. We are given several elements, each of which is a separate set. A DSU will have an operation to combine any two sets, and it will be able to tell in which set a specific element is.

First, we will be going to remove all the stones that are given in the removal array and then one by one we add those stones in the grid back but before adding the stones back we make different sets where each set represents all the connected stones.

Then we iterate the removal array from reverse and whenever we find a stone, we connect all the adjacent stones (set will be connected) and we are also storing the size as the sets get connected.

And if a set is connected to another set that already has a stone that is connected to the top then we add this value to the result.

 

Algorithm:

  • To implement DSU easily we first need to convert our 2d matrix in 1 dimension based indexing we will be using (i * M + j) for (i, j)th cell in the grid(row-based indexing) .
  • We will be using a typical DSU structure with some little modification.
  • Declare an array ‘parent’ of size (N * M + 1) and initialise it with its index value, as initially, we are supposing all cell are independent and are not connected.
  • Now, iterate in the removal array and  for each index (i, j) assign 0 to grid[i][j].
  • After this we will union all set that are connected to each other.
  • To do this task we will run 2 nested loops
    • for(i = 0 -> N)
      • for(j = 0 -> M)
      • if(grid[i][j] == 1) then union_set(‘dsuIndex’,’childIndex’)
        • Where ‘dsuIndex’  = i * M + N and similarly we calculate its ‘childIndex’
  • Now, we have all the connected stones in one set which is represented by a unique number.
  • After this, iterate the removal array from reverse and for each position if there exists one in the grid then we will connect the sets of all its adjacent cells.
  • To calculate the number of fallen stones we also need to declare an isTop() that will return whether this set has any stone that is connected to the top or not .
  • Then with the help of this function, we will check which set is connected to the top and all other sets which are not connected to the top will be added to ans.
  • If a position doesn’t have any set with isTop() == 1 then no stones will fall on the removal of this and Hence answer will be 0 for this case.

Description of union_set( int a, int b)

  • This will first find the set in which ‘a’ and ‘b’ belong using find_set()
  • Then if(a ! = b)
    • We make parent[b] = a
    • And size[a] += size[b]
    • Istop[a] = istop[a] or istop[b]

Description of Find_set(int v)

  • First we check if parent[v] == v then return ‘v’
  • Else
  • Return parent[v] = find_set(parent[v])
Time Complexity

O(N * M * R * ⍺(N * M * R) ), where ‘N’ and ‘M’ is the number of rows and columns resp. And ‘R’ is the size of the removal array and ‘⍺’ is the Inverse-Ackermann function.

 

In the worst-case scenario, when all the cell values are 1 then we need to call unionSet on all cells which results in this O(N * M * R * ⍺(N * M * R) ) time complexity.

Space Complexity

O(N * M), where ‘N’ and ‘M’ are the rows and columns of the grid.

 

As we are storing the parent array whose space complexity is O(N * M). 

Code Solution
(100% EXP penalty)
Stones falling
Full screen
Console