I have an N×N grid containing '.' and '#', along with U cell updates. Each cell belongs to a group of up to four positions related by horizontal and vertical reflection. The initial answer is the minimum number of changes needed to make every symmetric group contain the same character. For each update, one cell toggles between '.' and '#', and I print the new minimum after the toggle.
The initialization examines every symmetric group, which is O(N²), and each update currently examines only the affected group of up to four cells. Since U can be as large as 100,000, I expected the solution to fit within the time limit, but it still exceeds the limit. Is there an issue with the implementation or a more efficient way to maintain the answer?
2 Answers
Your posted update loop already appears to inspect only four cells, so its asymptotic complexity is O(N² + U), not O(N²U). The time limit may therefore be caused by the particular constraints, input handling, or unnecessary work in the implementation rather than the basic algorithm.
You can simplify the update code substantially: compute the four coordinates once, count the two characters, subtract min(counts), toggle the selected cell, recount or adjust the counts, and add the new minimum. Avoid repeatedly clearing and rebuilding lists, and use buffered input such as sys.stdin.buffer.read() if the input is large.
You do not need to recompute the whole grid after every update. Treat each reflected set of up to four cells as an independent group. For each group, store how many '.' and '#' cells it contains, and add min(dotCount,hashCount) to the global answer.
When a cell toggles, calculate the other three reflected coordinates to identify its group. Subtract that group's old contribution, change the cell, update the two character counts, and add the group's new contribution. Since a group has at most four cells, every update is O(1), giving O(N² + U) total time, with O(N²) memory if the grid is stored.
The initial O(N²) pass is fine. The important part is that the contribution must be updated only for the one symmetry group containing the changed cell; there is no reason to scan the entire grid again.
Also remember that the center cell of an odd-sized grid forms a group of size one, and cells on the middle row or column may form groups of size two. The same min(counts) formula works for all of those cases.