3x3 Subrectangles of a Painted Grid

Question

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.

Answer 1

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

1. For each black cell, process the 9 3x3 rectangles it is in

2. 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)

3. 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.