Ctrl K

Lamps on a Giant Board

Hard
A square board of size n × n has a lamp in every cell, all switched off at first. The list lamps names the lamps that are on: [r, c] is the row and column. A cell may appear in the list more than once; it is still a single lamp. A lamp that is on lights its own cell and every cell in the same row, the same column and on both diagonals through it. Then the checks in checks are processed in order, each one a cell [r, c]. For a check, first decide whether that cell is lit, then switch off the lamp in it and in all eight neighbouring cells (sharing a side or a corner), if they are on. Return a list holding, for every check, 1 if the cell was lit and 0 if it was not.
Example 1
n=6, lamps=[[2, 3], [5, 0]], checks=[[0, 1], [1, 3], [0, 3]] → [1, 1, 0]

(0, 1) is on a diagonal with lamp (2, 3), so it is lit. (1, 3) shares that lamp's column, so it is lit too, and lamp (2, 3) goes out as a neighbour. Nothing lights (0, 3) now: lamp (5, 0) shares no row, column or diagonal with it.

Example 2
n=4, lamps=[[1, 1], [1, 1]], checks=[[1, 2], [3, 3]] → [1, 0]

The lamp is listed twice but it is a single lamp. (1, 2) shares its row, so it is lit, and the lamp goes out as a neighbour. After that the board is dark.

Constraints
  • 1 ≤ n ≤ 10⁹
  • 0 ≤ len(lamps), len(checks) ≤ 20000
  • 0 ≤ r, c < n
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsComplete the Sudoku HardSmallest Absent Positive HardEvery Way to Space the Words HardStars on One Straight Line HardIslands After Each Landfill Hard
loading Python…
Input
n=6, lamps=[[2, 3], [5, 0]], checks=[[0, 1], [1, 3], [0, 3]]
Expected
[1, 1, 0]

Run checks the first 3 tests in your browser. Submit checks all 85 tests on the server, hidden ones included.