# Finding all possible bottom-most overlapping rectangles on a table

Let's say that I'm given a $n\times n$ ($n\leq 1000$) grid (more of like a table) and I color the grid with $n^2$ rectangles, each of a different color (let's say they have colors 1 to $n^2$ for simplicity). The color of the rectangle that is colored the latest on a cell will remain that color. For example, I could have the following progression:

 0 0 0 0 0 0 0 0 0

 1 1 0 1 1 0 0 0 0

 1 1 0 1 2 2 0 2 2

 1 1 3 1 2 3 0 2 3

Of course, the example would continue for all $n^2$ colors, and you are only given the final state as the input. For example, the input we would be given is only the last grid of the 4 above. From it, you have to determine, what is the number of possible colored rectangles that could have been painted first?

My initial idea is that any rectangle that "overlaps" another rectangle cannot be the bottommost. For example, in the sample, we know that color 2 cannot be the bottommost because it "covers" color 1. On the other hand, color 1 and color 3 do not cover any other colors, so they can be the bottommost. I suspect that this can lead to an algorithm, but how?

• We are only given the final state as an input. The initial part of the question was to just provide an example of how the table is colored. We would like to count the number of colors that could have been colored first. For example, in the sample, colors 1 and 3 could have been colored first if we are given the final sample. Furthermore, colors 4 through 9 also could have been colored first and completely covered later (since there are 9 colors). – qt. Mar 11 '17 at 18:24
• So you want to count the number of colors, not the number of rectangles? Your question says you want to count the number of rectangles, and doesn't say you want to count the number of possibilities for which color was first. Please edit the question to (a) clarify, and (b) remove incorrect statements. – D.W. Mar 11 '17 at 18:26
• There is 1 rectangle for each color. – qt. Mar 11 '17 at 18:26
• Please credit the source of this problem. Is this from an open programming competition/contest? Where did you encounter this problem? – D.W. Mar 11 '17 at 23:44
• This question is copied directly from an active USACO programming contest -- rather disappointing to see participants in our contest cheating this way... (I'm the contest director). – Brian Dean Mar 14 '17 at 4:36