3x3 Subrectangles of a Painted Grid
Recently I participated in a coding competition and couldn't figure out this question. The problem statement is as follows
You have a 10^9 * 10^9 grid of white cells with 10^5 of them painted black. For each integer j from 0 to 9 , output the number of 3x3 subrectangles that contain exactly j black cells. The time limit is 3 seconds and the memory limit is 256mb.
I had a vague idea that goes something like: iterate through the black cells and examine the cells in the 5x5 rectangle centered at your black cell, and then count 3x3 rectangles (which I believe would be an O(n) solution where n is the number of black cells, but I'm not sure how to even go about implementing this or how to deal with double counting.
The site has an Editorial for this question, but it's in Japanese and Google translate has been of no use.
My algorithm is as follows:
Have 2 ordered sets, 1 for the points and 1 for the top-left coordinate of each 3x3 subrectangle. This is for efficient searching for duplicates and black cells
For each black cell, process the 9 3x3 rectangles it is in
For each 3x3 rectangle, check if the top-left coordinate is already in the set
2a. If it is, ignore the rectangle
2b. If it isn't, count the number of black cells in the rectangle (by checking if a black cell exists in each cell)
Insert the new top-left coordinate into the set and add 1 to the appropriate counter.
To calculate the number of 3x3 rectangles that do not have any black cells, you can take (H-2)*(W-2) - number of rectangles with at least 1 black cell
The algorithm should take ~O(Nlog(N)) steps. Step 1 takes O(N) time, step 2 takes O(9*9*logN) = O(logN) . Step 3 takes O(logN) time.
上一篇: 在数组中排列学生测试分数
下一篇: 绘画网格的3x3子矩形