Matrix Illumination

Hard
0/120
Average time to solve is 45m
profile
Contributed by
0 upvote
Asked in companies
IntuitShareChatYourdrop

Problem statement

A 2-D matrix ‘MAT’ of size ‘N’ * ‘N’ is present, where each cell consists of a bulb. Initially, all bulbs are turned OFF. You are given a 2-D array ‘BULB’ of size ‘M’, where ‘BULB[i]’ = [‘ROW’, ‘COL’] indicates that the bulb is turned ON at position [‘ROW’, ‘COL’]. When a bulb is turned ON, it illuminates its cell and illuminates the cells present in the same row, column, or diagonal.

You are also given another 2-D array, ‘QUERY’, where ‘QUERY[i]’ = [‘ROW’, ‘COL’]. For each query, print ‘1’ if the ‘MAT[ROW][COL]’ is illuminated, else print 0. After answering a query, you have to turn OFF the bulb at ‘MAT[ROW][COL]’ and its 8 adjacent bulbs if they exist. A bulb is adjacent if it shares either a side or corner with ‘MAT[ROW][COL]’.

Note: There can be repeated values present in the ‘BULB’ array. If the same value is repeated in the ‘BULB’ array, the ‘BULB’ remains on.

For example: 
Initially, let ‘MAT’ be : 
0 0 0
0 0 0
0 0 0
Let the ‘BULB’ array be: [[0, 0]]

‘MAT’ will be changed to :
‘1’ 1 1
1 1 0
1 0 1    where (1 represents the cell is illuminated and ‘1’ represents the cell is illuminated and the bulb is turned ON).

Let ‘QUERY’ array be : [[0, 1]]
As the cell [0, 1] is illuminated, we will print 1 and then turn OFF the bulb at that position and adjacent to it.

‘MAT’ will be changed to :
0 0 0
0 0 0
0 0 0
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’, ‘M’, and ‘Q’, representing the size of the matrix, the size of the ‘BULB’ array, and the size of the ‘QUERY’ array.

The next ‘M’  lines of each test case contain two space-separated integers representing the ‘BULB’ array elements.

The next ‘Q’  lines of each test case contain two space-separated integers representing the ‘QUERY’ array elements.
Output Format : 
For each test case, print the result of queries in 0 and 1, where 0 represents the cell is not illuminated, and 1 represents the cell is illuminated.

Print output of each test case 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 <= 10
1 <= M, N, Q <= 2*10^4
0 <= BULB[i][0], BULB[i][1], QUERY[i][0], QUERY[i][1] < N    

Time Limit: 1 sec
Sample Input 1 :
2
3 1 1
0 0
0 1
4 2 2
0 0
3 3
1 1
1 0
Sample Output 1 :
1
1 0
Explanation For Sample Input 1 :
For test case 1: 
Initially, the ‘MAT’ will be : 
0 0 0
0 0 0
0 0 0

After turning ON, bulbs present in the ‘BULB’ array, ‘MAT’ will be changed to :
‘1’ 1 1
1 1 0
1 0 1    where (1 represents the cell is illuminated and ‘1’ represents the cell is illuminated and the bulb is turned ON).

Performing ‘QUERY’ 1:
As the cell [0, 1] is illuminated, we will print 1 and then turn OFF the bulb at that position and adjacent to it.

‘MAT’ will be changed to :
0 0 0
0 0 0
0 0 0

So the result is [1].

For test case 2: 
Initially, the ‘MAT’ will be : 
0 0 0 0
0 0 0 0 
0 0 0 0
0 0 0 0 

After turning ON, bulbs present in the ‘BULB’ array, ‘MAT’ will be changed to :
‘1’ 1 1 1
1 1 0 1
1 0 1 1
1 1 1 ‘1’   where (1 represents the cell is illuminated and ‘1’ represents the cell is illuminated as well as the bulb is turned ON).

Performing ‘QUERY’ 1:
As the cell [1, 1] is illuminated, we will print 1 and then turn OFF the bulb at that position and adjacent to it.

‘MAT’ will be changed to :
1 0 0 1
0 1 0 1
0 0 1 1
1 1 1 ‘1’

Performing ‘QUERY’ 2:
As the cell [1, 0] is not illuminated, we will print 0.

So the result is [1, 0].
Sample Input 2 :
2
5 2 2
0 0
4 4
1 1
1 1
5 2 3
0 0
0 4
0 4
0 1 
1 4
Sample Output 2 :
1 1
1 1 0
Hint

Try to check in all directions from which a cell can be illuminated for each query.

Approaches (2)
Brute Force

The basic idea is to simply check every row, column, and diagonal from which a cell can be illuminated for each query. For each cell, there can be 1 row, 1 column,  and four diagonals from which it can be illuminated. So we simply check whether a bulb is ON or not in these. We use a set to store the positions of the bulbs that are already ON.

 

Here is the algorithm :

 

  1. Create a set (say, ‘S’) to store the bulbs which are turned ON.
  2. Run a loop from 0 to ‘M’ (say, iterator ‘i’) to traverse the ‘BULB’ array.
    • Insert the current position in the set.
  3. Create an array (say, ‘ANS’) to store the result.
  4. Run a loop from 0 to ‘Q’ (say, iterator ‘i’) to run each query.
    • Call the function CHECK that will tell whether the current cell can be illuminated or not.
    • If the current cell can be illuminated
      • Push 1 in ‘ANS’.
      • Remove the bulbs from the set that are ON and adjacent to the current cell.
    • Else,
      • Push 0 in ‘ANS’.
  5. Return ‘ANS’.
     

CHECK(‘N’, ‘S’, ‘R’, ‘C’)   (where ‘N’ is the size of the matrix, ‘S’ is the set that consists of positions where the bulb is ON, ‘R’ and ‘C’ is the position of the current query).

 

  1. Run a loop from 0 to ‘N’ (say, iterator ‘i’)
    • Check if position [‘R’, ‘i’] is present in the set.
      • Return TRUE.
  2. Run a loop from 0 to ‘N’ (say, iterator ‘i’)
    • Check if position [‘i’, ‘C’] is present in the set.
      • Return TRUE.
  3. Create two variables (say, ‘diagR’ and ‘diagC’) to traverse the diagonals.
  4. Run a loop till ‘diagR’ and ‘diagC’ are greater than equal to 0.
    • Check if position [‘digaR’, ‘diagC’] is present in the set.
      • Return TRUE.
  5. Similarly, check for all the other diagonals.
  6. Finally, return FALSE.
Time Complexity

O(M + (N*Q*logM)), where ‘M’ is the size of ‘BULB’, ‘N’ is the number of rows or columns, and ‘Q’ is the number of queries.

 

We traverse all the elements of the ‘BULB’ array to turn ON the bulbs which take O(M) time. We then run a loop to find results for each query that takes O(Q) time, and for each query, we check in the same row and columns and in all diagonals whether a turned ON bulb is present that takes O(N) time. We also search for elements in the set that takes O(logM) time. Therefore, the overall time complexity will be O(M + (N*Q)).

Space Complexity

O(M), where ‘M’ is the size of ‘BULB’.

 

We use a set to store the bulbs’ positions that are turned ON, which can take O(M) space. Therefore, the overall space complexity will be O(M).

Code Solution
(100% EXP penalty)
Matrix Illumination
Full screen
Console